知乎：互聯網公司最常見的面試算法題有哪些？

鏈接：https://www.zhihu.com/question/24964987

編輯：深度學習與計算機視覺

聲明：僅做學術分享，侵刪

作者：知乎用戶
https://www.zhihu.com/question/24964987/answer/128620102

本人在美國10年，FLAG公司，以及各大科技巨頭面試也見過很多次，可以大概的分享下我的經驗

首先需要明白的是：應屆畢業(yè)生和在職跳槽，面試難度上，應屆畢業(yè)生的難度，以及打分的要求，會略低于在職跳槽，原因很簡單，應屆畢業(yè)生經驗不足，沒有全職的工作經歷。

至于灣區(qū)FLAG和各大公司巨頭的面試流程，時間線，不是本問題的中心，如果需要的話，可以私信我。

首先，作為程序員，你必須知道Leetcode這個OJ，刷題題庫，必備
題目分為easy, medium, hard等級，沒有聽說過的朋友可以先去看看。

現在講講面試的題目

Facebook，面試難度9分
考察的知識點很全面，Facebook的面試題目難度一般都在medium偏上一點，但為什么我打難度9分，因為Facebook的面試要求很高，簡單的說，面試者必須在最快的時間內寫出bug free的代碼，一旦出現BUG，這輪面試基本就掛了。另外，FB比較強調最優(yōu)解。比如，會先問你2sum，然后拓展到3sum，4sum。比如經典的動態(tài)規(guī)劃，背包問題以及所有的follow up，都是比較經典的常考題目。

Linkedin，面試難度7分
Linkedin的面試難度適中，Leetcode上中等難度的題目居多，經典一點的，比如nested element iterator, sqrt, paint fence都是比較經典的題目。大概的難度都在這個范圍之內

Amazon，面試難度6.5
整體而言，亞馬遜在硅谷的四大巨頭里的面試，技術難度是最低的，但是能夠成功通過面試并沒多很多。原因在于亞馬遜很看重行為類問題（behaviral question）以及公司的文化配合（culture fit）。技術方面，經典一點的題目，比如最長回文串，二叉樹層遍歷，二叉樹validate等等

Google，面試難度9.5
狗家的面試題目，在LEETCODE上算是medium偏難，以及一些hard的題目。但最難的點在于，谷歌有自己的題庫，而且是不斷跟新的，這個就無形中增大了面試難度。題目方面，谷歌考得很全面，線段樹(segment tree)，動態(tài)規(guī)劃DP，以及圖，是常出現的。

作者：文航
https://www.zhihu.com/question/24964987/answer/33541018

說一說我在Airbnb當面試官的經驗

先說個結論：算法是其次，主要是寫碼能力與熟練度

Airbnb一般的coding面試的流程是45分鐘，10~15分鐘白板分析下問題，25~30分鐘上機實現算法，5分鐘留給面試者問問題

時間的限制決定了題不可能太難，基本不會超過leetcode難度。而且Airbnb作為還算是創(chuàng)業(yè)公司，更看重的是快速落實一個想法的能力。一些常用的算法（什么拓撲排序啊，回溯，最小生成樹這些，都是很基本的）你忘了也沒關系，我們可以一起在白板上推。稍微有點實力的面試者白板出一個solution是沒有問題的，所以這個時候就主要看寫碼能力與熟練度了。

上機寫碼考察的方面很多，比如面試者

• 語言的熟練程度 語言不重要，但你總得對你拿來面試的語言很熟吧。我們會先問你prefer什么語言，然后選這個語言熟的面試官來。
  
• 落實設計的能力 最怕吹半天，寫一行代碼都困難的那種人。
• 對電腦的熟悉程度  這個不是必須，但熟練使用快捷鍵、shell之類的總是加分項

灣區(qū)據我所知有越來越多的公司是采用上機寫碼或者pair programming的這種形式。（Square是純pair programming。Uber是只白板，所以uber印度人多）

我見過很多面試者，名校畢業(yè)簡歷上project一大堆，結果第一步implement一個圖都扭扭捏捏半天搞不出來，估計在project里面也就醬油為輔混資歷為主。還有Amazon資深工程師，在eclipse里面寫java，每一行不寫完，讓IDE自動改錯，還都是拿鼠標去點，結果愣是沒寫完。

作者：土豆不是馬鈴薯
https://www.zhihu.com/question/24964987/answer/137554551

2017年校招，總共面試10家互聯網公司，總結一下大概遇到的算法題。
1.數組中逆序對計算。(劍指offer)

2.判讀一個樹是不是另一個樹的子樹(劍指offer)

3.數據流要求o(1)求得中位數，o(lgn)插入（劍指offer）

4.順時針打印矩陣（劍指offer）

5.復雜鏈表復制（劍指offer）

6.二叉排序樹中第k小的數（劍指offer）

7.反轉鏈表遞歸  、非遞歸（劍指offer）

8.鏈表中倒數第k個結點（劍指offer）

9.數組中超過一半的數字(劍指offer)

10.左旋轉字符串（劍指offer）

11.把二叉樹打印成多行（劍指offer）

12.旋轉數組查找（劍指offer）

13.鏈表歸并排序

14.Trapping Rain Water：https://leetcode.com/problems/trapping-rain-water/

15.Longest Palindromic Substring：https://leetcode.com/problems/longest-palindromic-substring/

16.Gray Code：https://leetcode.com/problems/gray-code/

17.Binary Tree Maximum Path Sum：https://leetcode.com/problems/binary-tree-maximum-path-sum/

18.Search for a Range：https://leetcode.com/problems/search-for-a-range/

19.算術表達式轉逆波蘭表達式（后綴表達） 

20.k-means  

21.字符串由大小寫字母組成，要求去重，只允許使用幾個int臨時變量，要求時間復雜度盡可能少

22.青蛙每次跳臺階，每次一步或者二步，青蛙總共可以跳n次，臺階共m階（n<=m），每個臺階有若干害蟲，使得青蛙吃的害蟲最多。

23.左右括號組成的字符串，去除最少使得剩余的字符串是合法的（符合左右括號規(guī)則）

24.實現5選3  組合

25.數組中后面的數減前面的數差的最大值，要求時間、空間復雜度盡可能低

26.多個有序數組的歸并

27.多個有序數組求交集

28.二個有序數組求差集

29.字符串中最長不重復子串

30.小于10萬的回文數的個數
總結：多刷幾遍劍指offer！！！

往期精彩：
【原創(chuàng)首發(fā)】機器學習公式推導與代碼實現30講.pdf
【原創(chuàng)首發(fā)】深度學習語義分割理論與實戰(zhàn)指南.pdf
 談中小企業(yè)算法崗面試
 算法工程師研發(fā)技能表
 真正想做算法的，不要害怕內卷
 算法工程師的日常，一定不能脫離產業(yè)實踐
 技術學習不能眼高手低
 技術人要學會自我營銷
 做人不能過擬合
求個在看