谷歌(Google)算法面试题

1、谷歌(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那么我们保留下66就是我们这次生成的随机数。2. 谷歌面试题:判断一个自然数是否是某个数的平方。当然不能使用开方运算。回答:假

2、设待判断的数字是N。方法1:遍历从1到N的数字,求取平方并和N进行比较。如果平方小于N,则继续遍历;如果等于N,则成功退出;如果大于N,则失败退出。复杂度为O(n0.5。方法2:使用二分查找法,对1到N之间的数字进行判断。复杂度为O(logn。方法3:由于(n+12=n2+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(n0.5。不过方法3中利用加减法替换掉了方法1中的乘法,所以速度会更快些

3、。3. 谷歌面试题:给定一个数据流,其中包含无穷尽的搜索关键字(比如,人们在谷歌搜索时不断输入的关键字。如何才能从这个无穷尽的流中随机的选取1000个关键字?回答:定义长度为1000的数组。对于数据流中的前1000个关键字,显然都要放到数组中。对于数据流中的的第n(n1000个关键字,我们知道这个关键字被随机选中的概率为1000/n。所以我们以1000/n的概率用这个关键字去替换数组中的随机一个。这样就可以保证所有关键字都以1000/n的概率被选中。对于后面的关键字都进行这样的处理,这样我们就可以保证数组中总是保存着1000个随机关键字。4. 谷歌面试题:将下列表达式按照复杂度排序2nnGoo

4、gol(其中Googol=10100n!nn回答:按照复杂度从低到高为nGoogol2nn!nn5.谷歌面试题:在半径为1的圆中随机选取一点。回答:假设圆心所在位置为坐标元点(0,0。方法1.在x轴-1,1,y轴-1,1的正方形内随机选取一点。然后判断此点是否在圆内(通过计算此点到圆心的距离。如果在圆内,则此点即为所求;如果不在,则重新选取直到找到为止。正方形的面积为4,圆的面积为pi,所以正方形内的随机点在圆内的概率是pi/4。方法2.从0,2*pi中随机选一个角度,对应于圆中的一条半径,然后在此半径上选一个点。但半径上的点不能均匀选取,选取的概率应该和距圆心的长度成正比,这样才能保证随机点

5、在圆内是均匀分布的。6. 谷歌面试题:给定一个未知长度的整数流,如何随机选取一个数回答:方法1.将整个整数流保存到一个数组中,然后再随机选取。如果整数流很长,无法保存下来,则此方法不能使用。方法2.如果整数流在第一个数后结束,则我们必定会选第一个数作为随机数。如果整数流在第二个数后结束,我们选第二个数的概率为1/2。我们以1/2的概率用第2个数替换前面选的随机数,得到满足条件的新随机数。.如果整数流在第n个数后结束,我们选第n个数的概率为1/n。我们以1/n的概率用第n个数替换前面选的随机数,得到满足条件的新随机数。.利用这种方法,我们只需保存一个随机数,和迄今整数流的长度即可。所以可以处理任

6、意长的整数流。6.谷歌面试题:给定一个未知长度的整数流,如何随机选取一个数回答:方法1.将整个整数流保存到一个数组中,然后再随机选取。如果整数流很长,无法保存下来,则此方法不能使用。方法2.如果整数流在第一个数后结束,则我们必定会选第一个数作为随机数。如果整数流在第二个数后结束,我们选第二个数的概率为1/2。我们以1/2的概率用第2个数替换前面选的随机数,得到满足条件的新随机数。.如果整数流在第n个数后结束,我们选第n个数的概率为1/n。我们以1/n的概率用第n个数替换前面选的随机数,得到满足条件的新随机数。.利用这种方法,我们只需保存一个随机数,和迄今整数流的长度即可。所以可以处理任意长的整

7、数流。7.谷歌面试题:设计一个数据结构,其中包含两个函数,1.插入一个数字,2.获得中数。并估计时间复杂度。回答:1.使用数组存储。插入数字时,在O(1时间内将该数字插入到数组最后。获取中数时,在O(n时间内找到中数。(选数组的第一个数和其它数比较,并根据比较结果的大小分成两组,那么我们可以确定中数在哪组中。然后对那一组按照同样的方法进一步细分,直到找到中数。2.使用排序数组存储。插入数字时,在O(logn时间内找到要插入的位置,在O(n时间里移动元素并将新数字插入到合适的位置。获得中数时,在O(1复杂度内找到中数。3.使用大根堆和小根堆存储。使用大根堆存储较小的一半数字,使用小根堆存储较大的

8、一半数字。插入数字时,在O(logn时间内将该数字插入到对应的堆当中,并适当移动根节点以保持两个堆数字相等(或相差1。获取中数时,在O(1时间内找到中数。8. 谷歌面试题:在一个特殊数组中进行查找,给定一个固定长度的数组,将递增整数序列写入这个数组。当写到数组尾部时,返回数组开始重新写,并覆盖先前写过的数。请在这个特殊数组中找出给定的整数。回答:假设数组为a0,1,.,N-1。我们可以采用类似二分查找的策略。首先比较a0和aN/2,如果a0然后判断要找的整数是否在递增子序列范围内。如果在,则使用普通的二分查找方法继续查找;如果不在,则重复上面的查找过程,直到找到或者失败为止。9. 谷歌面试题:1024!末尾有多少个0?答案:末尾0的个数取决于乘法中因子2和5的个数。显然乘法中因子2的个数大于5的个数,所以我们只需统计因子5的个数。是5的