资源描述：
《谷歌(Google)算法面试题》由会员上传分享，免费在线阅读，更多相关内容在工程资料-天天文库。
1、谷歌(Google)算法面试题1.谷歌血试题：给定能随机生成整数1到5的函数，写11!能随机生成整数1到7的函数。冋答：此题的关键是让生成的1到7的数出现概率相同。只要我们可以从n个数屮随机选出1到n个数，反复进行这种运算，直到剩下最后一个数即可。我们可以调用n次给定函数，生成n个：［到5之间的随机数，选取最大数所在位置即可满足以上要求。例如初女台的7个数［1,2,3,4,5,6,7］.7个1至05的随机数［5,3,1,4,2,5,5］那么我们保留下［1,6,7］,3个1到5的随机数［2,4,1］那么我们保留下［
2、6］6就是我们这次生成的随机数。2.谷歌面试题：判断一个自然数是否是某个数的平方。当然不能使用开方运算。回答：假设待判断的数字是N。方法1：遍历从1到N的数字，求取平方并和N进行比较。如果平方小于N,则继续遍历；如果等于N,则成功退出；如果大于N,则失败退出。复杂度为0("0.5)。方法2：使用二分查找法，对1到N之间的数字进行判断。复杂度为O(logn)。方法3：由于(n+l)A2=nA2+2n+l,°"•••=l+(2*l+l)+(2*2+l)+...+(2*n+l)注意到这些项构成了等差数列(每项之问相差2
3、)。所以我们可以比较N-l,N-l-3,N-1-3-5…和0的关系。如果大于0,则继续减；如果等于0,则成功退出；如果小于0,则失败退岀。复杂度为0(20.5)。不过方法3屮利用加减法替换掉了方法1屮的乘法，所以速度会更快些。3.谷歌面试题：给定一个数据流，其中包含无穷尽的搜索关键字(比如，人们在谷歌搜索时不断输入的关键字）。如何才能从这个无穷尽的流屮随机的选取1000个关键字？回答：定义长度为1000的数组。对于数据流中的前1000个关键字，显然都要放到数组中。对于数据流屮的的第n（n>1000）个关键字，我们
4、知道这个关键字被随机选屮的概率为1000/no所以我们以1000/n的概率用这个关键字去替换数组中的随机一个。这样就可以保证所有关键字都以1000/n的概率被选中。对于后面的关键字都进行这样的处理，这样我们就可以保证数组中总是保存着1000个随机关键字。1.谷歌面试题：将下列表达式按照复杂度排序2AnnAGoogol（其中Googol=10A100）n!nm回答：按照复杂度从低到高为nAGoogol2Ann!nF2.谷歌面试题：在半径为1的圆中随机选取一点。回答：假设圆心所在位置为坐标元点（0,0）。方法1.在x
5、轴［-1,1］，y轴卜1,1］的正方形内随机选取一点。然后判断此点是否在圆内（通过计算此点到圆心的距离）。如果在圆内，则此点即为所求；如果不在，则重新选取直到找到为止。正方形的面积为4,圆的面积为pi,所以正方形内的随机点在圆内的概率是pi/4o方法2.从［0,2*pi）屮随机选一个角度，对应于圆屮的一条半径，然后在此半径上选一个点。但半径上的点不能均匀选取，选取的概率应该和距圆心的反度成正比，这样才能保证随机点在圆内是均匀分布的。3.谷歌面试题：给定一个未知长度的整数流，如何随机选取一个数冋答：方法1.将整个整
6、数流保存到一个数组中，然后再随机选収。如果整数流很长，无法保存下来，则此方法不能使用。方法2.如果整数流在第一个数后结朿，则我们必定会选第一个数作为随机数。如果整数流在第二个数后结束，我们选第二个数的概率为坨。我们以以的概率用第2个数替换前而选的随机数，得到满足条件的新随机数。••••如果整数流在第n个数后结束，我们选第n个数的概率为我们以"n的概率用第n个数替换前面选的随机数，得到满足条件的新随机数。••••利用这种方法，我们只需保存一个随机数，和迄今整数流的长度即可。所以可以处理任意长的整数流。6•谷歌面试题
7、：给定一个未知长度的整数流，如何随机选取一个数回答：方法1.将整个整数流保存到一个数组中，然后再随机选取。如果整数流很长，无法保存下来，则此方法不能使用。方法2.如果整数流在第一个数后结束，则我们必定会选第一个数作为随机数。如果整数流在第二个数后结束，我们选第二个数的概率为以。我们以m的概率用第2个数替换前面选的随机数，得到满足条件的新随机数。••••如果整数流在第n个数后结束，我们选第n个数的概率为1/n。我们以］/n的概率用第n个数替换前面选的随机数，得到满足条件的新随机数。••••利用这种方法，我们只需保存
8、一个随机数，和迄今整数流的长度即可。所以可以处理任意长的整数流。1.谷歌而试题：设计一个数据结构，其中包含两个函数，1.插入一个数字，2.获得中数。并估计时间复杂度。回答：1.使用数组存储。插入数字时，在0(1)时间内将该数字插入到数组最后。获取中数吋，在0(n)吋间内找到中数。(选数组的第一个数和其它数比较，并根据比较结果的大小分成两组，那么我们可以确定屮数在哪组屮。然
