Google 筆試題

1、Google筆試是沒有門檻的。這樣說是因為Google根本沒有限制筆試的人數，開了N個教室，讓N多人參加不過筆試本身卻有門檻，看了題目就知道。 本來想上午寫寫的，但是，嗯，出于攢人品的目的，還是等到現(xiàn)在才寫現(xiàn)在，面試通知已經發(fā)過，很顯然我又被無視了OK，那也不錯，我也沒怎么準備這些東西呢，倒不是說我不重視，而是事情太多唔，多少算是一種經驗了?；貋碚f說昨天的筆試。題目的量并不大，除了幾個單選題，剩下就是三個編程或算法題。單選就不說了，考得比較基礎，涉及C語言常識、數據結構、文法、操作系統(tǒng)，主要說說大題。大題雖然題型不一，但都有一個重要特點：考遞歸。精確點說，我每一題都用到了遞歸。第一個的題目（嗯

2、，記的不是很完整）：在一棵（排序？）二叉樹中搜索指定值，數據結構定義為（唉唉，數據結構的具體名字都不記得了，my god）：struct Node    Node * lnext;    Node * rnext;    int value;函數定義為（情況同上，啥都記不清了）：Node * search(Node * root, int value)實現(xiàn)這個search函數。用遞歸，經典的樹的遍歷，pass先。第二個的題目：計算Tribonaci隊列（嗯，九成九記錯了那個單詞），規(guī)則是T(n) = T(

3、n - 1) + T(n - 2) + T(n -3)，其中T(0) = T(1) = 1，T(2) = 2。函數定義：int Tribonaci(int n) 備注，不考慮證整數溢出，盡可能優(yōu)化算法。這一題我一看就知道要考什么，很顯然的遞歸定義，但也是很顯然的，這里所謂的優(yōu)化是指不要重復計算。簡單的說，在計算T(n)的時候要用到T(n - 1)、T(n - 2)和T(n - 3)的結果，在計算T(n - 1)的時候也要用到T(n - 2)和T(n - 3)的結果，所以在各項計算的時候必須把以前計算的結果記錄下來，去掉重復計算。這里用到的一點小技巧就是要新寫一個函數用來做這種事情，嗯，看看我寫

4、的代碼吧！/*  Get the value of T(n - 1), and retrieve the result of  T(n - 2) and T(n - 3).  paramin n The n in T(n).  paramout mid Value of T(n - 2).  paramout right Value of T(n - 3).  return Value of T(n - 1). */int find_trib(int n, int & mid, int & right)

5、60;   if (3 = n)            mid = 1;        right = 1;        return 2;        else          &#

6、160; int temp;        mid = find_trib(n - 1, right, temp);        return mid + right + temp;    /*  Find value of T(n).  paramin The n in T(n).  return Value of T(n).  note T(n) = T(n - 1) + T(n

7、- 2) + T(n - 3) (n > 2)        T(0) = T(1) = 1, T(2) = 2. */int tribonaci(int n)    if (n < 0)            / Undefined feature.        return 0;  

8、;      if (0 = n | 1 = n)            return 1;        if (2 = n)            return 2;        int mid, right;  

9、  int left = find_trib(n, mid, right);    return left + mid + right;啊啊，對了，答卷的時候我可沒心情寫注釋剛才到VC.Net 2003上測試了一下，貌似沒有啥問題。唉，看來我多少還是懂一點算法的第三個的題目：在一個無向圖中，尋找是否有一條距離為K的路徑，描述算法即可，不用實現(xiàn)，分析算法的時間和空間復雜度，盡量優(yōu)化算法。OK，這個就是傳說中的軟肋了我也就不把自己的答案寫出來了（丟人?。m然后來仔細想想，我那個挫挫的方法也能夠用只是效率That's all.粗體文字 取自"

10、;這都已經是昨天的事啦。之所以起這個標題是想有朝一日本博的文章也會被搜索引擎搜到，然后訪問量就是指數級增長，有沒有可能啊。 話說某歌和某度居然在某一天的同一個時間搞宣講筆試，只不過一個在就業(yè)中心，一個在科學館，在我XJTU的廣袤土地上東西對峙，真是讓人不記住魚和熊掌的故事都難。Google的筆試時間一個月前就確定了，baidu一個周之前才得到消息，所以俺有理由認為，這是百度要問鼎中原的意思啦。夠豪邁呀，就不怕人都去了google冷場么？看來百度還是很自信的，贊一個，況且百度的中文搜索做得不比google差。俺堅決支持民族自己的搜索引擎，雖然事實上俺是去了google 筆試。此事不怪俺，想想科學

11、館那昏暗的燈光吧，俺覺得，非常及其適合你在臺下看著你偶像的臉搞個人崇拜 今天聽說昨晚百度非常人性化，每人一瓶礦泉水，一塊巧克力蛋糕，后來因為天熱還每人發(fā)了紙巾擦汗，這下俺虧大了嘿嘿。 俺本來發(fā)文的目的是說下筆試題，想想還是不說了，想知道的可以私下跟俺討論，題目不難，全做對也不容易，不過錯個兩三道基本也就kaka了。考察得很全面，算法數據結構操作系統(tǒng)編譯原理網絡離散數學，還居然考了個中斷。 筆試之前的宣講會，略有收獲。獲知Google全球共有員工12000左右，其中總部8000左右，而google中國，北京195，上海45，臺北35，而在一年前這一數字分別是北京100，上海20（這個沒記準確），

12、臺北10。我得到的唯一結論：google中國還差的遠啊，不知道開復能把它做成什么樣子，應該不會撤攤子吧。 這是第二次筆試，作個記錄，以備日后參考，題目另行記錄。1、 兩個二進制數的異或結果 2、 遞歸函數最終會結束，那么這個函數一定（不定項選擇）： 1. 使用了局部變量 2. 有一個分支不調用自身3. 使用了全局變量或者使用了一個或多個參數3、以下函數的結果？int cal(int x)if(x=0)return 0;elsereturn x+cal(x-1);4、 以下程序的結果？ void foo(int*a, int* b)*a = *a+*b;*b = *a-*b;*a = *a-*b

13、;void main()int a=1, b=2, c=3;foo(&a,&b);foo(&b,&c);foo(&c,&a);printf("%d, %d, %d", a,b,c); 5、下面哪項不是鏈表優(yōu)于數組的特點？ 1. 方便刪除 2. 方便插入 3. 長度可變 4. 存儲空間小 6、T(n) = 25T(n/5)+n2的時間復雜度？ 7、n個頂點，m條邊的全連通圖，至少去掉幾條邊才能構成一棵樹？ 8、正則表達式(01|10|1001|0110)*與下列哪個表達式一樣？ 1.(0|1)* 2.(01|01)* 3.(01

14、|10)* 4.(11|01)* 5.(01|1)* 9、如何減少換頁錯誤？ 1. 進程傾向于占用CPU 2. 訪問局部性（locality of reference）滿足進程要求3. 進程傾向于占用I/O 4.使用基于最短剩余時間（shortest remaining time）的調度機制 5. 減少頁大小10、實現(xiàn)兩個N*N矩陣的乘法，矩陣由一維數組表示 11、找到單向鏈表中間那個元素，如果有兩個則取前面一個 12、長度為n的整數數組，找出其中任意(n-1)個乘積最大的那一組，只能用乘法，不可以用除法。要求對算法的時間復雜度和空間復雜度作出分析，不要求寫程序。 取自"早晨看SIN

15、A新聞，看到Google品牌價值已經達到664.34億美元，躍居世界第一位?；貞涀蛲砼闩笥褏⒓觛oogle在北大的招聘會，想和朋友們分享一些特別的感受。總體感覺這是一個無限富有，充滿驚喜的公司。</div> 05年9月google開始在北京設立公司，目前已經發(fā)展到100名員工。每個工程師將新配2臺30inch的液晶顯示器。經常到美國，澳洲，韓國，日本，印度等國家TRAVEL，ENJOY great food and drink(喜歡吃喝玩樂)，在中國有兩名外籍人士，統(tǒng)統(tǒng)講流利的普通話。其中美國人eric帶領的PSO（商務合作工程部）部門，9個人，穿著京劇戲服上班，他扮演孫悟空，開玩

16、笑說穿這些工作服上班還是要花些時間的。主要筆試考題如下，其他題目是基礎題，就不貼出了：1、假設在n進制下，下面的等式成立，n值是（）567*456=150216a、 9 b、 10 c、 12 d、 182、文法G:S->uvSvu|w所識別的語言是：（）a、uvw*vu b、（uvwvu）* c、uv(uv)*wvu(vu)* d、(uv)*w(vu)*3、如下程序段輸出是：（）char str10="Hello","Google"char *p=str0;count<<strlen(p+10);a、0 b、5 c、6 d、104、c

17、nt=0while(x!=1)cnt=cnt+1;if(x&1=0)x=x/2;elsex=3*x+1;count<<cnt<<end1;當n=11時，輸出：（）a、12 b、13 c、14 d、155、寫一段程序判斷一個有向圖G中節(jié)點w是否從節(jié)點v可達。（如果G中存在一條從v至w的路徑就說節(jié)點w是從v可達的）。以下算法是用C+寫成的，在bool Reachable函數中，你可以寫出自己的算法。class Graphpublic:int NumberOfNodes();/返回節(jié)點的總數bool HasEdge(int u,int v);/u,v是節(jié)點個數，從零開

18、始依次遞增，當有一條從u到v的邊時，返回true；bool Reachable(Graph&G, int v, int w)/請寫入你的算法6、給定一棵所有邊的長度均為整數的樹，現(xiàn)要求延長其中某些邊，使得從根到任意節(jié)點的路徑長度相等。問滿足要求的樹的邊長度之和最小是多少?請寫出你的算法，并分析時間復雜度。歡迎回復，給出你的解答。取自"從沒有找工作經歷的我今天參加了Google的筆試，本來還自我感覺良好呢，誰知道考題那是嗷嗷不會啊。 考的幾乎都是算法，指針特別的多，不過時間太久不用了都忘記了，數據結構的也不少，考了隊列，還有一些編譯原理的題，關于表達式的； 三道大題第一個還蠻簡

19、單，是向雙向列表插入一個節(jié)點，第二個問題比較惡心，判斷A字符串中的各個字符數目是否不大于B字符串中的各個字符數目，由于沒時間了就沒寫完，第三題更是相當及其以及特別的惡心，找到整數數組中滿足A*B=C的元素，而且要更優(yōu)的，算了半天的時間復雜度還是沒寫出來。 還是忙該忙的事吧，眼看期末考試了，不能掛課，加油！ 取自"1、有兩根不均勻分布的香，香燒完的時間是一個小時，你能用什么方法來確定一段15分鐘的時間？ 答：2根香同時點燃，第一根兩頭都點燃，第二根只點一頭， 第一根點完的時候是半個小時，接著把第二根兩頭都點燃，第二根點完的時候就是15分鐘。 、一個經理有三個女兒，三個女兒的年齡加起來等

20、于13，三個女兒的年齡乘起來等于經理自己的年齡，有一個下屬已知道經理的年齡，但仍不能確定經理三個女兒的年齡，這時經理說只有一個女兒的頭發(fā)是黑的，然后這個下屬就知道了經理三個女兒的年齡。請問三個女兒的年齡分別是多少？為什么？ 答：2，2，9， 1歲不可能 3、有三個人去住旅館，住三間房，每一間房$10元，于是他們一共付給老板$30，第二天，老板覺得三間房只需要$25元就夠了于是叫小弟退回$5給三位客人，誰知小弟貪心,只退回每人$1，自己偷偷拿了$2，這樣一來便等于那三位客人每人各花了九元，于是三個人一共花了$27，再加上小弟獨吞了不$2，總共是$29?？墒钱敵跛麄內齻€人一共付出$30那么還有$1

21、呢？ 答：沒錯，三個人付了27塊，老板拿了25塊，小弟拿了2塊 、有兩位盲人，他們都各自買了兩對黑襪和兩對白襪，八對襪了的布質、大小完全相同，而每對襪了都有一張商標紙連著。兩位盲人不小心將八對襪了混在一起。 他們每人怎樣才能取回黑襪和白襪各兩對呢？ 答：不知道，還要仔細想想 、有一輛火車以每小時15公里的速度離開洛杉磯直奔紐約，另一輛火車以每小時20公里的速度從紐約開往洛杉磯。如果有一只鳥，以30公里每小時的速度和兩輛火車同時啟動，從洛杉磯出發(fā)，碰到另一輛車后返回，依次在兩輛火車來回飛行，直到兩輛火車相遇，請問，這只小鳥飛行了多長距離？ 答：記好兩車相遇時間，就是鳥飛行時間，乘以其飛行速度就得

22、到飛行距離。 、你有兩個罐子，50個紅色彈球，50個藍色彈球，隨機選出一個罐子，隨機選取出一個彈球放入罐子，怎么給紅色彈球最大的選中機會？在你的計劃中，得到紅球的準確幾率是多少？ 答：不知道，還要仔細想想 、你有四個裝藥丸的罐子，每個藥丸都有一定的重量，被污染的藥丸是沒被污染的重量1.只稱量一次，如何判斷哪個罐子的藥被污染了？ 答：不知道，還要仔細想想 、你有一桶果凍，其中有黃色，綠色，紅色三種，閉上眼睛，抓取兩個同種顏色的果凍。抓取多少個就可以確定你肯定有兩個同一顏色的果凍？ 答：4 、對一批編號為1100，全部開關朝上(開)的燈進行以下*作：凡是1的倍數反方向撥一次開關；2的倍數反方向又撥

23、一次開關；3的倍數反方向又撥一次開關問：最后為關熄狀態(tài)的燈的編號。 答：不知道，還要仔細想想 、想象你在鏡子前，請問，為什么鏡子中的影像可以顛倒左右，卻不能顛倒上下？ 答：人的眼睛是左右對稱的 、一群人開舞會，每人頭上都戴著一頂帽子。帽子只有黑白兩種，黑的至少有一頂。每個人都能看到其它人帽子的顏色，卻看不到自己的。主持人先讓大家看看別人頭上戴的是什幺帽子，然后關燈，如果有人認為自己戴的是黑帽子，就打自己一個耳光。第一次關燈，沒有聲音。于是再開燈，大家再看一遍，關燈時仍然鴉雀無聲。一直到第三次關燈，才有劈劈啪啪打耳光的聲音響起。問有多少人戴著黑帽子？ 答：3 取自"1 超級失敗的1：說

24、8點開始，考試時間100分鐘 ，怎么算都是9：10交卷；9點一到匆匆交卷了，晚上躺床上才發(fā)現(xiàn)錯也； 2 超級失敗的2：把自個的生日又記錯了； 3 怕怕的發(fā)現(xiàn)：發(fā)現(xiàn)mm還是超級可怕滴，眼睜睜看著一個騙局，哎，也得謹慎些以防上當受騙??； 題目如下： T( 0 ) = 1  T(1)=1;T(2)=2;T(n)=T(n-1)+T(n-2)+T(n-3); 用最優(yōu)方式求T(n)  int?T(int?n)? 可以用最熟悉的語言寫 在考場的第一個做法 ?1 public ? class ?T? ?2  ? public ? int ?

25、t( int ?n) ?3  ? if ?(n? = ? 0 )? ?4 ? return ? 1 ?5  ? ? else ? if ?(n? = ? 1 )? ?6 ? return ? 1 ?7  ? ? else ? if ?(n? = ? 2 )? ?8 ? return ? 2 ?9  ? ? else ? 10 ?

26、 return ?t(n - 1 )? + ?t(n - 2 )? + ?t(n - 3 );11 ? ?12 ? 13 當時發(fā)現(xiàn)時間夠用，進行了公式推理，但未得出規(guī)律的真諦每個都與T(3)可以直接發(fā)生關系，關系是2的冪次方，但最終沒有得出公式遂改進如下：?1 public ? class ?T? ?2  ? public ? int ?t( int ?n) ?3  ? if ?(n? = ? 0 )? ?4 ? return 

27、;? 1 ?5  ? ? else ? if ?(n? = ? 1 )? ?6 ? return ? 1 ?7  ? ? else ? if ?(n? = ? 2 )? ?8 ? return ? 2 ?9  ? ? else ? 10 ? return ? 2 ? * ?t(n - 1 )? - ?t(n - 3 );11 ? 

28、;?12 ? 13 晚上躺床上，怎么可能這樣直接呢？突然想到最起碼的一點就是重復數的計算，應該進行保存；如果正向逐個求然后保存，可行；如果倒向如何保存，尚未想好大家來仁者見仁一下哦（有更好的思路的請指點）public class T ?Map values = new HashMap();?public int t(int n)?int result = 0;?if (n = 0) ? result = 1;? else if (n = 1) ?result = 1;? else if (n = 2) ?result = 2;? else ?result =? 2 * t(n-1)

29、- t(n-3);? ?return result;?取自"、一、單選 1、80x86中，十進制數-3用16位二進制數表示為？ 2、假定符號-、*、$分別代表減法、乘法和指數運算，且 1)三個運算符優(yōu)先級順序是：-最高，*其次，$最低； 2)運算符運算時為左結合。請計算3-2*4$1*2$3的值： (A)4096，(B)-61，(C)64，(D)-80，(E)512 3、下列偽代碼中，參數是引用傳遞，結果是？ calc(double p, double q, double r)q=q-1.0;r=r+pmain()double a = 2.5, b = 9.0;calc(b-a, a

30、, a);print(a);(A)1.5 (B)2.5 (C)10.5 (D)8 (E)6.5 4、求輸出結果： int foo(int x, int y)if(x <=0 | y <= 0) return 1;return 3 * foo(x - 1, y / 2);printf("%dn", foo(3, 5);(A)81 (B)27 (C)9 (D)3 (E)1 5、下列哪個數據結構在優(yōu)先隊列中被最廣泛使用？ (A)堆 (B)數組 (C)雙向鏈表 (D)圖 (E)向量 6、以下算法描述了一個在n國元素的雙向鏈表中找到第k個元素的方法（k >= 1且k

31、 <= n）： 如果k <= n - k，從鏈表開始往前進k-1個元素。 否則，從終點出發(fā)，往回走n - k個元素。 這個算法的時間代價是？ (A)(nlogn) (B)(maxk, n - k) (C)(k + (n - k) (D)(maxk, k - n) (E)(mink, n - k) 7、有一個由10個頂點組成的圖，每個頂點有6個度，那么這個圖有幾條邊？ (A)60 (B)30 (C)20 (D)80 (E)90 8、正則表達式L = x*(x|yx+)。下列哪個字符串不符合L (A)x (B)xyxyx (C)xyx (D)yxx (E)yx 9、為讀取一塊數據而準備

32、磁盤驅動器的總時間包括 (A)等待時間 (B)尋道時間 (C)傳輸時間 (D)等待時間加尋道時間 (E)等待時間加尋道時間加傳輸時間 二、算法 1、打印出一個二叉樹的內容。 2、在一個字符串中找到第一個只出現(xiàn)一次的字符。如abaccdeff，輸出b。 3、給定一個長度為N的整數數組（元素有正有負），求所有元素之和，最大的一個子數組。分析算法時空復雜度。不必寫代碼。 附上動態(tài)規(guī)劃做法的答案: 最大子序列 問題： 給定一整數序列A1， A2，. An （可能有負數），求A1An的一個子序列AiAj，使得Ai到Aj的和最大 例如：整數序列-2, 11, -4, 13, -5, 2, -5, -3,

33、12, -9的最大子序列的和為21。對于這個問題，最簡單也是最容易想到的那就是窮舉所有子序列的方法。利用三重循環(huán)，依次求出所有子序列的和然后取最大的那個。當然算法復雜度會達到O(n3)。顯然這種方法不是最優(yōu)的，下面給出一個算法復雜度為O(n)的線性算法實現(xiàn)，算法的來源于Programming Pearls一書。在給出線性算法之前，先來看一個對窮舉算法進行優(yōu)化的算法，它的算法復雜度為O(n2)。其實這個算法只是對對窮舉算法稍微做了一些修改：其實子序列的和我們并不需要每次都重新計算一遍。假設Sum(i, j)是Ai . Aj的和，那么Sum(i, j+1) = Sum(i, j) + Aj+1。利用這一個遞推，我們就可以得到下面這個算法： int max_sub(int a,int size)int i,j,v,max=a0;for(i=0;i<size;i+)v=0;for(j=i;j<size;j+)v=v+aj;/Sum(i, j+1) = S