谷歌筆試真題一：

選擇題：

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

A.忘了

B. 32位的機(jī)器上，8位加法比 32位加法更快

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

D.一般來(lái)講，整數(shù)除法比乘法更加費(fèi)時(shí)間

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

A. HTTP

B. FTP

C. IP

D. TCP

3.給一段代碼，問(wèn)正確的是：

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

數(shù)組 a[20M]

A.動(dòng)態(tài)申請(qǐng)效率會(huì)比較高

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

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

4. 28.5625的 4進(jìn)制表示

A.121.XX

B.XXXX

C121.XX

D130.21

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

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

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

C.垃圾回收機(jī)制能夠讓程序員更方便地寫(xiě)代碼

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

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

A. MD5

B. RSA

C. RC4

D. DES

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

排列數(shù)是多少?

A. 8!

B.好大一個(gè)數(shù)

C. 840

D. 780

E. 69

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

A 11 b 12 C 13 D 14 E 15

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

A0 B1 C2 D3 E4

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

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

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

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

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

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

三道大題：

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

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

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

谷歌筆試真題二：

以下是2011年google中國(guó)筆試題，共有10道選擇題，3道大題。大家也來(lái)練一練，看看自己能做對(duì)多少題。

選擇題

1、考的是正則表達(dá)式，什么字符串匹配，沒(méi)看過(guò)。2、在 Intel 8086中，加減乘除那個(gè)

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

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

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

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

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

7、房?jī)r(jià) 200萬(wàn)，每年以 10%的速度遞增，工程師為 40萬(wàn)年薪，問(wèn)什么時(shí)候買(mǎi)得起房。

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

9、TLB和 Cache的區(qū)別，這個(gè)題不會(huì)，沒(méi)聽(tīng)說(shuō)過(guò) TLB。

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

編程題

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

2、有 2^K隊(duì)伍比賽，按照 order給出一個(gè)比賽順序的排列，order表示編號(hào)為 i的

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

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

谷歌筆試真題三：

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é)議哪個(gè)正確?

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

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

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

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

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

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

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

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

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

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

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、無(wú)法確定

D、x y z同為正數(shù)時(shí)為真

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

A、26%

B、28%

C、30%

D、32%

1.6假設(shè)我們用 d=(a1,a2,….a5)表示無(wú)向無(wú)環(huán)圖 G的 5個(gè)頂點(diǎn)的度數(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和隊(duì)列 Q的初始狀態(tài)為空，元素 e1，e2，e3，e4，e5，e6一次壓入棧 S,一個(gè)元素出棧后即進(jìn)入隊(duì)列 Q，若出隊(duì)列的順序?yàn)?e2,e4,e3,e6,e5,e1則棧 S的容量要求最小值為?()

A、2

B、3

C、4

D、5

1.8在堆排序算法中我們用一個(gè)數(shù)組 A來(lái)模擬二叉樹(shù) T，如果該 A[0]存放的是 T的根節(jié)點(diǎn)，那么 A[K](K>0)的父親節(jié)點(diǎn)是?()

A、(K-1)/2

B、K/2

C、(K+1)/2

D、都不對(duì)

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

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

A、1

B、2

C、3

D、4

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

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

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

C、用戶管理模塊

D、進(jìn)程管理模塊

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

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

(2)設(shè)計(jì)測(cè)試數(shù)據(jù)來(lái)驗(yàn)證函數(shù)程序在各種輸入下的正確性。

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

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

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

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

1.考的是正則表達(dá)式，什么字符串匹配，沒(méi)看過(guò)。

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

3.看程序，寫(xiě)算法，考察的是 unsigned short 類型的范圍。程序有點(diǎn)長(zhǎng)，變量名還相似，想不起來(lái)了，

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

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

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

7.房?jī)r(jià) 200 萬(wàn)，每年以 10%的速度遞增，工程師為 40 萬(wàn)年薪，問(wèn)什么時(shí)候買(mǎi)得起房。

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

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

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

大題

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

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

三、KOF 里連招，簡(jiǎn)化為 ABCD……Z 求最長(zhǎng)連招……記不清了，見(jiàn)諒，XDJM補(bǔ)充。

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

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

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

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

1、單項(xiàng)選擇題

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

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

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

3.使用一輛卡車(chē)?yán)?000塊單塊1TB裝滿數(shù)據(jù)的硬盤(pán)，以100km/h的速度從上海到天津(100km)一趟所等價(jià)的數(shù)據(jù)傳輸帶寬

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

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

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

1.2 對(duì)以下程序，正確的輸出結(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.程序可以正確編譯連接，但是運(yùn)行時(shí)會(huì)崩潰

D.程序語(yǔ)法錯(cuò)誤，編譯不成功

1.3 在區(qū)間[-2, 2]里任取兩個(gè)實(shí)數(shù)，它們的和>1的概率是：

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

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

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

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

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

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

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 下面哪種機(jī)制可以用來(lái)進(jìn)行進(jìn)程間通信?

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

1.9 下列關(guān)于編程優(yōu)化的說(shuō)法正確的是：

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

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

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

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

1.10 一下程序是用來(lái)計(jì)算兩個(gè)非負(fù)數(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中最大的那個(gè)數(shù)的長(zhǎng)度為n，基本運(yùn)算時(shí)間復(fù)雜度為O(1)，那么該程序的時(shí)間復(fù)雜度為：

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

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

2.1 寫(xiě)函數(shù)，輸出前N個(gè)素?cái)?shù)。不需要考慮整數(shù)溢出問(wèn)題，也不需要使用大數(shù)處理算法。

2.2 長(zhǎng)度為n的數(shù)組亂序存放著0至n-1. 現(xiàn)在只能進(jìn)行0與其他數(shù)的swap，請(qǐng)?jiān)O(shè)計(jì)并實(shí)現(xiàn)排序。

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

1.在給定位置插入一個(gè)字符

2.替換任意字符

3.刪除任意字符

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

——

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

1.1 A

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

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

卡車(chē)?yán)�硬盤(pán)，1000x1000x8/3600=2222Mbps，這個(gè)應(yīng)該是最快的;

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

1.2 D

這道題大家走出考場(chǎng)后爭(zhēng)議非常大。