15道Google面試題，你會做嗎？
英文原文：15 Mind-Bending Interview Questions That Every Google Engineer Can Answer
導讀：進入像谷歌這樣的互聯網公司是許多人的夢想，而這些公司的面試卻是很大的檻。那么，谷歌對前來應聘的工程師會提出什么樣的問題呢？我們這里收集了來自職業發展社區 Glassdoor 的一些面試者真實經歷的面試題。雖然這些題目沒有人想象的那么匪夷所思，看似很簡單，但實際上這些題目都值得好好思量一番。
來看看谷歌為他們準工程師們準備的題目，看看你能做出多少：
1. 請寫出一個整數乘法的算法
挑戰：這是一個相當開放性的問題，設計初衷是看看工程師是否會定義參數。
編程語言是什么？是匯編語言嗎？
是：那么你得白手起家開發出一套基本運算來。
否則的話：那就簡單了，只需將數字套進去即可，因為大部分語言均支持數學運算。
2. 合并兩個排序鏈表
挑戰：這類問題是 Google 面試問題的一個共同趨勢：找出解決問題的有效辦法。
合并兩條鏈表一般會在鏈表之間發生“沖突”（因為它們各自有特定的次序，而你的合并會把次序搞亂），你必須找出一種算法快速消除這些沖突。
3. 給出一組時段（以秒計），讓你找出重疊的部分
挑戰：Google 一般也會要你解決一堆數學問題。
這些設計的意圖是讓工程師對問題進行有效的思考，而不是僅僅知道如何對每個問題進行編碼。
此處的問題會需要你利用一個聰明的數學技巧來解決。
4. 如果有一個含有n個節點的列表，對于一個有向無環圖來說，最多可以有幾條邊？
挑戰：這是著名的旅行商問題（traveling salesman problem）的一個派生。
這是一個不要求你找出聰明的數學算法而是要你拓展思路的數學問題。你必須在節點間畫線，條件只有一個：無論你從哪里開始，永遠不要回到原點
5. 在 Java 里面，finally、final 和 finalize 的區別是什么？
挑戰：看看你知不知道這些術語。比方說，finalize 處理的是“垃圾回收”，而 finally 則是指向一個特定的錯誤。
6. 從一大塊文本中去掉重復的行
挑戰：一個基本問題，看你是不是能估算出問題是否可以在有限的時間內解決。
這樣的問題通常可以采取暴力攻擊手段，但也有可能永遠都無法解決。
7. 給你一個字符串，找出包含給定字符集的最小窗口
挑戰：此類問題有許多解決方式，完全取決于你選擇的算法是什么。
Google 要找的是能選出最快算法的工程師。
8. 寫一段程序計算出某字符串是否另一字符串的輪換（rotation）
挑戰：這個問題靠的是看你是不是能夠靈活掌握一些計算機方面知識的轉義。
比方說，“strings”一語通常是指由字符、單詞或可打印、可見的東西組成的多行字符串。不過同時也可以是矩陣（二維對象）及別的對象。
你必須檢查看看它是不是可以輪換（rotate），然后跟另一個進行對比。
9. 舊金山能容納多少個氣球？
挑戰：此類問題 Google 的面試官一般都會問到，目的是想看看你設定的“邊界條件”是什么樣的。
這個問題有許多解決方式，可以通過添加限定條件來進行簡化—比如說舊金山的面積，這種限定在進行編程的時候是很重要的。
10. 粘滯位是什么？為什么要用？
挑戰：粘滯位是一個系統管理術語，指在 Unix 系統中設置文件或者目錄訪問權限的標志位，如果設置，只有 owner 或者 root 權限用戶能夠重命名、刪除文件。
Google 想測試一下，看看你是否了解一些管理的細節，而不是只會編程。
11. 給出一組整數，值范圍在很窄的區間，但是區間未明，如何找出其中位數？
挑戰：又是一個要你能夠利用聰明的數學技巧的問題，離散數學課你有沒有認真聽？
這可不是什么簡單問題。
12. 給出一組區間，找出交集數最多的一個
挑戰：現在 Google 要你確信知道自己檢查的是問題的正確部分，無視沒有價值的部分，這樣才能夠令算法更高效。
13. 100 個整數組成的數組，打亂次序，拿掉其中一個數，把它找出來
挑戰：運用另外一個數學技巧可以幾行代碼搞定。
測試目的是看看你是不是不僅知道用什么辦法，還知道如何實現代碼。
14. 判斷某個數獨解決方案是否正確
挑戰：這個要你想出辦法用另一種數學技巧從算術上快速檢驗解決方案。
15. 給你一支股票的日價，找出一次買賣交易（buy-sell trading）如何操作才會損失最大
挑戰：這個問題非常棒，你必須竭盡所能，把所有的知識本領都用上。
看看邊界條件（即挑出變動最大的股票價格點）然后有效地算出波動最大的一次。
我們能想到的唯一像樣一點的辦法是暴力計算，把每一個股價都遍歷一遍。
來自: www.36kr.com