面試題以及答案(一)

　　應聘職位：軟件工程師

　　10)假設你在衣櫥里掛滿襯衫，很難從中挑出某一件來。請問你打算怎樣整理一下，使得它們容易挑選?

　　答案：此題沒有固定答案。考驗的是被面試者在解決問題方面的想象力和創造性。我們覺得讀者”Dude”的這個答案可能會給Google留下深刻印象：把它們按布料的種類進行哈希(HASH)組合。然后每類再按2-3-4樹或紅黑樹(都是計算機算法)排序。

　　應聘職位：軟件工程師

　　11)給你一副井字棋(Tic Tac Toe)。。。你來寫一個程序，以整個游戲和一個玩家的名字為參數。此函數需返回游戲結果，即此玩家是否贏了。首先你要決定使用哪種數據結構處理游戲。你還要先講出使用哪種算法，然后寫出代碼。注意：這個游戲中的某些格子里可能是空的。你的數據結構需要考慮到這個條件。

　　答案：所需要的數據結構應為二元字符數列。調用此函數檢查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網站：“一個方法是寫一個遞歸算法來決定何時等待，何時跳進下一個車道。這由下條車道中是否有逐漸接近的障礙物來決定。”

　　應聘職位：軟件工程師

　　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”：建立臨時指針并從根上開始。(循環鏈表大多數情況下都有向前或向后指針。)判斷是向前更大還是向后更大。如果向前更大則知道已達到鏈表最后，又重新位于鏈表開始位置。如果向前更大，那你可以向后搜尋并進行數字比較。如果既沒有根也沒有指針指向鏈表，那么你的數據就丟失在內存中了。