IT名企面試：谷歌筆試題
谷歌是不少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（n>1000）個關鍵字，我們知道這個關鍵字被隨機選中的概率為 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個數替換前面選的隨機數，得到滿足條件的新隨機數。
....
利用這種方法，我們只需保存一個隨機數，和迄今整數流的長度即可。所以可以處理任意長的整數流。#p#
谷歌筆試題：設計一個數據結構，其中包含兩個函數，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]為遞增子序列，否則另一部分是遞增子序列。
然后判斷要找的整數是否在遞增子序列范圍內。如果在，則使用普通的二分查找方法繼續查找；如果不在，則重復上面的查找過程，直到找到或者失敗為止。
給定兩個已排序序列，找出共同的元素。
不妨假設序列是從小到大排序的。定義兩個指針分別指向序列的開始。
如果指向的兩個元素相等，則找到一個相同的元素；如果不等，則將指向較小元素的指針向前移動。
重復執行上面的步驟，直到有一個指針指向序列尾端。
谷歌筆試題：找到鏈表的倒數第m個節點。
方法1：
首先遍歷鏈表，統計鏈表的長度N。
然后再次遍歷鏈表，找到第N-m個節點，即為倒數第m個節點。
方法2：
使用兩個指針，并使它們指向的節點相距m-1個。
然后同時向前移動兩個指針，當一個指針指***一個節點時，第二個指針指向倒數第m個節點。
兩個方法的復雜度都是O(n)。
但是當N較大而m較小時，方法2可能會更快一些。因為方法2能更好利用CPU的緩存。
更多閱讀：
http://baike.baidu.com/view/2089.htm CPU -> 緩存
谷歌筆試題：給定一個排序數組，如何構造一個二叉排序樹？
采用遞歸算法。
選取數組中間的一個元素作為根節點，左邊的元素構造左子樹，右邊的節點構造有子樹。
谷歌筆試題：數組中是否有兩個數的和為10
1.比較任意兩個數的和是否為10。如
for (int i = 0; i < n; ++i) { for (int j = i+1; j < n; ++j) { .... }}
復雜度為O(n*n)。
2.將數組排序后，對每個數m，使用二分查找在數組中尋找10-m。
復雜度為O(nlogn)。
3.將數組存儲到hash_set中去，對每個數m，在hash_set中尋找10-m。
復雜度為O(n)。
4.如果數組很大，超過內存的容量，可以按照hash(max(m, 10-m))%g，將數據分到g個小的group中。然后對每個小的group進行單獨處理。
復雜度為O(n)。
谷歌筆試題：找到兩個字符串的公共字符，并按照其中一個的排序
寫一函數f(a,b)，它帶有兩個字符串參數并返回一串字符，該字符串只包含在兩個串中都有的并按照在a中的順序。寫一個版本算法復雜度O(N^2)和一個O(N)
O(N^2)：
對于a中的每個字符，遍歷b中的每個字符，如果相同，則拷貝到新字符串中。
O(N)：
首先使用b中的字符建立一個hash_map，對于a中的每個字符，檢測hash_map中是否存在，如果存在則拷貝到新字符串中。
給定一個整數序列，其中有些是負數，有些是正數，從該序列中找出***和的子序列。比如：-5，20，-4，10，-18，子序列[20，-4，10]具有***和26。
- ` int GetMaxSubArraySum(int* array, int array_len) {
- ` int current_sum = 0;
- ` int max_sum = 0;
- ` for (int i = 0; i < array_len; ++i) {
- ` current_sum += array[i];
- ` if (current_sum > max_sum) {
- ` max_sum = current_sum;
- ` } else if (current_sum < 0) {
- ` current_sum = 0;
- ` }
- ` }
- ` return max_sum;
- ` }
- 或者
- int maxsum(int n,int[] list)
- {
- int ret,sum=0;
- int i;
- for (ret=list[i=0];i<n;i++)
- sum=(sum>0?sum:0)+list[i],ret=(sum>ret?sum:ret);
- return ret;
- }
#p#谷歌筆試題：將無向無環連通圖轉換成深度最小的樹
已知一個無向無環連通圖T的所有頂點和邊的信息，現需要將其轉換為一棵樹，要求樹的深度最小，請設計一個算法找到所有滿足要求的樹的根結點，并分析時空復雜度。
最簡單直接的方法就是把每個節點都試一遍：
假設某個節點為根節點，計算樹的深度。當遍歷完所有節點后，也就找到了使樹的深度最小的根節點。
但這個方法的復雜度很高。如果有n個節點，則時間復雜度為O(n^2)。
樹的深度取決于根節點到最深葉節點的距離，所以我們可以從葉節點入手。
葉節點會且只會和某一個節點連通（反之不成立，因為根節點也可能只和一個節點連通），所以我們很容易找到所有可能的葉節點。
題目可以等價于找到了兩個葉節點，使得兩個葉節點之間的距離最遠。根節點就是這兩個葉節點路徑的中間點（或者中間兩個點的任意一個）。
我們可以每次都將連接度為1的節點刪掉，直到***只剩下1個或2個節點，則這一個節點，或者兩個節點中的任意一個，就是我們要找的根節點。
谷歌筆試題：將字符串中的小寫字母排在大寫字母的前面
有一個由大小寫組成的字符串，現在需要對它進行修改，將其中的所有小寫字母排在大寫字母的前面（大寫或小寫字母之間不要求保持原來次序）。
初始化兩個int變量A和B，代表字符串中的兩個位置。開始時A指向字符串的***個字符，B指向字符串的***一個字符。
逐漸增加A的值使其指向一個大寫字母，逐漸減小B使其指向一個小寫字母，交換A，B所指向的字符，然后繼續增加A，減小B....。
當A>=B時，就完成了重新排序。
i指向***一個小寫字符，j尋找小寫字符。
- void swapString(char* str, int len)
- {
- int i=-1;
- int j=0;
- for(j=0; j<len; j++)
- {
- if(str[j]<='z' && str[j]>='a')
- {
- i++;
- swap(str[i], str[j]);
- }
- }
- }
谷歌筆試題：在重男輕女的國家里，男女的比例是多少？
在一個重男輕女的國家里，每個家庭都想生男孩，如果他們生的孩子是女孩，就再生一個，直到生下的是男孩為止。這樣的國家，男女比例會是多少？
還是1：1。
在所有出生的***個小孩中，男女比例是1：1；在所有出生的第二個小孩中，男女比例是1：1；.... 在所有出生的第n個小孩中，男女比例還是1：1。
所以總的男女比例是1：1。
谷歌筆試題：如何拷貝特殊鏈表
有一個特殊的鏈表，其中每個節點不但有指向下一個節點的指針pNext，還有一個指向鏈表中任意節點的指針pRand，如何拷貝這個特殊鏈表？
拷貝pNext指針非常容易，所以題目的難點是如何拷貝pRand指針。
假設原來鏈表為A1 -> A2 ->... -> An，新拷貝鏈表是B1 -> B2 ->...-> Bn。
為了能夠快速的找到pRand指向的節點，并把對應的關系拷貝到B中。我們可以將兩個鏈表合并成
A1 -> B1 -> A2 -> B2 -> ... -> An -> Bn。
從A1節點出發，很容易找到A1的pRand指向的節點Ax,然后也就找到了Bx，將B1的pRand指向Bx也就完成了B1節點pRand的拷貝。依次類推。
當所有節點的pRand都拷貝完成后，再將合并鏈表分成兩個鏈表就可以了。
- class ListNode
- {
- int value;
- ListNode* p_next;
- ListNOde* p_rand;
- public ListNode(int v, ListNode* next, ListNode* rand): value(v), p_next(next), p_rand(rand)
- {
- }
- };
- ListNode*copyList(ListNode*p)
- {
- if(p!=null)
- {
- /*構建交叉數組 p0->q0->p1->q1->p2->q2...*/
- ListNOde*ppre=p;
- ListNode*post=->next;
- while(pre!=null)
- {
- pre->next=newListNode(pre->value,post,pre->p_rand->p_next);
- pre=last;
- lastlast=last->p_next;
- }
- /*拆分成被拷貝數組和拷貝數組 p0->p1->p2....;q0->q1->q2....*/
- ppre=p;
- ListNode*res=p->p_next;
- while(res->p_next!=null)
- {
- p->p_next=res->p_next;
- res->p_next=res->p_next->p_next;
- }
- returnres;
- }else
- {
- returnp;
- }
- }
如果在高速公路上30分鐘內看到一輛車開過的幾率是0.95，那么在10分鐘內看到一輛車開過的幾率是多少？(假設為常概率條件下)
假設10分鐘內看到一輛車開過的概率是x，那么沒有看到車開過的概率就是1-x，30分鐘沒有看到車開過的概率是(1-x)^3，也就是0.05。所以得到方程(1-x)^3 = 0.05
解方程得到x大約是0.63。
谷歌筆試題：從25匹馬中找出最快的3匹
最少需要7次。
首先將馬分成a,b,c,d,e 5個組，每組5匹，每組單獨比賽。然后將每組的***名放在一起比賽。假設結果如下
a0,a1,a2,a3,a4
b0,b1,b2,b3,b4
c0,c1,c2,c3,c4
d0,d1,d2,d3,d4
e0,e1,e2,e3,e4
其中a, b,c,d,e小組都是按照名次排列（速度a0>a1>a2>a3>a4, b0>b1....)。并第6次比賽的結果為a0>b0>c0>d0>e0。
那么第6次比賽結束后，我們知道最快的一匹為a0。
我們知道第2名的馬一定是a1或者b0，所以在接下來的比賽中要包含這兩匹馬。如果a1快，那么第3名是a2或者b0，如果b0快，那么第3名是a1，b1或者c0。也就是說第2名和第3名一定在a1，a2，b0，b1和c0當中，所以在第7場比賽中包括這5匹馬就可以得到第2名和第3名。
所以7次比賽就可以獲得前3名的馬。#p#
谷歌筆試題：海盜分金問題
有5個海盜，按照等級從5到1排列。***的海盜有權提議他們如何分享100枚金幣。但其他人要對此表決，如果多數（所有人中的多數）反對，那他就會被殺死。他應該提出怎樣的方案，既讓自己拿到盡可能多的金幣又不會被殺死？
分配方案是98，0，1，0，1。
5級海盜會不會被殺死，取決于5級海盜死后其他海盜是否會獲得更多的利益。如果可以獲得更多的利益，則肯定會反對，如果會獲得更少的利益，則肯定會支持，如果利益沒有變化，則反對或支持都可以。
如果5級海盜死了，則有4級海盜分配，4級海盜面臨同樣的問題，需要看自己死后的利益分配變化。然后是3級海盜，2級海盜。
2級海盜無論提出什么方案，都不會有多數人反對（自己支持，另一個人反對不能構成多數反對）。所以2級海盜肯定會提出100，0的分配方案，自己獨享所有金幣。
猜到2級海盜的分配方案后，3級海盜會提出99，0，1的分配方案。這樣1級海盜因獲得了比2級海盜方案中更多的金幣，所以會支持3級海盜的方案。
猜到3級海盜的分配方案后，4級海盜會提出99，0，1，0的分配方案。這樣2級海盜獲得了比3級海盜方案中更多的金幣，所以會支持4級海盜的方案。
猜到4級海盜的分配方案后，5級海盜會提出98，0，1，0，1的分配方案。這樣1級海盜和3級海盜獲得了比4級海盜方案中更多的金幣，所以會支持5級海盜的方案。
谷歌筆試題：4人過橋問題
4 個人晚上要穿過一座索橋回到他們的營地。可惜他們手上只有一支只能再堅持17分鐘的手電筒。通過索橋必須要拿著手電，而且索橋每次只能撐得起兩個人的份量。這四個人過索橋的速度都不一樣，***個走過索橋需要1分鐘，第二個2分鐘，第三個5分鐘，最慢的那個要10分鐘。他們怎樣才能在17分鐘內全部走過索橋？
1）***個和第二個一起過去，用掉2分鐘；
2）***個回來，用掉1分鐘；
3）第三個和第四個一起過去，用掉10分鐘；
4）第二個回來，用掉2分鐘；
5）***個和第二個一起過去，用掉2分鐘。
總共用掉17分鐘。
谷歌筆試題：如何從8只球中找出比較重的一個
你有8個一樣大小的球，其中7個的重量是一樣的，另一個比較重。怎樣能夠用天平僅稱兩次將那個重一些的球找出來。
解答：
先取6個，天平上一邊3個，同重則稱剩余2個即可；不同重，則取重的3個中的2個來稱。
分析：
此題可以通過倒推法來解決。
如果我們知道重球在某兩個球中，則可以通過天平兩邊各放一個，比較重量發現重球。
如果我們知道重球在某三個球中，則可以通過天平兩邊各放一個，如果一樣重，則第三個球是重球，否則天平上較重的即是重球。
如果我們知道重球在大于等于四個球中，則不能通過一次稱重發現重球。
所以通過***次稱重，我們必須將重球限定在某兩個或三個球當中。另外，天平兩端放的球數應該相等，否則結果基本沒有意義。
滿足兩端球相等的所有可能的比較方法
左，右
1， 1
2， 2
3， 3
4， 4
再考慮到必須將重球限定在2或3個球中，***次只能采取3，3的比較方法。
此題還可以擴展一下：在m只大小相同的球中，m-1只重量相同，另外一只比較重。問需要用天平稱多少次才能將重球找出來？
從上面的分析中可以知道，稱一次最多可以
- 將重球從3個球中找出來。
- 將重球從9個球中限定在3個球中。
- 將重球從27個球中限定在9個球中。
.....
所以，稱n次最多可以將重球從3^n中找出來。倒推回去也就可以獲得m個球需要稱多少次。
或者
我們用i+表示第i個球比較重。
共有8種可能性：1+; 2+; 3+; 4+; 5+; 6+; 7+; 8+;
將1 2 3 與4 5 6 放在天秤上稱，如果左邊中，則可以將重球確定在1 2 3中，
即可能性為：1+ 2+ 3+ 然后將1和2放在天秤兩邊稱，如果左邊重則重球為1，如果右邊重，重球為2，如果平衡重球為3。
如果平衡：7+ 8+ 將7和8放在天秤兩邊稱，可以判斷重球為7還是8
如果右邊重：4+ 5+ 6+ 同球1 2 3的情況。
【編輯推薦】
