2025年谷歌(Google)算法面试题 .pdfVIP

乐民之乐者，民亦乐其乐；忧民之忧者，民亦忧其忧。——《孟子》

谷歌（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.谷歌面试题：判断一个自然数是否是某个数的平方。当然不能使用开方运算。

回答：假设待判断的数字是N。

方法1：

遍历从1到N的数字，求取平方并和N进行比较。

如果平方小于N，则继续遍历；如果等于N，则成功退出；如果大于N，则失败退出。

复杂度为O(n^0.5)。

方法2：

使用二分查找法，对1到N之间的数字进行判断。

复杂度为O(logn)。

方法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中的乘法，所以速度会更

快些。

3.谷歌面试题：给定一个数据流，其中包含无穷尽的有哪些信誉好的足球投注网站关键字（比如，人们在谷歌有哪些信誉好的足球投注网站

穷则独善其身，达则兼善天下。——《孟子》

时不断输入的关键字）。如何才能从这个无穷尽的流中随机的选取1000个关键字？

回答：

定义长度为1000的数组。

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

对于数据流中的的第n（n1000）个关键字，我们知道这个关键字被随机选中的概率为

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.