Google 技术 面试

1.谷歌面试题：给定能随机生成整数1到5的函数，写出能随机生成整数1到7的函数。

求大牛指点：如果要求随机的次数最少，该怎么选择呢？有泛化解么？

回答：此题的关键是让生成的1到7的数出现概率相同。

只要我们可以从n个数中随机选出1到n个数，反复进行这种运算，直到剩下最后一个数即可。

　　我们可以调用n次给定函数，生成n个1到5之间的随机数，选取最大数所在位置即可满足以上要求。

　　例如

　　初始的7个数[1,2,3,4,5,6,7].

　　7个1到5的随机数[5,3,1,4,2,5,5]

　　那么我们保留下[1,6,7],

　　3个1到5的随机数[2,4,1]

　　那么我们保留下[6]

6就是我们这次生成的随机数。

 

2．谷歌面试题：设计一个数据结构，其中包含两个函数，1.插入一个数字，2.获得中数。并估计时间复杂度。

　　回答：

　　1.使用数组存储。　　

　　插入数字时，在O(1)时间内将该数字插入到数组最后。

　　获取中数时，在O(n)时间内找到中数。（选数组的第一个数和其它数比较，并根据比较结果的大小分成两组，那么我们可以确定中数在哪组中。然后对那一组按照同样的方法进一步细分，直到找到中数。）

　　2.使用排序数组存储。

　　插入数字时，在O(logn)时间内找到要插入的位置，在O(n)时间里移动元素并将新数字插入到合适的位置。

　　获得中数时，在O(1)复杂度内找到中数。

　　3.使用大根堆和小根堆存储。

　　使用大根堆存储较小的一半数字，使用小根堆存储较大的一半数字。

　　插入数字时，在O(logn)时间内将该数字插入到对应的堆当中，并适当移动根节点以保持两个堆数字相等（或相差1）。

　　获取中数时，在O(1)时间内找到中数。

3. 谷歌面试题：给定一个数据流，其中包含无穷尽的搜索关键字（比如，人们在谷歌搜索时不断输入的关键字）。如何才能从这个无穷尽的流中随机的选取1000个关键字？

　　

　　回答：

　　定义长度为1000的数组。

　　对于数据流中的前1000个关键字，显然都要放到数组中。

　　对于数据流中的的第n（n>1000）个关键字，我们知道这个关键字被随机选中的概率为1000/n。所以我们以1000/n的概率用这个关键字去替换数组中的随机一个。这样就可以保证所有关键字都以1000/n的概率被选中。

　　对于后面的关键字都进行这样的处理，这样我们就可以保证数组中总是保存着1000个随机关键字。

4. 谷歌面试题：将下列表达式按照复杂度排序

　　2^n

　　n^Googol(其中Googol=10^100)

　　n!

　　n^n

　　回答：

　　按照复杂度从低到高为

　　n^Googol

　　2^n

　　n!

　　n^n

5. 谷歌面试题：在半径为1的圆中随机选取一点。

回答：假设圆心所在位置为坐标元点(0,0)。 
　　

方法1.

在x轴[-1,1]，y轴[-1,1]的正方形内随机选取一点。然后判断此点是否在圆内（通过计算此点到圆心的距离）。如果在圆内，则此点即为所求；如果不在，则重新选取直到找到为止。

正方形的面积为4，圆的面积为pi，所以正方形内的随机点在圆内的概率是pi/4。

　　

方法2.

从[0,2*pi)中随机选一个角度，对应于圆中的一条半径，然后在此半径上选一个点。但半径上的点不能均匀选取，选取的概率应该和距圆心的长度成正比，这样才能保证随机点在圆内是均匀分布的。

6. 谷歌面试题：给定一个未知长度的整数流，如何随机选取一个数

　　回答：　　

　　方法1.

　　将整个整数流保存到一个数组中，然后再随机选取。

　　如果整数流很长，无法保存下来，则此方法不能使用。

　　方法2.

　　如果整数流在第一个数后结束，则我们必定会选第一个数作为随机数。

　　如果整数流在第二个数后结束，我们选第二个数的概率为1/2。我们以1/2的概率用第2个数替换前面选的随机数，得到满足条件的新随机数。

　　....

　　如果整数流在第n个数后结束，我们选第n个数的概率为1/n。我们以1/n的概率用第n个数替换前面选的随机数，得到满足条件的新随机数。

　　....

　　利用这种方法，我们只需保存一个随机数，和迄今整数流的长度即可。所以可以处理任意长的整数流。