Massive Algorithms: Algorithm Interview Misc Part 2

http://www.1point3acres.com/bbs/thread-191081-1-1.html

ab家，主力难点在算法 & coding。
算法 & coding
phone 一轮coding，线上写code，然后compile 然后跑实例。
写不完code或者实例结果不对，都很可能挂掉。
他家的难度一般都是在leetcode hard level。之前出面经题的概率挺大，但按lz最近的体会，他家新增了不少新题或者实战题目。
附录airbnb题库. 准备他家的coding，要增加胜率就只能把能见的机经都刷到吐。
leetcode 上hard的题目也要多练习。 lz结束leetcode 第四轮后，基本hard的题目都可以12分钟左右，写完bug free的code。
lz非大牛，只发现出苦力这一条路了。他家一轮面试45分钟。时间还是很紧的。遇到新题目，理解想思路要花5~10分钟。
和考官交流要5~10 分钟。跑测试，至少要5分钟。所以只能努力提速了。大家也加油。

Design ：请参考fb的design区块和下面的题库
基本相通
http://www.1point3acres.com/bbs/thread-191077-1-1.html

Culture fit：
他家这个很有意思，会有两轮。
通过只有一个技巧，他家很有前景，你很喜欢他家的服务，他家的服务能让人更好的感受local的文化。
常见问题多练习，参考附录题库。

Backgroud:
这个也没啥，自己的project和经验要准备好，常见问题多看看。

他家的面试难度，主要在coding，其他轮感觉还ok。lz最后fail在了design。 coding 倒是遇到两新题，都解完了，coding的feedback 也不错。
也没啥可惜的了。lz尽力了。

=============================题库了=============================

From Glassdoor：

1. Given a list ofstrings, return all pairs of strings that can make a palindrome. 高频

2. TextJustification, Alien Dictionary

3. How fast canyou parse strings?

The problem I was giveninvolved a bunch of ugly string data parsing and using a heuristic to modifythe data in a certain way. It was an easy problem, but they wanted a fullyworking solution within the short time limit. I couldn't finish it in time.Pick a language that has as little verbosity as possible and don't botherengaging with the interviewer because they don't care to speak with you. Theyjust want to see how fast you can code.

4. Write a CSV parser. Parse an escaped string into csvformat. 高频

5. Return the coins combination with the minimum number ofcoins.Time complexity O(MN), where M is the target value and N is the number ofdistinct coins. Space complexity O(M).

6. I had a phone screen question involving examination ofsubsets.

7. Check top 10 questions on leetcode

8. Implement a circular buffer using an array.

http://stackoverflow.com/questions/590069/how-would-you-code-an-efficient-circular-buffer-in-java-or-c-sharp

9. Provide a set of positiveintegers (an array of integers). Each integer represent number of nights userrequest on Airbnb.com. If you are a host, you need to design and implement analgorithm to find out the maximum number a nights you can accommodate. Theconstrain is that you have to reserve at least one day between each request, sothat you have time to clean the room.

Example:
1) Input: [1, 2, 3]===> output: 4, because you will pick 1 and 3
2) input: [5,1, 2, 6] ===> output: 11, because you will pick 5 and 6
3) input: [5,1, 2, 6, 20, 2] ===> output: 27, because you will pick 5, 2, 20

10. Given a set of numbersin an array which represent number of consecutive days of AirBnB reservationrequested, as a host, pick the sequence which maximizes the number of days ofoccupancy, at the same time, leaving atleast 1 day gap in between bookings forcleaning. Problem reduces to finding max-sum of non-consecutive array elements.

// [5, 1, 1, 5] => 10
The above array would represent an examplebooking period as follows -
// Dec 1 - 5
// Dec 5 - 6
// Dec 6 - 7
// Dec 7 – 12

The answer would be to pick dec 1-5 (5 days)and then pick dec 7-12 for a total of 10 days of occupancy, at the same time,leaving atleast 1 day gap for cleaning between reservations.

Similarly,
// [3, 6, 4] => 7
// [4, 10, 3, 1, 5] => 15

11. Boggle implementation (word search I, II)

12. Given a dictionary, and a matrix of letters, find all thewords in the matrix that are in the dictionary. (Going across, down ordiagonally)

What SQL columns you should index and how would you change the indexing in different lookup scenarios? .鐣欏璁哄潧-涓€浜�-涓夊垎鍦�
What can you teach me in a few minutes?
find all the combinations of a string in lowercase and uppercase. For example, string "ab" -> "ab", "Ab", "aB", "AB". So, you will have 2^n (n = number of chars in the string) output strings. The goal is for you to test each of these string and see if it match a hidden string。. 1point 3acres 璁哄潧
Implement a simple regex parser which, given a string and a pattern, returns a booleanindicating whether the input matches the pattern. By simple, we mean that the regex can only contain special character: * (star), . (dot), + (plus). The star means what you'd expect, that there will be zero or more of previous character in that place in the pattern. The dot means any character for that position. The plus means one or more of previous character in that place in the pattern.
Tell me about why you want to work here. . 鐣欏鐢宠璁哄潧-涓€浜╀笁鍒嗗湴
Find all words from a dictionary that are x edit distance away.
Store a set of sudden-death tournament results in a compact format (eg. a bit array) and a set of predicted match results (also in a bit array). Score the predictions, giving one point per correctly guessed match, without unpacking the bit array into a more convenient format (ie. you have to traverse the tree in-place).

20. Lots of treequestions (implement a BST, score sudden-death tournament results with a minimalbinary tree data structure, encode an alien dictionaryusing a tree and then produce a dictionary using topological traversal), and a"rebuild Twitter from the ground up" scaling/architecture question.

Describe what happens when you enter a url in the web browser
Sort a list of numbers in which each number is at a distance k from its actual position
You have a plain with lots of rectangles on it, find out how many of them intersect . 鐣欏鐢宠璁哄潧-涓€浜╀笁鍒嗗湴
Binary search tree

From MITBBS

1. http://www.mitbbs.com/article_t/JobHunting/32309663.html

regexmatch, slightly complicated version of http://leetcode.com/2011/09/regular-expression-matching.html

find maxium square inside a sqaure, similar tohttp://stackoverflow.com/questio ... argest-square-block

edit distance

2. http://www.mitbbs.com/article_t/JobHunting/32864407.html

3. http://www.mitbbs.com/article_t/JobHunting/32779809.html

alien dictionary，我还被问了两轮这题。。。
还有meetingroom2

4. http://www.mitbbs.com/article_t/JobHunting/33129803.html

电面二话不说上来就做题
一个餐馆，菜单上各种食物价格如下
A， $ X.XX
B， $ Y.YY
C， $ Z.ZZ
D, $ ...

问现在一个人有一定数额的钱，比如 $MM.MM，如何点菜才能把钱全部花完？
面试官要求列出所有可能的组合
我用了recursive的方法，写出来了
但是在比较 floatnumber的时候，细节没有处理好
直接比较 X.XX ==Y.YY 会出现错误，所以必须要做差来比较
经面试官提醒改了过来
然后周一被通知挂了

这题除了用recursive方法，有更好的解法吗？DP?

From 一亩三分地

http://www.1point3acres.com/bbs/forum.php?mod=forumdisplay&fid=145&sortid=311&searchoption[3046][value]=37&searchoption[3046][type]=radio&sortid=311&filter=sortid&page=1

1. http://www.1point3acres.com/bbs/forum.php?mod=viewthread&tid=176102&extra=page%3D1%26filter%3Dsortid%26sortid%3D311%26searchoption%5B3046%5D%5Bvalue%5D%3D37%26searchoption%5B3046%5D%5Btype%5D%3Dradio%26sortid%3D311

RT，白人面试官，感觉非常冷，啥都不问，上来直接做题。题目是2D iterator，加一个remove。我10多min就写完了，但是面试官说能run，但是design不太好，让我换一种方法。提示利用iterator的remove方法，我对iterator的remove方法不是很熟，我说能不能查api，他说可以。
然后我就查api，然后lz对api里说的看不大懂，然后面试官帮忙run了一个case，然后我懂了，然后就改，然后又出了几个很傻逼的bug，最后面试官说再给你1min调，然后lz终于调出来。然后面试官说great。（感觉安慰我）。然后我就问问题，但是很傻逼的是，我问的问题和那个面试官做的东西不一样，面试官不懂怎么回答，然后我就让他讲了一下他的工作，然后我又问了2个。然后就Bye了。

2. http://www.1point3acres.com/bbs/forum.php?mod=viewthread&tid=165457&extra=page%3D1%26filter%3Dsortid%26sortid%3D311%26searchoption%5B3046%5D%5Bvalue%5D%3D37%26searchoption%5B3046%5D%5Btype%5D%3Dradio%26sortid%3D311

首先是三个技术面：
1） AlienDictionary
2） Text Justification
3）写echoTCP client，向面试官的server发请求，读回数据。地里比较少人说这种，我来详细说一下，情境是这样的：想象你开车，踩下油门，车会加速，放开油门，车会减速。 client向server发的请求有以下2种：（a）STATUS --表示查询现在车的速度和踩下踏板的压力；（b）THROTTLE 50.1 --- 这条指令是“THROTTLE” 加上一个数字，表示我现在将踩油门的压力调为50.1 .鐣欏璁哄潧-涓\

http://www.1point3acres.com/bbs/thread-191141-1-1.html
电面的主体基本是两部分
1 coding ＆算法
2 简单 behavious question 和 back groud question

本帖会介绍下前期的准备工作和几个实战的例子。

1 coding ＆算法
准备阶段，lz是只做leetcode，现在大概有330+道题目。基本能cover 所有的类型了。 lz 也知道有其他网站啥的。但是lz觉得还是在质不在量。如果把这些题目都吃透了，那基本能cover 90%以上的面试了。 lz的策略就是集中突破leetcode。

lz的战法目标是提高总体胜率，不是针对单一公司。整体胜率就是我面10家，能有70%的胜率。

lz用的是四遍突破法：
第一、二遍熟悉题目，找到简单解法，自己联系写code
第三遍找其他解法，和最优解法。
第四遍追求速度和准确率

刷题攻略在这里
http://www.1point3acres.com/bbs/ ... D311%26sortid%3D311

能力强的大家，也可以合并第一二遍，就是三遍突破了。

面试前一周，这一周很关键，大家都知道要面哪个公司了，这时候要对特定公司重点突破了，就是找面经，找面经，找面经。。。基本技能大家应该都有。。。 lz用的是这几个地方：一亩三分地，mitbbs，glassdoor。
然后就是狂刷这些题目了。

面试：这就是实战了。大公司phone interview 时候关注的主要是三方面，记住是三方面：
一 communication
二 logic
三 code quality

分开讲： communication 个人感觉是最重要的，大公司录取你，要确保你能和现有员工愉快的一起工作。所以如果有communication的问题，那你code 写的再好，可能也是stop。而且你的分数是考古打得 =。 =。  具体点就是你能不能很好的理解考官出的题目，以及考官能否完全理解你的解法。写code前一定要多和考官说几句，让他明白你的思路，然后再写code。面试最后5分钟一般会让你问问题，这个你也要准备好。不要全是大众问题。。。如你怎么分配时间啥的。。考官都答吐了。。要有创新。。。

logic：这部分就是你的解法了，解法要简明，容易理解。不要绕弯路。刷题的时候大家研究解法的时候应该多注意。

code quality:  这个也是日常基本功，你的code分段要清晰，能share或者resued的code，写进单独的method里。这个网上很多文章，大家按自己的语言练习吧。

这里讲个实战的例子吧：
Clone a linked list with next and random pointer

http://www.geeksforgeeks.org/a-l ... -and-arbit-pointer/

补充内容 (2016-5-20 22:34):
机经部分，lz可能会花点时间收集收集，然后分享，需要些时间。需要的大家，记得收藏本帖，不要错过呦。。。

补充内容 (2016-5-20 22:35):
lz 其他几个帖子

面试经验谈（facebook，airbnb，google，linkedin，amazon
http://www.1point3acres.com/bbs/ ... D311%26sortid%3D311

补充内容 (2016-5-20 22:43):
面试经验谈（facebook，airbnb，google，linkedin，amazon
http://www.1point3acres.com/bbs/ ... D311%26sortid%3D311

补充内容 (2016-5-20 22:43):
FB 面经 phone & onsite  攻略附录题库呦
http://www.1point3acres.com/bbs/thread-191077-1-1.html

补充内容 (2016-5-20 22:43):
airbnb 面经 phone interview & onsite 附录题库呦
http://www.1point3acres.com/bbs/ ... D311%26sortid%3D311

补充内容 (2016-5-20 22:44):
lz的刷题攻略
http://www.1point3acres.com/bbs/ ... D311%26sortid%3D311

http://www.1point3acres.com/bbs/thread-190169-1-1.html

(高频)Wall flower 问题(bomb enemy 问题), x 是花,y 是墙,在哪个位置能看到最多的花(只
能横竖,不能对角)
X 0 0 0
X 0 Y X
0 X 0 0

假设只有墙能够遮挡视线，花不会互相遮挡，且只能站在0位置观察。

笨一点的方法：可以对每一行的第i位置，从左到右依次算出这行中每个i的左边有多少可见的花；然后再从右向左，算出每个i的右边有多少可见的花。然后对每一列也如此操作（只是计算顺序改成上-下和下-上）。

这样数组中的每个位置会得到4个数字。这4个数字的和就是这个位置能看到的花的总数。找出最大值即可。
时空复杂度都是O(N^2)，其中N是矩阵的边长。

https://raw.githubusercontent.com/UmassJin/Leetcode/master/Design/%E9%9D%A2%E7%BB%8F%E5%88%86%E4%BA%AB0616.py

A家电面：
     1 given 2 strings，can you construct str1 using chars in str2？
     2 binary tree inorder traversal，both recursively and iteratively
     3 erase given value item in linked list 
     4 how to debug memory leak in c++?
     5 design a parking lot.
F家：
-------
电面：
     \一个数组里有多个最大值，等概率随机返回其中一个最大值的index，
要求one pass。LC 的 permutations

Onsite：
     1 国人大哥（人很好，放我的水）： merge k sorted lists, best time to buy
and sell stock。
     2 印度经理： 背景+behavior+一个编程：code base在某个版本开始有bug，找到
这个版本。
     3 老美： LC 的 minimum window substring, decode ways。
     4 中东人： LC的valid palindrome。 给1， 2， 5面值的纸币，有多少种组合凑
出100 块钱。
     5 三哥：设计题，传输10G的data到5个data center，每个data center 有1000的
节点。三哥从问背景就开始找茬，面试过程中要求解gossip protocol的微分方程， 被
黑。
     面试完，立刻投诉三哥，因为所有其他面试官都给了strong recommend，于是加
面设计题
     6. 老美（高级别，大牛人）：设计iPhone Find Friends 的后端。Geohashing +
DHT解之

F家的面试官水平都很高， 都很乐意和你讨论他们的project， 当然如果你很恰当的给
出comment，会给你加分不少。
设计题问得很细，比如DHT如何实现，单机的Hash table如何实现能节省内存， 如何做
concurrency control，如何实现mutex之类的。

F家的算法：
----------------
    1. F家的题基本上都是Leetcode 的原题和变种。把leetcode的题研究透就OK了。
    2. 跟F家的HR 聊过， 如果你想拿到面试官的strong recommendation, 需要在一
轮面试中做完两道题。每题15-17分钟完成，包括和面试官讨论，写代码，以及写test 
case 的时间， 同时尽量bug free， 不一定要optimal solution。 
    3. 时间很紧，所以要多练习白板码，多练习在白板上跑test case。写多了就会发
现，白板码上写出bug的概率比用电脑写低很多， 因为白板上可以通过图表的形式很直
观的跑test case， 很容易发现bug。
    4. 面试的时候，自己带fine tip marker， 比粗的笔写代码快很多。

G家的算法：
--------------
    1. G家的题库很大，而且经常换新题，我面试的时候一道都没有见过，所以刷题用
处不大。
       G家的题基本上都是经典算法的变种。如果对经典算法很熟练，面试的时候很快
就可以想到解法。
   2. 复习经典算法，推荐看一下Sedgewick 教授的算法书。http://algs4.cs.princeton.edu/home/
        相比算法导论，我更推荐这本书，因为这本书的算法是用Java而不是伪代码实
现的，而且代码写的非常简洁而优雅。
        Sedgewick教授的书里没有 DP专门的章节，看看算法导论作为补充。
    3. G家喜欢考各种tree：prefix tree，augmented binary search tree (with 
rank and select APIs), segment tree，binary index tree （1D and 2D), 
interval tree, kd tree, quad tree. 
    4. G家喜欢考几何题，推荐：
           topcoder的教程：http://help.topcoder.com/data-science/competing-in-algorithm-challenges/algorithm-tutorials/
           Sedgwick的介绍几何算法（sweep line之类）的video：https://www.
youtube.com/watch?v=Igr6yONkpIQ
    5. G家关于设计棋类游戏的AI的题，基本上都可以用MinMax 算法解决: http://neverstopbuilding.com/minimax
    6. G家和F家都会考 Thread-Safe data structure和 Threading Pool，推荐阅读C
++ concurrency in action的第六章和第九章 http://www.manning.com/williams/

系统设计：
     1. 我基本没有web development的经验。和我一样0经验的同学可以先上一门课，
推荐Reddit Cofounder 开的web development
的课( 讲义和课程project都非常好）：https://www.udacity.com/course/viewer#!/c
-cs253/ 
     2. 对于distributed system不了解的同学，推荐coursera上的Cloud Computing 
Concept：https://www.coursera.org/course/cloudcomputing
     3. 系统设计里边，最重要的部分是Data Storage和Data processing。
         Data storage包含：
              a. Distributed File System: 推荐看一下GFS的paper和FB Haystack 
Photo storage的paper
              b. NoSQL Data storage: 推荐看一下Big Table的paper，了解一下
Cassandra 的架构：Cloud Computing Concept的课有讲
              c. Memcache
         Data processing：
              看一下Map-Reduce的paper。了解一下Map-Reduce能解决什么问题。如
何做job scheduling等等。

     4. 板上大牛收集的题库：https://www.evernote.com/shard/s21/sh/c2035c38-
1a80-4fd4-8c93-8ca0ad9ffb48/35079ac1bf5ae3ea
         大多数题，解题的时候，按三步走：
               a. 如果数据量小，如何在单机上实现。
               b. 如果数据量大，如何sharding data，如何实现scalability
               c. Fault tolerance，考虑有node failure和message loss的时候这
么处理。

所以这里我觉得比较有用的准备方法是，在弄明白一个design之前，先要做好几个准备

1. 先把一个process或者一个系统是怎么工作的搞清楚，这里是指，design一个
service需要cpu，memory，disk，network等等很多component协调工作，这些东西分别
都在什么时候用到，为什么要有这些东西，分别有什么特点。
相信大家都很熟悉有一篇文章叫做The numbers eveyone should know，在没有这篇文
章基础上的design都是瞎扯。

2. 要清楚这个design到底是为了解决什么问题，use case是什么，design一个系统根
本上讲是为了解决一个存在的problem，这个problem会有general的要求，比如latency
，比如throughput，比如load，比如哪种操作比较频繁，比如有没有consistency要求
，是不是reactive，是不是需要highly available，等等等等，这样跟第1点相结合才
能明白瓶颈可能在哪里，哪些东西可以tradeoff，进而才会有design的solution

3. knowledge base的储备要尽量够，操作系统，distributed system，concurrency这
些东西很难啃，我也曾经自学过几个大学的distributed system公开课，很多同学想绕
过这些走捷径，但是越难的东西就越有价值。知识量不够不是问题，看一点补充一点，
只要能坚持下来，到了一个时间点基本上还是可以有质变的。


FB 高频题
1 sort colors, O(n)时间, O(1)空间.      https://leetcode.com/problems/sort-colors/
2 One Edit Distance, Given two strings S and T, determine if they are both one edit distance apart.       https://leetcode.com/problems/one-edit-distance/
3 A set of points(x, y), 返回前k个离原点最近的点, 用k-selection 或者堆（代码见附件）
4 Flatten Binary Tree to Linked List   https://leetcode.com/problems/flatten-binary-tree-to-linked-list/
5 Remove Element 将一个01随机数列中，把1全部移到左边，要求移动次数最少

http://www.1point3acres.com/bbs/thread-173645-1-1.html
选择题两道：
1. 把一堆数放到一个set 里，然后再从set 把数放到list里，并排序，问你结果是多少...
2. int i = 1; while(i < N){ i *= 2;}; 复杂度多少...

码题三道：
1. LeetCode Valid Parentheses, 原题...
2. 给一个binary tree 的root node, 让你找某个值是不是在tree里... 是扣1，不是扣0...
3. cut the sticks, hackerrank 原题。地址是这个：https://www.hackerrank.com/challenges/cut-the-sticks
http://algobox.org/quad-tree-of-black-and-write-image/

Original Post 1

Original Post 2

Design a QuadTree for a black and white image which support the following operations:

count the number of black/white pixels;
calculate the ratio of black pixels;
combine two QuadTrees to make a new one: black plus black is black otherwise white.

Solution

Token Bucket

Original Post

Given a string compress and decompress it use the following format, for example:

s = "adddbffffsssssscvvvvv"

c = "a3xdb4xf6xsc5xv"

A lot of corner cases needs to be considered. s = "3xd", s = "3", s = "x".

Score Gathering – AlgoBox by dietpepsi
We have a system that records scores. We care about how many times we see the same score, and we want to maintain a rough ordering. We also want to send this information over the wire so that it can be collated with other results. As such we have decided to represent the stream of scores, and the count of how many times we see the same score, as an unbalanced binary search tree.
Your job is to write a method that will take a stream of integer scores, and put them into a tree while counting the number of times each score is seen. The first score from the given list should occupy the root node. Then you need to traverse the tree breadth-first to generate a string representation of the tree. Scores are to be inserted into the tree in the order that they are given.
For example, if you were given the stream of scores: [4, 2, 5, 5, 6, 1, 4].
That would result in the tree with the following structure where each node is represented as score:count.

1

2

3

4

5

4:2

/ \

2:1 5:2

/ \

1:1 6:1

When serialized this tree is represented by the string: 4:2,2:1,5:2,1:1,,,6:1
Each score:count entry is delimited with a comma. Empty children with a sibling do not output anything, but retain the comma delimiter.
Company : Amazon

http://algobox.org/top-stocks
http://www.1point3acres.com/bbs/thread-160877-1-1.html
1. add two numbers (link list)

Give a stream of stock prices, design a data structure to support the following operations:
1. void update(String stock, double price) add or update the price of a stock to the data structure.
2. List<Map.Entry<String, double>> top(int k) return the top k price stocks and their current prices.

Company : Bloomberg Phone

http://www.1point3acres.com/bbs/thread-160113-1-1.html

Construct binary tree from preorder and inorder traversal, Leetcode原题。

给一个数组，一个target，求Num of combinations that sums to the target。

e.g. [1, 2, 3] target = 3. return 4. [1, 1, 1], [1, 2], [2, 1], [3].

Square

两轮peer programming.

实现Luhn Check
实现Version Control（具体是存 <key, value> with timestamp，当输入time和key时要给出value。还有些其他功能实现，比如size、remove、add。但主要思想就是这样。）

题都不难，不过要求correctness，一定要有OOP设计，实现起来会很容易。跟其他鸡精一样，Square的电面什么都要自己写，testcase，main()…… 比起算法更重视正确性。

假设a == b，什么情况下 ++a != ++b，只考虑single thread。

在往disk写数据时，一般prefer把small IO整合成big IO然后读写，为什么？

两道算法题，很简单，都是鸡精原题。

Mirror Tree
TopK

Cask

说起来很有意思，收到LinkedIn推广邮件说这家公司正在招人, looking for candidates like you… 当时连这公司是做什么的都不知道就手贱申请了，第二天来了电面通知。电面问很多基础问题，妥妥被虐。

virtual class, pure virtual class, virtual destructor.

static variable, static class, singleton pattern vs static, 包括何时存在于内存的什么部分.

function pointer vs function referenced.

还有一些Hadoop问题和其他基础问题。

一道算法题。Candies，Leetcode原题。

fitbit有OA的，OA的题设计得不好，corner case给得不明确。题是这样，给一个字符串，要求把数字后面的字符重复数字那么多次后输出。比如：oneab 输出 ab，abtwocd 输出 abccd。至于oneonea是输出onea还是十一个a，就没有解释……
fitbit code base都是JAVA

http://www.1point3acres.com/bbs/thread-142441-1-1.html
桌子上有3n个object围成一个圈，每个object都有一个value，你和你的两个好朋友每次各从桌子上拿一个，你先选，之后你的朋友再选，而且你的朋友只能拿你拿的那个object的左右相邻的两个。问如何才能让你自己拿的objects的value的总和最大？（注意不是总和比朋友大，而是在自己所有不同拿法中总和的值最大）

如果朋友是为了配合你拿到所有拿法的最大可能的话，这题就比较简单：比如有2n个数字，那么先找出其中较小的n个值（记为O）和较大的n个值（记为X）。那么，这个圈可能看起来就是：
OOOXXOOOOXXOXXXX->back to 0
这个样子
那么从圈中任意一点开始，任意方向（比如顺时针）旋转。当找到了第一个“前面是O的”X时，那么“你”就拿这个X，然后朋友拿其前面的O。然后重复这个过程。到最后“你”拿的一定都是X，也就是最大的n个，朋友拿的一定是最小的n个。因此“你”的收益一定是最大化的。用O(n)额外内存的话，这算法可以用O(n)时间实现。
我的理解是我pick了一个后，两个朋友只能pick左右两边的value，然后continue
http://www.1point3acres.com/bbs/thread-145894-1-1.html

洗牌问题只允许调用一次 random(), 如果让结果随机呢?

http://www.1point3acres.com/bbs/thread-143007-1-1.html
一个数组，能不能做一次互换变成有序
当你看到一个下降点的时候……
如果这个数组是可调整的，那么它也只有一种换法：把大的丢到后面；而且这种换法的调整位置是唯一的。

换完还不是有序的……那就可以返回0了

http://www.allenlipeng47.com/blog/index.php/2014/12/24/find-median-out-of-5-numbers/

In quickselect, it requires to find the median out of the group of 5 numbers. Here I found a way from stackoverflow link. It requires 6 comparisons.

Start a mergesort with the first 4 elements and order each pair (2 comparisons)
Compare the two lower ones of each pair and eliminate the lowest one from the possibilities (3 comparisons)
Add in the 5th number set aside to the number without a pair and compare the two (4 comparisons)
Compare the two lowest of the two new pairs and eliminate the lower one (5 comparisons)
Compare the one by itself and the lower of the last pair and the lower number is the medianThe possible median is within the parentesis

Algorithm Interview Misc Part 2

Original Post 1

Original Post 2

See also Quadtree.

Solution

Original Post

Labels

Popular Posts