【IT職場】谷歌面試題集合(附答案)
1) 村子裏有100對夫妻，其中每一個丈夫都瞞着本身的妻子偷情。。。村裏的每一個妻子都能當即發現除本身丈夫以外的其餘男人是否偷情，惟獨不知道她本身的丈夫到底有沒有偷情。村裏的規矩不容忍通姦。任何一個妻子，一旦能證實本身的男人偷情，就必須當天把他殺死。村裏的女人全都嚴格照此規矩辦事。一天，女頭領出來宣佈，村裏至少有一個丈夫偷情。請問接下來會發生什麼事？面試
答案：（由讀者Olivier Coudert提供）算法
這是一個典型的遞歸問題。一旦全部的妻子都知道至少有一個男人×××，咱們就能夠按遞歸方式來看待這個流程。先讓咱們假設只有一個丈夫偷情。則他的妻子見不到任何偷情的男人，所以知道這我的就是本身丈夫，她當天就會殺了他。假若有兩個丈夫偷情，則他倆的妻子只知道不是本身丈夫的那一個男人偷情。所以她會等上一天看那我的有沒有被殺死。假如第一天沒人被殺死，她就能肯定她本身的丈夫也偷了情。依此類推，假若有100個丈夫偷情，則他們能安全活上99天，直到100天時，全部妻子把他們全都殺死。安全
應聘職位：產品經理數據結構
2）假設在一段高速公路上，30分鐘以內見到汽車通過的機率是0.95。那麼，在10分鐘內見到汽車通過的機率是多少？（假設缺省機率固定）ide
答案：（由讀者ru提供）函數
這題的關鍵在於0.95是見到一輛或多輛汽車的機率，而不是僅見到一輛汽車的機率。在30分鐘內，見不到任何車輛的機率爲0.05。所以在10分鐘內見不到任何車輛的機率是這個值的立方根，而在10分鐘內見到一輛車的機率則爲1減去此立方根，也就是大約63%。網站
應聘職位：產品經理spa
3）有四我的要在夜裏穿過一條懸索橋回到宿營地。但是他們只有一支手電，電池只夠再亮17分鐘。過橋必需要有手電，不然太危險。橋最多隻能承受兩我的同時經過的重量。這四我的的過橋速度都不同：一個須要1分鐘，一個須要2分鐘，一個須要5分鐘，還有一個須要10分鐘。他們如何才能在17分鐘以內所有過橋？設計
答案：（由匿名讀者提供）指針
1和2一塊兒過（2分鐘）；1返回（3分鐘）；5和10一塊兒過（13分鐘）；2返回（15分鐘）；1和2一塊兒過（17分鐘）。全體安全過橋。
應聘職位：產品經理
4) 你和一個朋友去參加聚會。聚會算上大家一共10人。。。你的朋友想要跟你打個賭：你在這些人每找到一個和你生日相同的，你就贏1塊錢。他在這些人裏每找到一個和你生日不一樣的人，他就贏2塊錢。你該不應打這個賭？
答案
不算閏年的話，別人跟你生日相同的機率是1/365；跟你生日不一樣的機率是364/365。所以不要打這個賭。
應聘職位：產品經理
5）若是你看到時鐘上面的時間是3：15，那麼其時針和分針之間的角度是多少？（答案不是零）
答案：（由讀者Matt Beauchamp提供）
7.5度。時鐘上每一分鐘是6度（360度/60分鐘）。時針每小時從一個數字走到下一個數字（此例中爲從3點到4點），也就是30度。由於此題中時間恰好走過1/4小時，所以時針走完30度的1/4，也就是7.5度。
應聘職位：產品經理
6）將一根木條折成3段以後，能夠造成一個三角形的機率有多大？
答案
由於題目中沒有說要求木條必須首尾相連的作成三角形，所以答案是100%。任何長度的三根木條均可以造成一個三角形。
應聘職位：產品經理
7）南非有個延時問題。請對其加以分析。
答案
這顯然是個很是模糊的問題，所以沒有惟一的正確答案。比較好的回答應該是由被面試者展現本身對「延時」概念的熟悉程度以及發揮本身的想象力，構想出一個有趣的延時問題並對其提供一個有趣的解決方案。
應聘職位：產品經理
8）在一個兩維平面上有三個不在一條直線上的點。請問可以做出幾條與這些點距離相同的線？
答案：（由讀者Denis提供）
三條。將兩點之間聯成一條線段。在這條線段與第三點之間正中的位置，作一條與此線段平行的直線，即爲一條距三點等距的線。而後按此方法對其他兩點的組合作出另外兩條來。
應聘職位：軟件工程師
9）2的64次方是多少？
答案
若是你不是由於坐在面試室裏，手邊沒有計算器的話，應該能夠很容易找到答案，即1.84467441 乘以10的19次方。
【要是我，就寫一個1，後面加上64個零，算是2進制答案，哈哈。——譯者注】
應聘職位：軟件工程師
10）假設你在衣櫥裏掛滿襯衫，很難從中挑出某一件來。請問你打算怎樣整理一下，使得它們容易挑選？
答案
此題沒有固定答案。考驗的是被面試者在解決問題方面的想象力和創造性。咱們以爲讀者"Dude"的這個答案可能會給Google留下深入印象：把它們按布料的種類進行哈希（HASH）組合。而後每類再按2-3-4樹或紅黑樹（都是計算機算法）排序。
應聘職位：軟件工程師
11）給你一副井字棋（Tic Tac Toe）。。。你來寫一個程序，以整個遊戲和一個玩家的名字爲參數。此函數需返回遊戲結果，即此玩家是否贏了。首先你要決定使用哪一種數據結構處理遊戲。你還要先講出使用哪一種算法，而後寫出代碼。注意：這個遊戲中的某些格子裏多是空的。你的數據結構須要考慮到這個條件。
答案：（由讀者」Dude」提供）
所須要的數據結構應爲二元字符數列。調用此函數檢查6種條件，判斷是否有贏家。其中第6種條件就是看是否還有空格。若是有贏家，則字符判斷玩家是X仍是O。所以你須要一個旗標。若是有贏家則返回此值並結束遊戲，若是沒有則繼續遊戲。
應聘職位：軟件工程師
12）爲1萬億個數排序須要多長時間？請說出一個靠譜的估計。
答案
這又是一個沒有標準答案的題目。目的是考察被面試者的創造性。
咱們傾向於兩位讀者給出的簡單答案：用歸併排序法（Merge Sort）排序。平均狀況下爲O(1,000,000,000,000 Log 1,000,000,000,000)。最差狀況下爲O(1,000,000,000,000 Log 1,000,000,000,000)【二者相同。——譯者注】。如今能夠作到每秒10億次的運算，因此大約應須要3000秒。
應聘職位：軟件工程師
13）請設計一個「蛙跳」遊戲的算法，並寫出方案的代碼。。。
答案
這個遊戲的目標是引導一個青蛙避開來往車輛，橫穿一條繁忙的公路。你能夠用一個數列來表明一條車道。將方案簡化成一條N車道的公路。咱們只找到一個對此問題的解答，它來自Glassdoor.com網站：「一個方法是寫一個遞歸算法來決定什麼時候等待，什麼時候跳進下一個車道。這由下條車道中是否有逐漸接近的障礙物來決定。」
應聘職位：軟件工程師
14）Google每一年收到多少份軟件工程師的簡歷？這也是在考察應試者是否有能力把問題簡單明確化，並提出創造性的解決方案。
答案
一個「量化報酬分析師」職位的求職者，應該知道2008年Google僱傭了3400人。估計其中75%，即2550人，應該是工程師，而且Google和哈佛的錄取率相似，即從申請人中取3%。由此可知應該收到大約85000簡歷（85000 x 3% = 2550）
應聘職位：量化報酬分析師
15）給你一個數字鏈表。。。鏈表到頭以後又會從頭開始（循環鏈表）。請寫出尋找鏈表中最小數字的最高效算法。找出此鏈表中的任意給定數字。鏈表中的數字老是不斷增大的，可是你不知道循環鏈表從何處開始。例：38, 40, 55, 89, 6, 13, 20, 23, 36.
答案
咱們最喜歡的答案來自讀者」dude」：創建臨時指針並從根上開始。（循環鏈表大多數狀況下都有向前或向後指針。）判斷是向前更大仍是向後更大。若是向前更大則知道已達到鏈表最後，又從新位於鏈表開始位置。若是向前更大【原文如此，似應爲「向前更小」。——譯者注】，那你能夠向後搜尋並進行數字比較。若是既沒有根也沒有指針指向鏈表，那麼你的數據就丟失在內存中了。