Airbnb Skype 新题

Skype两轮，第一轮word search，要求output最多的词并且词与词之间在board上不重合。第二轮新题，也可能是老题，但我翻近期的面经贴没看到过：
Given a very large array, which you could only do sequencial access, not random access. Find out the medium of the array.

我面试经验不足，花了很久理解什么叫“could only do sequencial access, not random access”，说白了就是只能遍历array，不能access array by given index. 后来面试官给了思路：遍历len/2次array，每次找到max，然后下次找剩余element的max. 第len/2次得到的max就是medium。接着面试官说可以log n解，方法是pick up a number by random (我面试时理解的是pick up an index by random, 后来想想因为不能random access所以估计是直接生成一个random number)，过一遍array，count number of elements smaller than our guess. 如果count结果大于len/2,说明guess number大了，因此next round guess = (min of array + guess) / 2. 于是变成binary search。

据说这道题是uber的常考题，但先前也没有看过uber面经。花了将近一周把airbnb每道面经题都写了两遍，可惜都没用上。面试以来诸多不顺，有时看地里的帖子会觉得每个人都难免有起有落，心里稍微好受点。希望与大家共勉吧。

找 median 我第一反应是用俩 heap，不过空间复杂度太高了。还是 binary search 靠谱。

另外，时间复杂度应该是 nlogn 吧

谢面经！！！楼主onsite了嘛