谷歌筆試真題一：

選擇題：

1.關(guān)于整數(shù)，下列說法正確的是：

A.忘了

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

C.整數(shù)加法最好不要溢出，否則會浪費內(nèi)存

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

2.在 OSI標(biāo)準鐘，下列協(xié)議哪個位于最底層：

A. HTTP

B. FTP

C. IP

D. TCP

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

大概是兩個函數(shù)，其中一個里面調(diào)用了 malloc但是沒有釋放，另一個申請了局部

數(shù)組 a[20M]

A.動態(tài)申請效率會比較高

B.聲明局部數(shù)組的那個函數(shù)可能有內(nèi)存泄露

C.聲明局部數(shù)組的那個函數(shù)可能會導(dǎo)致運行時棧溢出

4. 28.5625的 4進制表示

A.121.XX

B.XXXX

C121.XX

D130.21

5.關(guān)于垃圾回收機制，下列說法錯誤的是

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

B.現(xiàn)在的垃圾回收機制能夠處理循環(huán)引用

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

D.有垃圾回收機制的語言肯定不會導(dǎo)致內(nèi)存泄露

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

A. MD5

B. RSA

C. RC4

D. DES

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

排列數(shù)是多少?

A. 8!

B.好大一個數(shù)

C. 840

D. 780

E. 69

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

A 11 b 12 C 13 D 14 E 15

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

A0 B1 C2 D3 E4

10.關(guān)于操作系統(tǒng)的說法，哪個是錯誤的?

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

B.系統(tǒng)調(diào)用是用戶態(tài)和內(nèi)核態(tài)連接的接口

C.操作系統(tǒng)為用戶程序提供運行平臺

D.文件系統(tǒng)和 XX必須實現(xiàn)在內(nèi)核態(tài)

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

三道大題：

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

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

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

谷歌筆試真題二：

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

選擇題

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

2、整數(shù)運算最耗時。

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

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

5、N為滿二叉樹的葉子節(jié)點數(shù)，求總結(jié)點數(shù)。

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

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

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

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

10、數(shù)據(jù)庫的試題。

編程題

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

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

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

3、給一些字母連接規(guī)則比如 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關(guān)于 IP協(xié)議哪個正確?

A、IP是 TCP上層協(xié)議

B、IP協(xié)議是應(yīng)用層協(xié)議

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

D、IP協(xié)議不提供可靠的通信

1.2關(guān)于內(nèi)存正確的是()。

A、內(nèi)存的存取速度不能低于 cpu速度，否則會造成數(shù)據(jù)丟失。

B、程序只有在數(shù)據(jù)和代碼等被調(diào)入內(nèi)存后才能運行。

C、采用虛擬內(nèi)存技術(shù)后程序可以在硬盤上直接運行。

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

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

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同為正數(shù)時為真

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

A、26%

B、28%

C、30%

D、32%

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

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設(shè)棧 S和隊列 Q的初始狀態(tài)為空，元素 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在堆排序算法中我們用一個數(shù)組 A來模擬二叉樹 T，如果該 A[0]存放的是 T的根節(jié)點，那么 A[K](K>0)的父親節(jié)點是?()

A、(K-1)/2

B、K/2

C、(K+1)/2

D、都不對

1.9現(xiàn)有如下任務(wù)需要安排在若干機器上并行完成，每個任務(wù)都有開始時間和結(jié)束時間(開始和結(jié)束時間都包括在任務(wù)執(zhí)行時間內(nèi))的要求。

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

A、1

B、2

C、3

D、4

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

A、設(shè)備管理模塊

B、文件系統(tǒng)模塊

C、用戶管理模塊

D、進程管理模塊

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

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

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

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

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

谷歌筆試經(jīng)驗一：

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

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

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

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

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

5.N 為滿二叉樹的葉子節(jié)點數(shù)，求總結(jié)點數(shù)。確實很基礎(chǔ)。

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

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

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

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

10.數(shù)據(jù)庫的試題，偶記不清了，不過不難。

大題

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

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

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

谷歌筆試經(jīng)驗二：

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

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

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

1、單項選擇題

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

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

2.使用100M以太網(wǎng)，在局域網(wǎng)內(nèi)拷貝大文件時網(wǎng)絡(luò)上的數(shù)據(jù)傳輸速率

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

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

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

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

1.2 對以下程序，正確的輸出結(jié)果是

#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 在區(qū)間[-2, 2]里任取兩個實數(shù)，它們的和>1的概率是：

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

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

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

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

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

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

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

1.7 下列程序段，循環(huán)體執(zhí)行次數(shù)是：

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 下列關(guān)于編程優(yōu)化的說法正確的是：

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

B.循環(huán)展開得越多越徹底，程序的性能越好

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

D.現(xiàn)代主流C/C++編譯器可以對簡單的小函數(shù)進行自動Iinline

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

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

if( y==0) return 0;

else return gcd (y, x%y);

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

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

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

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

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

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

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

2.替換任意字符

3.刪除任意字符

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

——

以下是我根據(jù)各種來源總結(jié)的參考答案：

1.1 A

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

100M以太網(wǎng)的速率就是100Mbps;

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

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

1.2 D

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