标题

谷歌笔试题 附答案及解题思路

责任编辑:admin
日期:2012-10-26
谷歌是不少IT人都想去的企业,那么在进入公司前,少不了面试笔试的测试。那么这里我们就总结了如下谷歌笔试题,并提供了一些参考答案。希望对您有用。
谷歌笔试题:判断一个自然数是否是某个数的平方。当然不能使用开方运算。
假设待判断的数字是 N。
方法1:
遍历从1到N的数字,求取平方并和N进行比较。
如果平方小于N,则继续遍历;如果等于N,则成功退出;如果大于N,则失败退出。
复杂度为O(n^0.5)。
方法2:
使用二分查找法,对1到N之间的数字进行判断。
复杂度为O(log n)。
方法3:
由于
(n 1)^2
=n^2 2n 1,
=
= 1 (2*1 1) (2*2 1) (2*n 1)
注意到这些项构成了等差数列(每项之间相差2)。
所以我们可以比较 N-1, N ; 1 ; 3, N ; 1 ; 3 ; 5 和0的关系。
如果大于0,则继续减;如果等于0,则成功退出;如果小于 0,则失败退出。
复杂度为O(n^0.5)。不过方法3中利用加减法替换掉了方法1中的乘法,所以速度会更快些。
谷歌笔试题:如何随机选取1000个关键字
给定一个数据流,其中包含无穷尽的搜索关键字(比如,人们在谷歌搜索时不断输入的关键字)。如何才能从这个无穷尽的流中随机的选取1000个关键字?
定义长度为1000的数组。
对于数据流中的前1000个关键字,显然都要放到数组中。
对于数据流中的的第n(n1000)个关键字,我们知道这个关键字被随机选中的概率为 1000/n。所以我们以 1000/n 的概率用这个关键字去替换数组中的随机一个。这样就可以保证所有关键字都以 1000/n的概率被选中。
对于后面的关键字都进行这样的处理,这样我们就可以保证数组中总是保存着1000个随机关键字。
谷歌笔试题:将下列表达式按照复杂度排序
将下列表达式按照复杂度排序
2^n
n^Googol (其中 Googol = 10^100)
n!
n^n
按照复杂度从低到高为
n^Googol
2^n
n!
n^n
谷歌笔试题:在半径为1的圆中随机选取一点
假设圆心所在位置为坐标元点(0, 0)。
方法1.
在x轴[-1, 1],y轴[-1, 1]的正方形内随机选取一点。然后判断此点是否在圆内(通过计算此点到圆心的距离)。如果在圆内,则此点即为所求;如果不在,则重新选取直到找到为止。
正方形的面积为4,圆的面积为pi,所以正方形内的随机点在圆内的概率是 pi / 4。
方法2.
从[0, 2*pi)中随机选一个角度,对应于圆中的一条半径,然后在此半径上选一个点。但半径上的点不能均匀选取,选取的概率应该和距圆心的长度成正比,这样才能保证随机点在圆内是均匀分布的。
谷歌笔试题:给定一个未知长度的整数流,如何随机选取一个数
方法1.
将整个整数流保存到一个数组中,然后再随机选取。
如果整数流很长,无法保存下来,则此方法不能使用。
方法2.
如果整数流在第一个数后结束,则我们必定会选第一个数作为随机数。
如果整数流在第二个数后结束,我们选第二个数的概率为1/2。我们以1/2的概率用第2个数替换前面选的随机数,得到满足条件的新随机数。
....
如果整数流在第n个数后结束,我们选第n个数的概率为1/n。我们以1/n的概率用第n个数替换前面选的随机数,得到满足条件的新随机数。
....
利用这种方法,我们只需保存一个随机数,和迄今整数流的长度即可。所以可以处理任意长的整数流。
谷歌笔试题:设计一个数据结构,其中包含两个函数,1.插入一个数字,2.获得中数。并估计时间复杂度。
1. 使用数组存储。
插入数字时,在O(1)时间内将该数字插入到数组最后。
获取中数时,在O(n)时间内找到中数。(选数组的第一个数和其它数比较,并根据比较结果的大小分成两组,那么我们可以确定中数在哪组中。然后对那一组按照同样的方法进一步细分,直到找到中数。)

阅读:

相关新闻:
评论