google筆試題收集

1. 異或
1^1=0
0^0=0
1^0=1
0^1=1

2. 斐波那契數列(Fibonacci)

3.存儲空間上不具有優勢

4. 由“主定理”
T(n)=25T(n/5) + n²

a=25  b=5   f(n)=n²
log_ba=2

將n^log_ba與f(n)比較： 相等
則時間復雜度為O(n²logn)



1.

 

2. 

3

時間復雜度分析:
總共的操作步驟 n*{[n+(n-1)]+1}=2n²
時間復雜度為O(n2)

空間復雜度為O(1)  4*sizeof(int)


改進算法：

Google筆試集錦
Google筆試集錦
 
選擇題+三道算法題
選擇題沒什么難的  最后一道考的數據庫使用什么存儲結構不會做。。
算法題
第一題沒什么好說
第二題可破

Google筆試集錦
Google筆試集錦
 
選擇題+三道算法題
選擇題沒什么難的  最后一道考的數據庫使用什么存儲結構不會做。。
算法題
第一題沒什么好說
第二題可破壞一個數組A[0..N-1]的條件下使用最少的內存判斷是否存在相同的元素
   我的做法是堆排序  時間O(NlogN) 空間O(1) 復雜度上來看應該最優了
第三題已知每個點的父節點，求這棵樹的最大獨立集
   用遞歸求解  類似動態規劃  但是不存在重疊子狀態  經典算法問題了
   預處理每個節點的子節點存在一張表里
   時間O(N）空間O(N）
大家做的結果是這樣嗎？
發信站: 飲水思源 (2006年10月11日03:06:04 星期三), 站內信件
開章明義，我是個廢人，上來積攢rp了。
在宣講會的時候，聽旁邊的師姐說上海只招兩個職位每個職位只招一個人。
現在后悔只選了北京和上海的SWE了。
不過反正……也不指望了。。。

筆試題目：9道單選+3道問答
時間：100分鐘
我做的是B卷。
單選題：
1，求兩個二進制數的異或值，基本上學過一點計算機的東西的人都能對的題目。。
2，不記得了。。也是不需要思考的題目。。
3，大概是如下的函數：
int someFunc(int x){
    if (x == 0)
        return 0;
    else
        return x + someFunc(x - 1);
}
問這個計算的是什么。。。
4，不記得了。。不需要思考吧。。
5，不記得了。。不需要思考吧。。
6，參見2，4，5。。
7，似乎需要思考一下。。
8，問鏈表結構和數組相比的優勢不包括哪項，
包括：
插入的時間
刪除的時間
存儲空間
剩下兩個不記得了。。
9，如下函數：
T(x) = 1 (x <= 1)
T(n) = 25 T(n/5) + n^2
問T(n)隨n的增長。
選項大概是這樣的：
O(n^2)，O(n^2logn)等等的。。
問答：
1，寫兩個N*N的矩陣的乘法，給出了C的格式，你可以選擇你喜歡的語言去寫。。
int* multi(int* a1, int* a2, int N){
}
2，尋找一個單向鏈表的中項，如果存在兩個則返回前一個。給出了C的格式，同樣你可
以選擇。。。。
struct {
    Node* next;
    int value;
} Node;
Node* someFunc(Node* head){
}
3，給一個長度為n的整數數組，只允許用乘法不允許用除法，計算任意(n-1)個數的組合
乘積中最大的一組。。。寫出算法的時空復雜度。
ps：懷疑這道題目出錯啦。。雖然我也做錯了。。。。。。
一些補充：
1，問答的第一題是google上學期 intern的大題原題；
2，google很喜歡考鏈表，無論intern的面試以及兩次的筆試都有這樣的題目；
3，google一般大題第三道都是寫算法的時空復雜度；
4，選擇題基本上偏簡單，但是要做得準確率高似乎并不那么容易；
5，根據傳言，小道消息，人云亦云以及以訛傳訛，google的高速審卷政策來源于審卷時
以選擇題為主，如果你全對啦，那么恭喜你pass啦；如果你錯了好幾道，那么下次努力
吧，如果還有下次。。。大題基本是做參考的。。。
6，選擇題很多記不清了，因為一遍做下來的，回去隨便掃了兩眼。。。加上過了這幾個
小時，記不得了。希望大家補充修正以及修改。。。
7，google會在11號開始3天內發面試通知，據小道消息等等，有四輪面試。bless大家~~
 
 
輸入a_1,   a_2,   ...,   a_n,   b_1,   b_2,   ...,   b_n，如何在O(n)的時間，用O(1)的空間，
將這個序列順序改為a_1,   b_1,   ...,   a_n,   b_n。
這個問題在瀚海星云上跟出了好幾十的跟帖，看看大家有沒有什么好的解法！！！
 

晚上是google的校園宣講會
先前并沒有投簡歷，但是還是奔了去
google的hrjj看起來仿佛沒有ibm的那么動人，但卻很親切
五點半左右開始，開始前那個hrjj放了些google員工自己拍的mv，
比較有意思
之后是一個做技術的男生如數家珍的介紹google做的東西
之所以稱為“男生”主要感覺他很學生氣。。。講話并沒有那些很商業的調度氣氛的東西
很理想主義，呵呵，雖然聽的很多人打瞌睡
他總是說google是個很理想主義的公司，雖然為了生存不得不做一些商業化的事情，但是，google做很多事情都是因為認為覺得有做的價值并且要做好，所以有了googleprint,googleearth,等等
不過，google仿佛是一個需要聰明人的公司，接下來的筆試應證了這一點
內容很少，甚至簡單，選擇題可能是送分的，大概10來道，并不難，算些東西，還有一點點程序方面的基礎概念，后面是三個算法設計題。
第一個，深拷貝一個二叉樹。我不明白這道題的動機是什么，我最后很搓得用了遞歸，雖然明知道這樣很耗，可是實在想不起來非遞歸算法怎么個寫法了。
第二個，把輸入數組隨機分配到一個新的數組上，每個數都完全對應一個隨機的位置，當然，隨即產生函數是提供了的。這個題我想了很久，沖突的時候怎么辦？散列？但是那樣還是隨機的嗎？
第三個，很ft。居然是C語言的一個作業題。N個人排成圈，從第一個人開始，去掉，隔一個人，去掉下一個，以此類推，要求出最后出局的那個人的位置。并且，要求分析算法的時間、空間復雜度。我感覺這個題表面簡單，實際對算法的優化要求很高。一個是空間復雜度，一個是時間復雜度，只是不知道做到什么程度算是極好。
仿佛這種類型的考試，大家差不多都能答完，只是如何才能與眾不同卻讓人傷腦筋
回來后對google的印象變得很好，至少感覺他們真的是需要人，而不是一個螺絲釘。。。
 
 

昨天，參加了Google春季實習工程師的招聘筆試。這是進入大學以來參加的第一次筆試。
可以說，這次筆試也讓我更明確了我的學習方向。學習什么技能不重要，重要的是要有扎實基礎，數據結構，c++語言等，都要扎實的掌握，不可有絲毫的馬虎。于是，漸漸開始后悔了，后悔自己對基礎知識沒有學好，卻又一天到晚想著要學什么什么東西，這真是丟了西瓜撿了芝麻，一點便宜都沒有占到啊。
還記得昨天的筆試，第一題是有關位操作的，很簡單。接下來兩題是講const指針的，這便是我的一個薄弱點，以前一直都沒有學好。首先，constchar*p="abcde"，那么，p指向的內容是不可變得，即不能改變*p的值，但是，p卻是可變的，即可以這么操作：p=“12345”，或者p=newchar[10]，等等；另外，char*constp="abcde"，則表示這是一個指針常量，即p不能指向另外的地址，但是，p指向的內容是可以改變的；還有一個就是常量指針常量，constchar*constp，它是指向常量的常量指針，若初始化的時候，p指向的是一個變量，那么，不能用指針操作來改變變量的值，例如：inta=0;constint*constp=&a;*p=1;//這句或是錯誤的，但是，可以直接給變量賦值，即a=1；是可以的。
接下來幾題涉及了算法分析的一些東西，然后是涉及語法分析的正則表達式什么的，這個因為沒學過編譯，也就不太懂了。接下來是考了抖動。什么是抖動？所謂抖動，主要是由于頁面交換過于頻繁，而導致時間浪費太多的現象。特別的，在虛擬內存技術下，若工作集大小選的不合適的話，就會有頻繁的換入換出，而我們知道，硬盤的讀寫是需要花費大量時間的，這樣，就導致了某進程等待的時間比實際運行的時間多的多。
接下來的大題是編程題和算法題，前兩題都挺簡單的，第一題要求完成雙向鏈表的添加結點，第二題要求比較兩字符串的字符出現頻率；第三題是個算法題，基本意思很簡單，但是，要找到一個好的算法卻需要一定的思考能力，具體題目已經記不太清了。
總之，這次筆試，雖然說從一開始所抱的心態就是見識見識，沒有奢求什么，只是想走出這個溫暖的象牙塔，走到外面這個花花世界來看看情形。一切都需放開。走了一遭才發現，不要總往高處看，基礎扎實了，才能造起巴比倫塔。
 
 
1.寫程序判斷是否字符串A里每個字符在A中出現的次數都大于在字符串B中出現的次數。
注：此題我是對每個字符出現的次數分別統計，然后比較。重復的字符重復統計比較，所以效率很低。不知有什么好的改進方法？
2.對一個數組S，求其中滿足要求的最大元素C。要求C滿足等式C=A*B，其中A、B也是數組S中的元素。請用能想到的最優算法，分析時間和空間復雜度。（用語言描述算法，不用寫程序）
注：這個題我當時做的方法在時間上要用o(n^3)，事后想出了個o(n^2logn)的方法。不知有沒有更好的方法。
 
 
傳說中有人說：google筆試很變態，題目希奇古怪；google題目比較基礎簡單。
終于得于一見。
晚上干完活才去，到的時候已經7點左右。在二教已經沒有空余座位，無賴多等了20多分鐘才安排了一個新的教室。
發題，答卷。
整體感覺就是比較基礎，沒有什么很難的題目，除最后一題目以外。
選擇題目9個，比較基礎。
第一題，相對比較簡單，遞歸
第二題，基本是看是否對函數效率是否有概念。似乎也跟動態規劃的記錄法有點相似之處。
最后一題目回想起來實在慚愧，其實還是題目沒有怎么讀懂。嗨！
以下是科苑上，看到的解法。慚愧慚愧
第一和第二應該是不錯的選擇！
特別是第二種方法！

發信人:oasis(綠洲),信區:SISE2004702
標題:筆試最后一題想到的幾種解法
發信站:BBS科苑星空站(WedOct1803:24:342006),站內
反正也晚了，干脆再折騰一會兒。
題目：n個點組成的無向圖，對于任意給出的兩點，判斷其是否有長度為K的通路。
分析：無向圖是允許有環存在的，也允許兩點間有多條邊，長度為K是指從一個點
移動到相鄰點這樣過程的次數。比如AB兩點相鄰，那么A-B-A-B就是長度為3的通路。
解法一：直接利用圖論中的一個定理，鄰接矩陣U的K次方后所得矩陣的(i,j)元素
即為原無向圖中i,j兩點之間長度為K的通路數量。因此復雜度只需要對U^K分析。
由于U^2的時間復雜度為O(n^3)，（這里使用了傳統矩陣乘法，不過即使用strassan
方法也依然是O(n^(2+e))，其中0小技巧，不需要去依次的乘，否則的話需要K-1次矩陣乘法，可以從U^2，算出U^4，
依此類推，因此總的時間復雜度為O(n^3*lgK)。空間復雜度不細述O(n^2)。
評論一：細心的人會注意到這樣的解法其實比題目的要求要強，因為題目中只是要
求出任意給定的兩點間K通路數目，而上述做法，則是把所有的兩點組合都求出來
了。因此還應該存在著改進的算法在O(n^2)這個時間復雜度級別。
解法二：這是看水木上一個網友的解法，我重寫成下面這樣：設所給的兩點為A、B。
那么首先把A的所有相鄰點全部放入U集合中，接著對之前放入U中的點i分別求出其相
鄰點，并將它們放入U中（而原先的點i本身則從集合中事先去除）。這樣做過K次后，
看隊列中是否有B點。若有則表明存在著長度為K的通路。由于每次尋找鄰接點的次數
不超過n^2，而要進行K次，因此時間復雜度為O(n^2*K)，空間復雜度為O(n)。
評論二：和解法一相比，從n^3*lgK變為了n^2*K，也就是n*lgK與K之間的差別，若n=k
的話，也就說明后者比前者快了lgK倍。
解法三：從A到B利用深度優先遍歷，找出每一條AB間的路徑，其中沒有點重復經過。
對每一條這樣的路徑進行分析：
若長度>K，該路徑不可能滿足；
若長度=K，則已滿足；
若長度一次加一）。若無環，則看K-當前路徑長度，若該值為偶數，則可以在該路徑上的某兩
個鄰接點上來回的重復走從而滿足要求（每來回走一次加二）。其他情況，無法滿足。
由上得到算法的時間和空間復雜度均為O(n^2)，
評論三：時間復雜度很可能不是O(n^2)，因為從A到B上找出每一條AB間的簡單路徑，由
于存在著重復邊和環的情況，多半就不是簡單的深度遍歷的O(n^2)了，具體是多少我也
說不清。筆試里我用的這個方法，現在感覺挺玄。。。
 

『2006-10-17』
      今晚Google筆試，也是本人的“處女筆”，人山人海啊，開始Google技術總監宣講時，有位義憤填膺的老兄，抓住提問時間，強烈指責Google搜索不了“南京大屠殺”等“不公正”現象。唉，勇氣和愛國主義情感可嘉啊，只可惜為什么不弄清情況就跑來亂說話呢？
      筆試的人數比Google預想的多出2-3倍，題目不是很難，似乎都是計算機專業的基礎課。不過可惜，我不是計算機專業的，很多題目只是憑自己編程經驗寫的，估計希望不會太大。但是心情還不錯，因為本來就沒有抱太大希望，而且Google筆試尚且不是很難，就不必對其他公司筆試有太大心里壓力了。
      有幾道題目給出來，喜歡C的來看看：
      int main()
      {const char* p = "12345";
       const char **q = &p;
       *q = "abcde";
      const char *s = ++p;
      p = "XYZWVU";
      printf("%c\n", *++s);
     }
   求輸出結果。
---------------------------------------------
   最后一道題：
   n個節點的無向圖，判斷任意兩點之間是否有長度為K的通路。寫出算法思路，并給出你的算法的時間和空間復雜度。
--------------------------------------------
   上面一題答案“c”，因為p是指向常量的指針，但P本身可以變化；下面一題據說是離散數學教程中的經典題型，我沒有上過，只想到深度遍歷的方法。
 
google的魅力就不用詞語形容了,從晚上的人氣就可見一斑.準點趕到教七,卻發現門口已經被人群給賭了,google的工作人員一個勁地勸大家別進去了,理由是"為了安全":).也好,不用聽開復同學的嘮叨.回教三的路上,一打打的人迎面而來,熟悉的,陌生的,本校的,外校的.我彷佛到了麥加,穿梭在朝圣的人流中. 但是念佛的人多,成佛的卻是寥寥.晚上肯定有四位數的申請者,不過能有多少人登上幸運的快車呢?能突破個位數嗎?所謂千軍萬馬過獨木橋,找工作,挺殘酷!
　　于我,去參加筆試,更多是一種體驗.選擇google,權當是我對這家偉大的公司的一點敬意吧!
　　在軟件上,我這樣的水平,恐怕連菜鳥也談不上.那么硬件呢?光學呢?我的競爭力在哪里?不能不說,對于找工作,我是有所恐懼的.現在的選擇,也許不過是種逃避.
　　昨天,zhengzheng說他改變主意,準備工作了,一起走的兄弟,又少了一個.今天,simon說在猶豫是否調整申請的方向,因為他想以后還是進公司的.說起,5年的努力是否值得?未來也許只有上帝知道吧!
　　乘著腦子還清晰,先把筆試題記下:
　　9個選擇題,2個編程,1個算法.選擇題,感覺比較基礎,不知里面有沒有設地雷?反正沒啥印象了.
　　編程1,打印二叉樹,實現語言不限,先后也不限.
　　編程2,給定一個字符串數組,從中找出第一個只出現一次的字母.
　　算法題,給定一個整數數組,從中切出一個連續片段,保證其元素和最大.求最優算法,分析時間和空間復雜度. 
 

標  題: Google筆經
發信站: 飲水思源 (2006年10月11日03:06:04 星期三), 站內信件
開章明義，我是個廢人，上來積攢rp了。
在宣講會的時候，聽旁邊的師姐說上海只招兩個職位每個職位只招一個人。
現在后悔只選了北京和上海的SWE了。
不過反正……也不指望了。。。

筆試題目：9道單選+3道問答
時間：100分鐘
我做的是B卷。
單選題：
1，求兩個二進制數的異或值，基本上學過一點計算機的東西的人都能對的題目。。
2，不記得了。。也是不需要思考的題目。。
3，大概是如下的函數：
int someFunc(int x){
    if (x == 0)
        return 0;
    else
        return x + someFunc(x - 1);
}
問這個計算的是什么。。。
4，不記得了。。不需要思考吧。。
5，不記得了。。不需要思考吧。。
6，參見2，4，5。。
7，似乎需要思考一下。。
8，問鏈表結構和數組相比的優勢不包括哪項，
包括：
插入的時間
刪除的時間
存儲空間
剩下兩個不記得了。。
9，如下函數：
T(x) = 1 (x <= 1)
T(n) = 25 T(n/5) + n^2
問T(n)隨n的增長。
選項大概是這樣的：
O(n^2)，O(n^2logn)等等的。。
 
問答：
1，寫兩個N*N的矩陣的乘法，給出了C的格式，你可以選擇你喜歡的語言去寫。。
int* multi(int* a1, int* a2, int N){
}
2，尋找一個單向鏈表的中項，如果存在兩個則返回前一個。給出了C的格式，同樣你可
以選擇。。。。
struct {
    Node* next;
    int value;
} Node;
Node* someFunc(Node* head){
}
3，給一個長度為n的整數數組，只允許用乘法不允許用除法，計算任意(n-1)個數的組合
乘積中最大的一組。。。寫出算法的時空復雜度。
ps：懷疑這道題目出錯啦。。雖然我也做錯了。。。。。。
 
 
一些補充：
1，問答的第一題是google上學期 intern的大題原題；
2，google很喜歡考鏈表，無論intern的面試以及兩次的筆試都有這樣的題目；
3，google一般大題第三道都是寫算法的時空復雜度；
4，選擇題基本上偏簡單，但是要做得準確率高似乎并不那么容易；
5，根據傳言，小道消息，人云亦云以及以訛傳訛，google的高速審卷政策來源于審卷時
以選擇題為主，如果你全對啦，那么恭喜你pass啦；如果你錯了好幾道，那么下次努力
吧，如果還有下次。。。大題基本是做參考的。。。
6，選擇題很多記不清了，因為一遍做下來的，回去隨便掃了兩眼。。。加上過了這幾個
小時，記不得了。希望大家補充修正以及修改。。。
7，google會在11號開始3天內發面試通知，據小道消息等等，有四輪面試。bless大家~~
 

google brainy test/exam 就是流傳甚廣的傳說中的google 的21道 GLAT 考試了。
　　10月底，Google在美國《麻省技術評論》、《LinuxJournal》、《Mensa》、《今日物理》等幾本專業雜志上，刊登了一份"Google實驗室能力傾向測試"。
　　試卷開頭，蠱惑地寫著"試試看！把答案寄回Google，你有希望去Google總部參觀，并成為我們其中一員"。
1. Solve this cryptic equation, realizing of
course that values for M and E could be
interchanged. No leading zeros are allowed.
WWWDOT - GOOGLE = DOTCOM
2. Write a haiku describing possible methods
for predicting search traffic seasonality.
3.
1
1 1
2 1
1 2 1 1
1 1 1 2 2 1
What is the next line?
4. You are in a maze of twisty little passages,
all alike. There is a dusty laptop here with a
weak wireless connection. There are dull,
lifeless gnomes strolling about. What dost
thou do?
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 evil"
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 upon emptiness.
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 P
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.’Tis 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) 1000000000000000000000000000000000
0000000000000000000000000000000000
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.
 
 
Google慣用“整蠱題”
　　Google上一輪招聘，今年夏天剛結束。
　　用的也是一道“科學麻瓜”看不懂的“整蠱題”，而且，堂而皇之掛在硅谷各大地鐵站上。9月底，3塊15米長的米色廣告牌上，簡簡單單刷著“（在‘e’的數列中所能找到的第一個十位數質數）.com”，沒有公司名也沒有任何廣告詞。
　　花了幾秒鐘，路人才明白，這是一道數學題。自然常數e（2.718281828……）的第一個十位數質數，是目標網站的名字。
　　好奇分子忍不住用Google搜索起答案來，壓根兒不曉得這就是Google出的“硬骨頭”考題。
　　不少人后來在規定時間內，登錄上了www.7427466391.com。然而，那不是夢寐以求的終點站，Google惡作劇似的，為“高手”們在半山腰設了個休息的小涼亭。
　　www.7427466391.com里，貼出一條更令人頭疼的數學問題，答出這個問題，能得到進入下一個網頁的密碼。
　　跑完數學“馬拉松”，7500個“幸存者”走入Google實驗室網頁，成功投出簡歷。最后，Google只要了50個人。“光以廣告而論，Google也算得上高段！”
　　波士頓一家廣告公司的高級副總裁弗里茨·庫恩分析，“目標人群看到廣告后會想，‘這是我的語言，那是沖著我來的’；對其他人而言，廣告也使Google的形象大大提升。他們可能會想，‘我是得不到這份工作的了。不過，在那兒工作的人真聰明’。”
　　Google測試考的就是腦筋
　　·試著證明WWWDOT-GOOGLE=DOTCOM·用俳句（一種日本短詩，每句有一個與季節有關的詞）來描述各種模型，借此預測網絡搜索流量的季節性變化。
　　·你落入一個迷宮，回旋不斷的走廊。手里有一臺堆滿灰塵的手提電腦，可以無線上網。周圍，許多無生命的侏儒徘徊走動。這種情況下，你會如何做？
　　A)無目的地徘徊，不停走入死胡同，然后被迷宮里面的妖怪吃掉。
　　B)用手提電腦當鏟子，打穿地板直接進入游戲下一關。
　　C)玩網絡游戲《魔法奇兵》，直到電池耗盡。
　　D)利用計算機，找到迷宮的節點，發現準確出路。
　　E)把你的簡歷寄給Google，告訴迷宮里領頭的妖怪，你要退出游戲。然后，發現你回到了現實世界。
　　·Unix有什么問題？你會如何補救它？
　　·你在Google工作的第一天，發現你同寢室的室友，曾寫過一本書。你研究生一年級時，這本書是你最重要的參考資料。你會：A)求他幫你簽個名。B)不改坐姿，卻放輕打字聲音，盡量避免影響他。
　　C)把你每天吃的麥片和咖啡，留給他吃。
　　D)引用他那本書中間，你最喜歡的程式，告訴他這則方程給了你多少啟發。
　　E)讓他看看，你可以用不到34句語句，完成一個高難度程序。
　　·以下哪個最好地表達了Google的企業文化？
　　A)“我感覺挺幸運”
　　B)“別干壞事”
　　C)“哦，我已經完成了任務”
　　D)“你身邊10米以內，必定能找到食物”
　　E)以上皆是·用1歐姆的電阻，組成無限大的放行點陣，問“象棋跳馬步”（“日”字對角點）兩點之間的電阻是多少？
　　·下午2點，舊金山著名的灣區。你可以選擇去陽光海岸、國家公園的紅杉林里徒步旅行，或者參觀城市
里的文化景觀。你會怎么做？
　　·搜索技術的下一個革命性突破是什么？
　　·一個技術研究小組的最優化人員組合是幾個人？一旦超過這個數字，每增加一個研究員，平均生產力就會相應下降：A)1B)3C)5D)11E)24·三角形ABC，用圓規和尺，找出點P，保證三角形ABP、ACP和BCP周長相等。
　　·你寫過最酷的程序是什么？
　　·找出此數列的下一個:10,9,60,90,70,66?A)96B)10的100次方C)A或者BD)以上皆否·用少于29個詞，描述你能帶給Google實驗室的貢獻。
 
 
今年10月底，Google在美國《麻省技術評論》、《LinuxJournal》、《Mensa
》、《今日物理》等幾本專業雜志上刊登了一份“Google實驗室能力傾向測試”的
試卷，開頭蠱惑地寫著“試試看！把答案寄回Google，你有希望去Google總部參觀
，并成為我們其中一員”。有興趣的人可以做完了郵寄給Google公司，也許會得到
一個工作機會呢。
　　1、解答下面的隱藏等式，其中的M和E的值可以互換，但不允許第一位是0：
　　WWWDOT - GOOGLE = DOTCOM
　　2、用一個俳句(一種日本短詩，每句有一個與季節有關的詞)來建立模型，借
此預測網絡搜索流量的季節性變化；
　　3、
　　1
　　1 1
　　2 1
　　1 2 1 1
　　1 1 1 2 2 1
　　下一行是什么？
　　4、你正處于一個全部由崎嶇小路構成的迷宮里，手里有一個滿是灰塵的筆記
本，可以無線上網，但是信號很弱。與此同時，一些陰森可怕、毫無生氣的妖怪在
你身邊游蕩。你會怎么做呢？
　　(1)毫無目的的四處游蕩，到處碰壁，直到被迷宮里的妖怪吃掉。
　　(2)用筆記本作為挖掘工具，打穿地面直接進入下一關。
　　(3)玩網絡游戲《魔法騎兵》，直至電池耗盡，你也心灰意冷。
　　(4)使用筆記本畫出迷宮的節點地圖，找到出路。
　　(5)發送簡歷給Google，告訴主管妖怪你選擇退出，隨后你就回到現實世界。
　　5、Unix有何缺陷？你準備如何補救？
　　6、在Google工作的第一天，你發現身邊的同事竟然是研究生一年級課本的作
者，你會：
　　(1)主動示好并索取簽名。
　　(2)不改變坐姿，但放輕打字聲音，避免影響她的工作和思考。
　　(3)把你每天的麥片和咖啡都留給她享用。
　　(4)在她所寫的書中找到你最喜歡的內容，并告訴她這些內容已經成為你的座
右銘。
　　7、下列哪句話最貼切的表達了Google的企業文化？
　　(1)我感到很幸運。
　　(2)不要干壞事。
　　(3)哦，我已經解決了那個問題。
　　(4)你身邊50英寸之內，必定能找到食物。
　　(5)以上皆是。
　　8、用3種顏色為20面體上色，每個面一種顏色，有多少種組合？你會選擇哪些
顏色？
　　9、下面是故意留出的空白，請將其填滿，使之看起來不那么空。
　　10、用1歐姆的電阻組成無限大的兩維矩陣，“象棋跳馬步”(“日”字對角點
)兩點之間的電阻是多少？
　　11、現在是星期日下午2點，你正在舊金山著名的灣區。你可以選擇去國家公
園的紅杉林里徒步旅行，或者參觀城市里的文化景觀。你會怎么做？
　　12、你認為最美的數學等式是什么？
　　13、下列哪個團體沒有在Google員工中形成？
　　(1)女子籃球
　　(2)淡黃色愛好者
　　(3)Cricketeers
　　(4)諾貝爾獎獲得者
　　(5)葡萄酒俱樂部
　　14、搜索技術的下一個革命性突破是什么？
　　15、一個項目組由多少人構成才能達到最優規模？也就是說，一旦超過這一數
字，每增加一個成員項目組的平均生產力就會相應下降。
　　(1)1個
　　(2)3個
　　(3)5個
　　(4)11個
　　(5)24個
　　16、給你一個三角形ABC，請用圓規和尺找出點P，保證三角形ABP、ACP和BCP
周長相等。
　　17、有這樣一個函數，對于任意整數n，都能返回寫出0到n之間出現“1”的個
數。例如，f（13）=6。請注意f（1）=1，那么下一個能實現f（n）=n的最大數字
是什么？
　　18、你編寫的最酷的黑客程序是什么？
　　19、在下面的數列中，下一個數字是多少：10, 9, 60, 90, 70, 66,?
　　(1)96
　　(2)10的100次方
　　(3)以上皆是
　　(4)以上皆不是
　　20、用少于29個詞，描述你能帶給Google實驗室帶來的貢獻。(天外)
--
“微軟是個公平的公司，這里幾乎沒有特權。蓋茨只是這兩年才有了自己的一個停車位。
以前他來晚了沒地兒，就得自己到處去找停車位。”
“微軟非常強調員工的動手能力。在做新產品發布時，蓋茨都能自己動手做演示。他總
是在和工程師作搭檔，對自己的產品很熟悉，這樣，任何人都糊弄不了他。”
 

1.單項選擇題
1.  下面一段代碼的輸出是[  ]
void fn( int* b){
    (*b)++;
}
int main(){
    int a=7;
    fn(&a);
cout<<a;
return 0;
}
A.0     B.7    C.8    D.undefined
2.  定義int i,j,*p=&i; 那么下面哪條語句可以完成i=j的賦值[  ]
A.i=*p;     B. *p=*&j;    C.i=&j;    D.I=**p;
3.  用二叉搜索樹和哈希表存儲相同的數據集,對于以下何種操作,二叉搜索樹比哈希表

速度更快?[  ]
A.檢索    B. 插入    C.刪除    D.更新    E.排序
4.  包含N個幾點和M條邊的有向帶權圖G, 邊的權為正, 以下操作中不可以在O(N+M)
的時間復雜度內完成的操作是:[  ]
A.  求結點s到結點t之間的最短距離
B.  求距離結點s最近的結點
C.  已知起始結點, 對圖G中的結點進行拓撲排序
D.  求圖G的最大強連通子圖
5.  有如下遞歸函數f(n),其時間復雜度為[  ]
int f(int n){
    if(n==0)
     return 0;
    if(n==1)
     return 1;
    return ( 5*f(n-1) - 6*f(n-2));
}
A.O(n)     B. O(n^2)    C. O(n^3)    D. O(2^n)
6.  下面所述步驟中,哪一個不是創建經常所必需有的[  ]
A.由調度程序為進程分配CPU       B.建立一個進程控制塊
C.為進程分配內存                    D.將進程控制塊鏈入就緒隊列
7.  在多進程的系統中,為了保證公區變量的完整性,各進程應互斥進入臨界區。所謂臨

界區是[  ]
A.一個緩沖區        B.一個數據區        C.一個同步機構      D.一段程序
8.  能產生滿足如下條件語言的正則表達式是：1.每一個a后至少緊跟兩個c; 2.每一個b

后至少緊跟一個c [  ]
A.(acc|bc|c)*   B.(acc|bc)* C.(ac|bc)*  D.不是正則語言
9.  以下哪項不是RPC（遠程過程調用）的特點[  ]
A.速度快        B.降低系統耦合度        C.可以實現異構系統間的協作
10. 有三個桶，容量分別是3升，5升，7升，你只能進行下面的操作：
把一個桶中所有的水倒掉；
把一個桶A中的水倒入桶B，直到桶A空了或者桶B滿了；
假設一開始容量為3升和5升的桶是滿的，7升的桶是空的，希望通過一系列操作使3個桶

中任意一個中正好有4升水，那么至少需要[  ]次操作。
A.3     B.5     C.7     D.不可能
2.  程序設計與算法
2.1 實現如下編碼算法，對于重復2-9次數的字符，用兩個數字表示，即NX（其中N為重

復的次數，X為重復的字符，下同），超過九個則先輸出9X，然后處理剩下的字符。對于

連續的不重復的字符，則兩邊加1來封字符串。如果被封的字符串其中有數字為1，則用1

來轉義。    示例： AAAAAABCCCC -> 6A1B14C,  12344 -> 11123124。。。（下面的框

架是用C++語言寫的。你可以用你熟悉的語言。）
void encode (const char* text, char* dest)
text 為需要編碼的字符串，dest表示編碼輸出的目標空間，而空間足夠大
2.2給定一顆有n個結點的二叉樹。求它的所有結點數為m的連通子圖數目。m<=n分析你的

算法的時間復雜度，解釋算法即可，不必寫代碼。
 
 
用:    
  假設有這樣一種字符串，它們的長度不大于   26   ，而且若一個這樣的字符串其長度為   m   ，則這個字符串必定由   a,   b,   c   ...   z   中的前   m   個字母構成，同時我們保證每個字母出現且僅出現一次。比方說某個字符串長度為   5   ，那么它一定是由   a,   b,   c,   d,   e   這   5   個字母構成，不會多一個也不會少一個。嗯嗯，這樣一來，一旦長度確定，這個字符串中有哪些字母也就確定了，唯一的區別就是這些字母的前后順序而已。    
   
  現在我們用一個由大寫字母   A   和   B   構成的序列來描述這類字符串里各個字母的前后順序：    
   
  如果字母   b   在字母   a   的后面，那么序列的第一個字母就是   A   （After），否則序列的第一個字母就是   B   （Before）；    
  如果字母   c   在字母   b   的后面，那么序列的第二個字母就是   A   ，否則就是   B；    
  如果字母   d   在字母   c   的后面，那么   ……   不用多說了吧？直到這個字符串的結束。    
   
  這規則甚是簡單，不過有個問題就是同一個   AB   序列，可能有多個字符串都與之相符，比方說序列“ABA”，就有“acdb”、“cadb”等等好幾種可能性。說的專業一點，這一個序列實際上對應了一個字符串集合。那么現在問題來了：給你一個這樣的   AB   序列，問你究竟有多少個不同的字符串能夠與之相符？或者說這個序列對應的字符串集合有多大？注意，只要求個數，不要求枚舉所有的字符串。    
   
   
  嘿嘿，這就是你要解決的問題了。如果不嫌慢的話大可以窮舉，不過這種解法拿出來那是顯然不好意思和人打招呼的。事實上，如果設   AB   序列的長度為   n   ，那么這個問題是可以做到   O(n^3)   的。 
 

1、有兩根不均勻分布的香，香燒完的時間是一個小時，你能用什么方法來確定一段15分鐘的時間？
答：2根香同時點燃，第一根兩頭都點燃，第二根只點一頭， 第一根點完的時候是半個小時，接著把第二根兩頭都點燃，第二根點完的時候就是15分鐘。

２、一個經理有三個女兒，三個女兒的年齡加起來等于13，三個女兒的年齡乘起來等于經理自己的年齡，有一個下屬已知道經理的年齡，但仍不能確定經理三個女兒的年齡，這時經理說只有一個女兒的頭發是黑的，然后這個下屬就知道了經理三個女兒的年齡。請問三個女兒的年齡分別是多少？為什么？

答：2，2，9， 1歲不可能

3、有三個人去住旅館，住三間房，每一間房$10元，于是他們一共付給老板$30，第二天，老板覺得三間房只需要$25元就夠了于是叫小弟退回$5給三位客人，誰知小弟貪心,只退回每人$1，自己偷偷拿了$2，這樣一來便等于那三位客人每人各花了九元，于是三個人一共花了$27，再加上小弟獨吞了不$2，總共是$29。可是當初他們三個人一共付出$30那么還有$1呢？
答：沒錯，三個人付了27塊，老板拿了25塊，小弟拿了2塊
４、有兩位盲人，他們都各自買了兩對黑襪和兩對白襪，八對襪了的布質、大小完全相同，而每對襪了都有一張商標紙連著。兩位盲人不小心將八對襪了混在一起。 他們每人怎樣才能取回黑襪和白襪各兩對呢？

答：不知道，還要仔細想想
５、有一輛火車以每小時15公里的速度離開洛杉磯直奔紐約，另一輛火車以每小時20公里的速度從紐約開往洛杉磯。如果有一只鳥，以30公里每小時的速度和兩輛火車同時啟動，從洛杉磯出發，碰到另一輛車后返回，依次在兩輛火車來回飛行，直到兩輛火車相遇，請問，這只小鳥飛行了多長距離？

答：記好兩車相遇時間，就是鳥飛行時間，乘以其飛行速度就得到飛行距離。

６、你有兩個罐子，50個紅色彈球，50個藍色彈球，隨機選出一個罐子，隨機選取出一個彈球放入罐子，怎么給紅色彈球最大的選中機會？在你的計劃中，得到紅球的準確幾率是多少？

答：不知道，還要仔細想想

７、你有四個裝藥丸的罐子，每個藥丸都有一定的重量，被污染的藥丸是沒被污染的重量＋1.只稱量一次，如何判斷哪個罐子的藥被污染了？
答：不知道，還要仔細想想
８、你有一桶果凍，其中有黃色，綠色，紅色三種，閉上眼睛，抓取兩個同種顏色的果凍。抓取多少個就可以確定你肯定有兩個同一顏色的果凍？
答：4

９、對一批編號為1～100，全部開關朝上(開)的燈進行以下*作：凡是1的倍數反方向撥一次開關；2的倍數反方向又撥一次開關；3的倍數反方向又撥一次開關……問：最后為關熄狀態的燈的編號。

答：不知道，還要仔細想想

１０、想象你在鏡子前，請問，為什么鏡子中的影像可以顛倒左右，卻不能顛倒上下？

答：人的眼睛是左右對稱的
１１、一群人開舞會，每人頭上都戴著一頂帽子。帽子只有黑白兩種，黑的至少有一頂。每個人都能看到其它人帽子的顏色，卻看不到自己的。主持人先讓大家看看別人頭上戴的是什幺帽子，然后關燈，如果有人認為自己戴的是黑帽子，就打自己一個耳光。第一次關燈，沒有聲音。于是再開燈，大家再看一遍，關燈時仍然鴉雀無聲。一直到第三次關燈，才有劈劈啪啪打耳光的聲音響起。問有多少人戴著黑帽子？
答：3 
 
 

一、單選
1、80x86中，十進制數-3用16位二進制數表示為？
2、假定符號-、*、$分別代表減法、乘法和指數運算，且
1)三個運算符優先級順序是：-最高，*其次，$最低；
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+p}
main(){
　　double a = 2.5, b = 9.0;
　　calc(b-a, a, 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("%d\n", foo(3, 5));
(A)81 (B)27 (C)9 (D)3 (E)1
5、下列哪個數據結構在優先隊列中被最廣泛使用？
(A)堆 (B)數組 (C)雙向鏈表 (D)圖 (E)向量
6、以下算法描述了一個在n國元素的雙向鏈表中找到第k個元素的方法（k >= 1且k <= n）：
如果k <= n - k，從鏈表開始往前進k-1個元素。
否則，從終點出發，往回走n - k個元素。
這個算法的時間代價是？
(A)θ(nlogn) (B)θ(max{k, n - k}) (C)θ(k + (n - k))
(D)θ(max{k, k - n}) (E)θ(min{k, 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、為讀取一塊數據而準備磁盤驅動器的總時間包括
(A)等待時間 (B)尋道時間 (C)傳輸時間 (D)等待時間加尋道時間
(E)等待時間加尋道時間加傳輸時間
二、算法
1、打印出一個二叉樹的內容。
2、在一個字符串中找到第一個只出現一次的字符。如abaccdeff，輸出b。
3、給定一個長度為N的整數數組（元素有正有負），求所有元素之和，最大的一個子數組。分析算法時空復雜度。不必寫代碼。

附上動態規劃做法的答案:
最大子序列
問題：
給定一整數序列A1， A2，... An （可能有負數），求A1~An的一個子序列Ai~Aj，使得Ai到Aj的和最大
例如：整數序列-2, 11, -4, 13, -5, 2, -5, -3, 12, -9的最大子序列的和為21。對于這個問題，最簡單也是最容易想到的那就是窮舉所有子序列的方法。利用三重循環，依次求出所有子序列的和然后取最大的那個。當然算法復雜度會達到O (n^3)。顯然這種方法不是最優的，下面給出一個算法復雜度為O(n)的線性算法實現，算法的來源于Programming Pearls一書。在給出線性算法之前，先來看一個對窮舉算法進行優化的算法，它的算法復雜度為O(n^2)。其實這個算法只是對對窮舉算法稍微做了一些修改：其實子序列的和我們并不需要每次都重新計算一遍。假設Sum(i, j)是A ... A[j]的和，那么Sum(i, j+1) = Sum(i, j) + A[j+1]。利用這一個遞推，我們就可以得到下面這個算法：
int max_sub(int a[],int size)
{
　　int i,j,v,max=a[0];
　　for(i=0;i<size;i++)
　　{
　　　　v=0;
　　　　for(j=i;j<size;j++)
　　　　{
　　　　　　v=v+a[j];//Sum(i, j+1) = Sum(i, j) + A[j+1]
　　　　　　　　if(v>max)
　　　　　　　　　max=v;
　　　　}
　　}
　　return max;
}
那怎樣才能達到線性復雜度呢？這里運用動態規劃的思想。先看一下源代碼實現：
int max_sub2(int a[], int size)
{
　　int i,max=0,temp_sum=0;
　　for(i=0;i<size;i++)
　　{
　　　　　　temp_sum+=a;
　　　　　　if(temp_sum>max)
　　　　　　　　max=temp_sum;
　　　　　　else if(temp_sum<0)
　　　　　　　　temp_sum=0;
　　}
　　return max;
}
在這一遍掃描數組當中，從左到右記錄當前子序列的和temp_sum，若這個和不斷增加，那么最大子序列的和max也不斷增加(不斷更新 max)。如果往前掃描中遇到負數，那么當前子序列的和將會減小。此時temp_sum 將會小于max，當然max也就不更新。如果temp_sum降到0時，說明前面已經掃描的那一段就可以拋棄了，這時將temp_sum置為0。然后， temp_sum將從后面開始將這個子段進行分析，若有比當前max大的子段，繼續更新max。這樣一趟掃描結果也就出來了。 
 
 

Google筆試是沒有門檻的。這樣說是因為Google根本沒有限制筆試的人數，開了N個教室，讓N多人參加……不過筆試本身卻有門檻，看了題目就知道。
　　本來想上午寫寫的，但是，嗯，出于攢人品的目的，還是等到現在才寫——現在，面試通知已經發過，很顯然我又被無視了……OK，那也不錯，我也沒怎么準備這些東西呢，倒不是說我不重視，而是事情太多……唔，多少算是一種經驗了。
　　回來說說昨天的筆試。題目的量并不大，除了幾個單選題，剩下就是三個編程或算法題。單選就不說了，考得比較基礎，涉及C語言常識、數據結構、文法、操作系統，主要說說大題。
　　大題雖然題型不一，但都有一個重要特點：考遞歸。精確點說，我每一題都用到了遞歸。
　　第一個的題目（嗯，記的不是很完整）：
在一棵（排序？）二叉樹中搜索指定值，數據結構定義為（唉唉，數據結構的具體名字都不記得了，my god）：
struct Node
{
    Node * lnext;
    Node * rnext;
    int value;
};
函數定義為（情況同上，啥都記不清了）：
Node * search(Node * root, int value)
{
}
實現這個search函數。
用遞歸，經典的樹的遍歷，pass先。
第二個的題目：
計算Tribonaci隊列（嗯，九成九記錯了那個單詞……），規則是T(n) = T(n - 1) + T(n - 2) + T(n -3)，其中T(0) = T(1) = 1，T(2) = 2。
函數定義：
int Tribonaci(int n) {
}
備注，不考慮證整數溢出，盡可能優化算法。
　　這一題我一看就知道要考什么，很顯然的遞歸定義，但也是很顯然的，這里所謂的優化是指不要重復計算。
　　簡單的說，在計算T(n)的時候要用到T(n - 1)、T(n - 2)和T(n - 3)的結果，在計算T(n - 1)的時候也要用到T(n - 2)和T(n - 3)的結果，所以在各項計算的時候必須把以前計算的結果記錄下來，去掉重復計算。這里用到的一點小技巧就是要新寫一個函數用來做這種事情，嗯，看看我寫的代碼吧！
    /**
      Get the value of T(n - 1), and retrieve the result of
      T(n - 2) and T(n - 3).
      @param[in] n The n in T(n).
      @param[out] mid Value of T(n - 2).
      @param[out] right Value of T(n - 3).
      @return Value of T(n - 1).
     */
    int find_trib(int n, int & mid, int & right)
    {
        if (3 == n)
        {
            mid = 1;
            right = 1;
            return 2;
        }
        else
        {
            int temp;
            mid = find_trib(n - 1, right, temp);
            return mid + right + temp;
        }
    }
    /**
      Find value of T(n).
      @param[in] The n in T(n).
      @return Value of T(n).
      @note T(n) = T(n - 1) + T(n - 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;
        }
        if (0 == n || 1 == n)
        {
            return 1;
        }
        if (2 == n)
        {
            return 2;
        }
        int mid, right;
        int left = find_trib(n, mid, right);
        return left + mid + right;
    }
　　啊啊，對了，答卷的時候我可沒心情寫注釋……剛才到VC.Net 2003上測試了一下，貌似沒有啥問題。唉，看來我多少還是懂一點算法的……
　　第三個的題目：
　　在一個無向圖中，尋找是否有一條距離為K的路徑，描述算法即可，不用實現，分析算法的時間和空間復雜度，盡量優化算法。
　　OK，這個就是傳說中的軟肋了………………我也就不把自己的答案寫出來了（丟人啊），雖然后來仔細想想，我那個挫挫的方法也能夠用……只是效率……
　　That's all.
轉載請注明出自應屆生求職招聘論壇 http://bbs.yingjiesheng.com/,本貼地址:http://bbs.yingjiesheng.com/thread-21638-1-1.html