電話面試演算法題

『壹』 Google的電話面試，發面經，攢人品

Google的電話面試，發面經，攢人品

原定的下午2：00開始，一分鍾都沒遲到。贊一下Google工作的認真。電話是從google北京
辦公室打來的。上來一聽是中文，失望了不少。之前連續聽了兩天NPR News溫習口語環境，
現在一看完全用不上了。

上來第一個問題是：談一下你以前做過的項目。因為我應聘的是google的wireless項目，所
以挑了一個以前做過的微軟的移動開發項目說了說。剛簡單介紹了一下項目內容，對方就開
始針對剛才我的描述發問。問得基本都是和技術有關的問題，比如我說我們的項目用到了
GPS定位，他就問如何獲得准確的GPS定位數據，如何把GPS坐標和二維地圖進行一一映射，
如何處理不合情理的數據，如何存儲數據更高效。感覺上對方相當善於從我的描述中找到發
問點。所以建議xdjm們介紹自己項目經驗時，除非自信是特別能化無為有、自圓其說、口才
驚人的那種，否則一定要挑自己最熟悉的項目介紹。

第二個問題是編程常識題：C語言中分配內存有幾種方式。這個不多說了，仔細查查書就能
知道。我謹慎的答一種是分配在堆里一種分配在棧里。達人不要笑話歐。

第三個問題是演算法設計題：一張白紙上畫了N條直線，用一種時間復雜度最低的方法算出這
些直線一共有多少個交點。個人感覺以後在面試技術類職務之前一定要多看看演算法題，答不
上來真的好糗。我一開始想了一種最直接的復雜度為O(n^2)的，被鄙視說復雜度太高，問還
能不能把復雜度降下來。於是我開始絞盡腦汁的想。大概20分鍾時間都花在這道題上了，中
能不能把復雜度降下來。於是我開始絞盡腦汁的想。大概20分鍾時間都花在這道題上了，中
間被對方提示和糾正了兩三回，最後還是沒完整的答完，只好進行到下一道題。（真後悔之
前沒主攻一下演算法部分）

第四個問題還是演算法題：有個MxN的迷宮，一個人站在迷宮的左上角，出口在右下角。這個
人每走一步只能向下一步或者向右一步，不能向左或後退。問這個人從入口到出口一共有多
少種不同的走法。這題相對簡單一點兒，我答上來了。

最後是提問階段，我提了一個技術層面的問題和另一個Google產品定位上的問題，對方很耐
心的給予了解答。

整個電面持續了57分鍾。個人感覺那個求交點個數的答得不好，沒有給出正確答案。以後應
該多看看演算法部分，要不然就別指望進Google混了。但願自己和Google的緣分不會到此終結
，特發此面經以攢rp。

掛上電話後的心情是好像弄到了五味瓶，各種情緒匯集在一起。平日里自己覺得自己挺優秀
的，但是突然感覺有種被鄙視了的感覺。也許以前的自我感覺良好都是蒙在眼前的幻覺，真
正的被鄙視的感覺才是真實的。聽著dido的thank you寫完此?
第三個問題是演算法設計題：一張白紙上畫了N條直線，用一種時間復雜度最低的方法算出這
些直線一共有多少個交點。個人感覺以後在面試技術類職務之前一定要多看看演算法題，答不
上來真的好糗。我一開始想了一種最直接的`復雜度為O(n^2)的，被鄙視說復雜度太高，問還
能不能把復雜度降下來。於是我開始絞盡腦汁的想。大概20分鍾時間都花在這道題上了，中
能不能把復雜度降下來。於是我開始絞盡腦汁的想。大概20分鍾時間都花在這道題上了，中
間被對方提示和糾正了兩三回，最後還是沒完整的答完，只好進行到下一道題。（真後悔之
前沒主攻一下演算法部分）

第四個問題還是演算法題：有個MxN的迷宮，一個人站在迷宮的左上角，出口在右下角。這個
人每走一步只能向下一步或者向右一步，不能向左或後退。問這個人從入口到出口一共有多
少種不同的走法。這題相對簡單一點兒，我答上來了。

最後是提問階段，我提了一個技術層面的問題和另一個Google產品定位上的問題，對方很耐
心的給予了解答。

整個電面持續了57分鍾。個人感覺那個求交點個數的答得不好，沒有給出正確答案。以後應
該多看看演算法部分，要不然就別指望進Google混了。但願自己和Google的緣分不會到此終結
，特發此面經以攢rp。

掛上電話後的心情是好像弄到了五味瓶，各種情緒匯集在一起。平日里自己覺得自己挺優秀
的，但是突然感覺有種被鄙視了的感覺。也許以前的自我感覺良好都是蒙在眼前的幻覺，真
正的被鄙視的感覺才是真實的。聽著dido的thank you寫完此文，希望自己能夠重新找回自
信，開拓出屬於自己的一片天空。 ;

『貳』 面試會出哪些經典演算法題

如下：

1、排序演算法∶快速排序、歸並排序、計數排序

2、搜索演算法∶回溯、遞歸、剪枝技巧

3、圖論∶最短路、最小生成樹、網路流建模

4、動態規劃：背包問題、最長子序列、計數問題

5、基礎技巧：分治、倍增、二分、貪心

6、數組與鏈表：單/雙向鏈表、跳舞鏈

7、棧與隊列

8、樹與圖：最近公共祖先、並查集

9、哈希表

10、堆：大/小根堆、可並堆

11、字元串∶字典樹、後綴樹

演算法簡介：

演算法（Algorithm）是指解題方案的准確而完整的描述，是一系列解決問題的清晰指令，演算法代表著用系統的方法描述解決問題的策略機制。也就是說，能夠對一定規范的輸入，在有限時間內獲得所要求的輸出。

如果一個演算法有缺陷，或不適合於某個問題，執行這個演算法將不會解決這個問題。不同的演算法可能用不同的時間、空間或效率來完成同樣的任務。一個演算法的優劣可以用空間復雜度與時間復雜度來衡量。

演算法中的指令描述的是一個計算，當其運行時能從一個初始狀態和（可能為空的）初始輸入開始，經過一系列有限而清晰定義的狀態，最終產生輸出並停止於一個終態。一個狀態到另一個狀態的轉移不一定是確定的。隨機化演算法在內的一些演算法，包含了一些隨機輸入。

形式化演算法的概念部分源自嘗試解決希爾伯特提出的判定問題，並在其後嘗試定義有效計算性或者有效方法中成形。

這些嘗試包括庫爾特·哥德爾、Jacques Herbrand和斯蒂芬·科爾·克萊尼分別於1930年、1934年和1935年提出的遞歸函數，阿隆佐·邱奇於1936年提出的λ演算，1936年Emil Leon Post的Formulation 1和艾倫·圖靈1937年提出的圖靈機。即使在當前，依然常有直覺想法難以定義為形式化演算法的情況。