谷歌是不少IT人都想去的企业，笔试和面试是必经之路，如今校园招聘的季节。袭击和整理IT名企经典笔试题是拿到offer的捷径！为此在网络上整理了些 很经典的笔试题目 和答案，细致阅读必有帮助！！
1.谷歌笔试题：推断一个自然数是否是某个数的平方。
当然不能使用开方运算。
如果待推断的数字是 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个keyword
给定一个数据流，当中包括无穷尽的搜索keyword（比方，人们在谷歌搜索时不断输入的keyword）。怎样才干从这个无穷尽的流中随机的选取1000个keyword？
定义长度为1000的数组。
对于数据流中的前1000个keyword。显然都要放到数组中。
对于数据流中的的第n（n>1000）个keyword。我们知道这个keyword被随机选中的概率为 1000/n。所以我们以 1000/n 的概率用这个keyword去替换数组中的随机一个。这样就能够保证全部keyword都以 1000/n的概率被选中。
对于后面的keyword都进行这种处理，这样我们就能够保证数组中总是保存着1000个随机keyword。
2.谷歌笔试题：将下列表达式依照复杂度排序
将下列表达式依照复杂度排序
2^n
n^Googol (当中 Googol = 10^100)
n!
n^n
依照复杂度从低到高为
n^Googol
2^n
n!
n^n
3. 谷歌笔试题：在半径为1的圆中随机选取一点
如果圆心所在位置为坐标元点(0, 0)。
方法1.
在x轴[-1, 1]，y轴[-1, 1]的正方形内随机选取一点。然后推断此点是否在圆内（通过计算此点到圆心的距离）。假设在圆内，则此点即为所求；假设不在，则又一次选取直到找到为止。
正方形的面积为4。圆的面积为pi，所以正方形内的随机点在圆内的概率是 pi / 4。
方法2.
从[0, 2*pi)中随机选一个角度，相应于圆中的一条半径，然后在此半径上选一个点。但半径上的点不能均匀选取。选取的概率应该和距圆心的长度成正比，这样才干保证随机点在圆内是均匀分布的。
4.谷歌笔试题：给定一个未知长度的整数流。怎样随机选取一个数
有个叫蓄水池抽样。就是随机选取一个数的方法！
方法1.
将整个整数流保存到一个数组中。然后再随机选取。
假设整数流非常长，无法保存下来。则此方法不能使用。
方法2.
假设整数流在第一个数后结束，则我们必然会选第一个数作为随机数。
假设整数流在第二个数后结束，我们选第二个数的概率为1/2。我们以1/2的概率用第2个数替换前面选的随机数，得到满足条件的新随机数。
....
假设整数流在第n个数后结束。我们选第n个数的概率为1/n。我们以1/n的概率用第n个数替换前面选的随机数，得到满足条件的新随机数。
....
利用这样的方法。我们仅仅需保存一个随机数，和迄今整数流的长度就可以。所以能够处理随意长的整数流。
5.谷歌笔试题：设计一个数据结构。当中包括两个函数。1.插入一个数字，2.获得中数。
并预计时间复杂度。
1. 使用数组存储。
插入数字时，在O(1)时间内将该数字插入到数组最后。
获取中数时。在O(n)时间内找到中数。（选数组的第一个数和其他数比較，并依据比較结果的大小分成两组。那么我们能够确定中数在哪组中。然后对那一组依照相同的方法进一步细分。直到找到中数。）
2. 使用排序数组存储。
插入数字时。在O(logn)时间内找到要插入的位置。在O(n)时间里移动元素并将新数字插入到合适的位置。
获得中数时，在O(1)复杂度内找到中数。
3. 使用大根堆和小根堆存储。
使用大根堆存储较小的一半数字，使用小根堆存储较大的一半数字。
插入数字时，在O(logn)时间内将该数字插入到相应的堆其中。并适当移动根节点以保持两个堆数字相等（或相差1）。
获取中数时，在O(1)时间内找到中数。
给定一个固定长度的数组。将递增整数序列写入这个数组。当写到数组尾部时。返回数组開始又一次写，并覆盖先前写过的数。
请在这个特殊数组中找出给定的整数。
如果数组为a[0, 1, ..., N-1]。
我们能够採用类似二分查找的策略。
首先比較a[0]和a[N/2]，假设a[0] < a[N/2]。则说明a[0,1,...,N/2]为递增子序列，否则还有一部分是递增子序列。
然后推断要找的整数是否在递增子序列范围内。假设在，则使用普通的二分查找方法继续查找；假设不在，则反复上面的查找过程。直到找到或者失败为止。
给定两个已排序序列，找出共同的元素。
最好还是如果序列是从小到大排序的。定义两个指针分别指向序列的開始。
假设指向的两个元素相等。则找到一个同样的元素。假设不等，则将指向较小元素的指针向前移动。
反复运行上面的步骤，直到有一个指针指向序列尾端。
本文转自mfrbuaa博客园博客，原文链接：http://www.cnblogs.com/mfrbuaa/p/5238687.html，如需转载请自行联系原作者
