谷歌筆試真題一：

選擇題：

1.關于整數，下列說法正確的是：

A.忘了

B. 32位的機器上，8位加法比 32位加法更快

C.整數加法最好不要溢出，否則會浪費內存

D.一般來講，整數除法比乘法更加費時間

2.在 OSI標準鐘，下列協議哪個位于最底層：

A. HTTP

B. FTP

C. IP

D. TCP

3.給一段代碼，問正確的是：

大概是兩個函數，其中一個里面調用了 malloc但是沒有釋放，另一個申請了局部

數組 a[20M]

A.動態申請效率會比較高

B.聲明局部數組的那個函數可能有內存泄露

C.聲明局部數組的那個函數可能會導致運行時棧溢出

4. 28.5625的 4進制表示

A.121.XX

B.XXXX

C121.XX

D130.21

5.關于垃圾回收機制，下列說法錯誤的是

A.在這個機制下，程序員不必顯式回收內存

B.現在的垃圾回收機制能夠處理循環引用

C.垃圾回收機制能夠讓程序員更方便地寫代碼

D.有垃圾回收機制的語言肯定不會導致內存泄露

6.下列加密方法，哪個不能用于加密文本：

A. MD5

B. RSA

C. RC4

D. DES

7.有 3個 a，5個 b，2個 c，現在對他們做全排列，其中包含至少一個"abc"串的

排列數是多少?

A. 8!

B.好大一個數

C. 840

D. 780

E. 69

8.給定一個無向帶權連通圖，求最大生成樹(權重和最大的生成樹)鄰接矩陣為{xxxxx}{xxxxx}{xxxxx}{xxxxx}{xxxxx}

A 11 b 12 C 13 D 14 E 15

9.一個節點數不小于 3的二叉樹，至少刪除幾個點能夠讓它不連通?

A0 B1 C2 D3 E4

10.關于操作系統的說法，哪個是錯誤的?

A. XX(好像是微內核)和 XX(忘記是啥了)在現在仍然是比較新的概念

B.系統調用是用戶態和內核態連接的接口

C.操作系統為用戶程序提供運行平臺

D.文件系統和 XX必須實現在內核態

參考答案：D C C D D A D D B D

三道大題：

1.一個環，N個點，任意相鄰兩點有一個距離。要求寫一個算法，輸入為點 i和點j，輸出是他們之間的最短路徑

2.一個字符串，去除重復的空格，并且把子段 reverse

3. X<10^6，如何用任意的 100、50、20、10、5、2、1來加出 X，求所有方法

谷歌筆試真題二：

以下是2011年google中國筆試題，共有10道選擇題，3道大題。大家也來練一練，看看自己能做對多少題。

選擇題

1、考的是正則表達式，什么字符串匹配，沒看過。2、在 Intel 8086中，加減乘除那個

2、整數運算最耗時。

3、看程序，寫算法，考察的是 unsigned short類型的范圍。

4、19本書，編號從 1-19。從中抽五本，任意相鄰兩本不是相鄰編號的情況有多少種。

5、N為滿二叉樹的葉子節點數，求總結點數。

6、排序算法：在最壞情況下時間復雜度為 O(nlogn)的是歸并，快速，冒泡，插入中的哪個。

7、房價 200萬，每年以 10%的速度遞增，工程師為 40萬年薪，問什么時候買得起房。

8、有兩個有序數組長度為 M和 N，將兩個數組合并，最好情況下比較幾次。M次，N次，Min(M,N),Max(M,N)。

9、TLB和 Cache的區別，這個題不會，沒聽說過 TLB。

10、數據庫的試題。

編程題

1、寫函數 double value(double x,double A[],double N) double A[N]存儲多項式f(x)=a0+a1x+a2x^2+……的系數。N為已知。

2、有 2^K隊伍比賽，按照 order給出一個比賽順序的排列，order表示編號為 i的

隊的位臵，記不太清了，有 winner[j]表示 i,j兩隊比賽結果，只有勝負沒有平局，winner[j]=winner[j]求 result[]里面存放各隊比賽排名。

3、給一些字母連接規則比如 ABC->D表示前面是 ABC后面可以接 D，求是否可以無限接下去，或者求最大長度。

谷歌筆試真題三：

1、Solve this cryptic equation, realizing of course that values for M and E could

be,interchanged No leading zeros are allowed.6 WWWDOT - GOOGLE = DOTCOM.

2、Write a haiku describing possible methods' for predicting search traffic seasonality.

3、

1

11

21

1211

111221

What is the next line?

4、You are in a maze of twisty little passages, all alike. There is a dusty laptop here witha'weak wireless connection. There are dull, lifeless gnomes strolling about. What dost thoudo?

A) Wander aimlessly, bumping into obstacles until you are eaten by a grue.

B) Use the laptop as a digging device to tunnel to the next level.

C) Play MPoRPG until the battery dies along with your hopes.

D) Use the computer to map the nodes of the maze and discover an exit path.

E) Email your resume to Google, tell the lead gnome you quit and find yourself in whole different world.

5、What’s broken with Unix? How would you fix it?

6、On your first day at Google, you discover that your cubicle mate wrote the textbook.You used as a primary resource in your first year of graduate school. Do you:

A) Fawn obsequiously and ask if you can have an autograph.

B) Sit perfectly still and use only soft keystrokes to avoid disturbing her concentration.

C) Leave her daily offerings of granola and English toffee from the food bins.

D) Quote your favorite formula from the textbook and explain how it’s now your mantra.

E) Show her how example 17b could have been solved with 34 fewer lines of code.

7、Which of the following expresses Google over-arching philosophy?.

A) "I’m feeling lucky",

B) "Don’t be evi”

C) "Oh, I already fixed that"

D) "You should never be more than 50 feet from food"

E) All of the above

8、How many different ways can you color an icosahedron with one of three colors on each face? What colors would you choose?

9、This space left intentionally blank. Please fill it with something that improves uponemptiness.

10、On an infinite, two-dimensional, rectangular lattice of 1-ohm resistors, what is the resistance between two nodes that are a knight’s move away?

11、It’s 2 PM on a sunny Sunday afternoon in the Bay Area. You’re minutes from the Pacific Ocean, redwood forest hiking trails and world class cultural attractions. What do you do?

12、In your opinion, what is the most beautiful math equation ever derived?

13、 Which of the following is NOT an actual interest group formed by Google employees?

A)Women’s basketball

B)Buffy fans

C)Cricketeers

D)Nobel winners

E)Wine club

14、What will be the next great improvement in search technology?

15、What is the optimal size of a project team, above which additional members do not contribute productivity equivalent to the percentage increase in the staff size?

A) 1

B) 3

C) 5

D) 11

E) 24

16、Given a ABC, how would you use only a compass and straight edge to find a point such that s ABP, ACP and BCP have equal perimeters? (Assume that ABC is constructed so that a solution does exist.)

17、Consider a function which, for a given whole number n, returns the number of ones

required when writing out all numbers between 0 and n. For example, f(13)=6. Notice that

f(1)=1.What is the next largest n such that f(n)=n?!

18、What’s the coolest hack you’ve ever written?

19、It is known in refined company, that choosing K things out of N can be done in ways as many as choosing N minus K from N: I pick K, you the remaining. Find though a cooler bijection,where you show a knack uncanny, of your choices contain all K of mine. Oh, for pedantry: let K be no more than half N.

20、What number comes next in the sequence:10, 9, 60, 90, 70, 66,?

A)96

B)10000000000000000000000000000000000000000000000000000000000000000000

000000000000000000000000000000000

C)Either of the above

D)None of the above

21、In 29 words or fewer, describe what you would strive to accomplish if you worked at Google Labs.

谷歌筆試真題四：

1.1關于 IP協議哪個正確?

A、IP是 TCP上層協議

B、IP協議是應用層協議

C、由于兩個屬于同一層協議，他們之間可以直接通信

D、IP協議不提供可靠的通信

1.2關于內存正確的是()。

A、內存的存取速度不能低于 cpu速度，否則會造成數據丟失。

B、程序只有在數據和代碼等被調入內存后才能運行。

C、采用虛擬內存技術后程序可以在硬盤上直接運行。

D、某計算機的內存容量為 16MB，那么他的地址總線為 24位。

1.3單鏈表中結點的結構為(data，link)，若想刪除結點 p(不是頭節點或者尾結點)的直接后繼，則應執行下列哪個操作?()

A、p=p->link; p->link=p->link->link;

B、p->link->link=p->link;

C、p=p->link->link;

D、p->link=p->link->link;

1.4已知 x>=y and y>=z為真，那么 x>z or y=z值為()。

A、真

B、假

C、無法確定

D、x y z同為正數時為真

1.5某請求被隨即分配到四臺機器進行處理，分配到每臺機器的概率 A15%，B20%，C30%，D35%,處理請求的失敗概率分別為 5%，4%，3%，2%，現在請求失敗，問由 C造成的概率最接近()

A、26%

B、28%

C、30%

D、32%

1.6假設我們用 d=(a1,a2,….a5)表示無向無環圖 G的 5個頂點的度數，下面給出的哪組值是可能的?()

A、{3,4,4,3,1}

B、{4,2,2,1,1}

C、{3,3,3,2,2}

D、{3,4,3,2,1}

1.7設棧 S和隊列 Q的初始狀態為空，元素 e1，e2，e3，e4，e5，e6一次壓入棧 S,一個元素出棧后即進入隊列 Q，若出隊列的順序為 e2,e4,e3,e6,e5,e1則棧 S的容量要求最小值為?()

A、2

B、3

C、4

D、5

1.8在堆排序算法中我們用一個數組 A來模擬二叉樹 T，如果該 A[0]存放的是 T的根節點，那么 A[K](K>0)的父親節點是?()

A、(K-1)/2

B、K/2

C、(K+1)/2

D、都不對

1.9現有如下任務需要安排在若干機器上并行完成，每個任務都有開始時間和結束時間(開始和結束時間都包括在任務執行時間內)的要求。

則最少需要使用的機器數目為?()

A、1

B、2

C、3

D、4

1.10在設計一個操作系統時，哪項不是必須考慮的?()

A、設備管理模塊

B、文件系統模塊

C、用戶管理模塊

D、進程管理模塊

2.1正整數序列 Q中的每個元素都至少能被正整數 a和 b中的一個整除，現給定a和 b，需要計算出 Q中的前幾項，例如，當 a=3，b=5，N=6時，序列為 3，5，6，9，10，12。

(1)設計一個函數 void generate(int a,int b,int N ,int * Q)計算 Q的前幾項。

(2)設計測試數據來驗證函數程序在各種輸入下的正確性。

2.2有一個由大小寫組成的字符串，現在需要對他進行修改，將其中的所有小寫字母排在答謝字母的前面(大寫或小寫字母之間不要求保持原來次序)，如有可能盡量選擇時間和空間效率高的算法 c語言函數原型 void proc(char *str)也可以采用你自己熟悉的語言。

2.3已知一顆無向無環連通圖 T的所有頂點和邊的信息，現需要將其轉換為一棵樹，要求樹的深度最小，請設計一個算法找到所有滿足要求的樹的根結點，并分析時空復雜度(描述算法即可，無需代碼)。

谷歌筆試經驗一：

昨天剛參加 Google 宣講和筆試，考得很基礎，共享一下筆試題目，奇文共賞之。共有10道選擇題，3 道大題。

1.考的是正則表達式，什么字符串匹配，沒看過。

2.在 Intel 8086 中，加減乘除那個整數運算最耗時。很基礎哇。

3.看程序，寫算法，考察的是 unsigned short 類型的范圍。程序有點長，變量名還相似，想不起來了，

4.19 本書，編號從 1-19。從中抽五本，任意相鄰兩本不是相鄰編號的情況有多少種。這個題誰會啊，大家發帖探討一下。

5.N 為滿二叉樹的葉子節點數，求總結點數。確實很基礎。

6.排序算法：在最壞情況下時間復雜度為 O(nlogn)的是歸并，快速，冒泡，插入中的哪個。

7.房價 200 萬，每年以 10%的速度遞增，工程師為 40 萬年薪，問什么時候買得起房。

8.有兩個有序數組長度為 M 和 N，將兩個數組合并，最好情況下比較幾次。M 次，N 次，Min(M,N),Max(M,N)

9.TLB 和 Cache 的區別，這個題不會，沒聽說過 TLB。上網查了查，TLB：Translation lookaside buffer,即旁路轉換緩沖，或稱為頁表緩沖;里面存放的是一些頁表文件(虛擬地址到物理地址的轉換表)。大家還是自己上網了解吧。

10.數據庫的試題，偶記不清了，不過不難。

大題

一、寫函數 double value(double x,double A[],double N) double A[N]存儲多項式 f(x)=a0+a1x+a2x^2+……的系數。N為已知。

二、有 2^K 隊伍比賽，按照 order 給出一個比賽順序的排列，order 表示編號為 i 的隊的位置，呀呀，記不太清了，有 winner[j]表示 i,j 兩隊比賽結果，只有勝負沒有平局，winner[j]=winner[j]求 result[]里面存放各隊比賽排名。貌似用遞歸，只是小弟拙見。

三、KOF 里連招，簡化為 ABCD……Z 求最長連招……記不清了，見諒，XDJM補充。

谷歌筆試經驗二：

昨天晚上去蹭了一下Google的招聘筆試。其實是去打醬油的，主要是為了感受一下Google的出題風格和考試氛圍，可以對將來找工作提供些參考。

回來之后本來想回憶一下題目的，結果發現braveheart89大大已經貼出了所有的題而且連選項都一字不差，記憶力真心佩服……以下就根據他寫的題目稍微修正一下[1]，然后隨便說說好了。(說的也不一定對，歡迎更正。)

考試是第一頁需要填寫個人信息，包括實習經歷、獲獎情況、工作地點意向(國內、國外還是兩者皆可之類，反正對我無用啦-.-)然后就是一個半小時的答題，全部手寫。

1、單項選擇題

1.1 如果把傳輸速率定義為單位時間內傳送的信息量(以字節計算)多少。關于一下幾種典型的數據傳輸速率：

1.使用USB2.0閃存盤，往USB閃存盤上拷貝文件的數據傳輸速率

2.使用100M以太網，在局域網內拷貝大文件時網絡上的數據傳輸速率

3.使用一輛卡車拉1000塊單塊1TB裝滿數據的硬盤，以100km/h的速度從上海到天津(100km)一趟所等價的數據傳輸帶寬

4.使用電腦播放MP3，電腦的PCI總線到聲卡的數據傳輸速率

在通常情況下，關于這幾個傳輸速率的排序正確的是：

A.4<1<2<3 B.1<4<2<3 C.4<1<3<2 D.1<4<3<2

1.2 對以下程序，正確的輸出結果是

#define SUB(x,y) x-y

#define ACCESS_BEFORE(element,offset,value) *SUB(&element, offset) =value

int main()

{

int array[10]= {1,2,3,4,5,6,7,8,9,10};

int i;

ACCESS_BEFORE(array[5], 4, 6);

printf("array: ");

for (i=0; i<10; ++i){

printf("%d", array[i]);

}

printf("\n");

return (0);

}A.array: 1 6 3 4 5 6 7 8 9 10

B.array: 6 2 3 4 5 6 7 8 9 10

C.程序可以正確編譯連接，但是運行時會崩潰

D.程序語法錯誤，編譯不成功

1.3 在區間[-2, 2]里任取兩個實數，它們的和>1的概率是：

A.3/8 B.3/16 C.9/32 D.9/64

1.4 小組賽，每個小組有5支隊伍，互相之間打單循環賽，勝一場3分，平一場1分，輸一場不得分，小組前三名出線。平分抽簽。問一個隊最少拿幾分就有理論上的出線希望：

A.1 B.2 C.3 D.4

1.5 用二進制來編碼字符串“abcdabaa”，需要能夠根據編碼，解碼回原來的字符串，最少需要多長的二進制字符串?

A.12 B.14 C.18 D.24

1.6 10個相同的糖果，分給三個人，每個人至少要得一個。有多少種不同分法

A.33 B.34 C.35 D.36

1.7 下列程序段，循環體執行次數是：

y=2

while(y<=8)

y=y+y;

A.2 B.16 C.4 D.3

1.8 下面哪種機制可以用來進行進程間通信?

A.Socket B.PIPE C.SHARED MEMORY D.以上皆可

1.9 下列關于編程優化的說法正確的是：

A.使用編譯器的優化選項(如-O3)后程序性能一定會獲得提高

B.循環展開得越多越徹底，程序的性能越好

C.寄存器分配能夠解決程序中的數據依賴問題

D.現代主流C/C++編譯器可以對簡單的小函數進行自動Iinline

1.10 一下程序是用來計算兩個非負數之間的最大公約數：

long long gcd(long long x, long long y) {

if( y==0) return 0;

else return gcd (y, x%y);

}我們假設x,y中最大的那個數的長度為n，基本運算時間復雜度為O(1)，那么該程序的時間復雜度為：

A.O(1) B.O(logn) C.O(n) D.O(n^2)

2、程序設計與算法(2.1,2.2為編程題，2.3為算法設計題，只需設計思路和關鍵步驟偽代碼)

2.1 寫函數，輸出前N個素數。不需要考慮整數溢出問題，也不需要使用大數處理算法。

2.2 長度為n的數組亂序存放著0至n-1. 現在只能進行0與其他數的swap，請設計并實現排序。

2.3 給定一個原串和目標串，能對源串進行如下操作：

1.在給定位置插入一個字符

2.替換任意字符

3.刪除任意字符

要求寫一個程序，返回最少的操作數，使得源串進行這些操作后等于目標串。源串和目標串長度都小于2000。

——

以下是我根據各種來源總結的參考答案：

1.1 A

USB 2.0的理論傳輸極限是480Mbps[2]，但是按照這個速率就沒有選項可選了-.-，所以猜測應該認為是普通U盤寫數據的6MB/s，即48Mbps;

100M以太網的速率就是100Mbps;

卡車拉硬盤，1000x1000x8/3600=2222Mbps，這個應該是最快的;

MP3在256kbps碼率下也平均只有1分鐘2MB，所以不會超過0.3Mbps，所以一定是最慢的。

1.2 D

這道題大家走出考場后爭議非常大。