為什麼最難不過二叉樹的演算法出現在面試題中都會被應聘者抱怨？
為什麼面試題比工作中遇到的演算法簡單那麼多，而面試時面一下演算法卻讓很多人義憤填膺呢？
一般最難無非也就出到二叉樹了，而且還不平衡，然後人們就啊啊啊??。我還見過有人這麼說的：「某某公司都日薄西山了，面試還那麼難」——但是他看到的是一道字元串兩個相鄰的子串 O(1) 空間複雜度換過來這種熱身題目。甚至還出現有小 candidate 臨走的時候在某公司的紙巾盒上寫下「不面演算法會死啊」等句子的事情。
最簡單的解釋：典型的工人去面試工程師職位，通不過面試是應該的。（假設如描述所說最難只問到二叉樹。）
我反對面試官隨便網上找一道題就拿來問的做法，我也反對 @歸辰 所說的只應該考察工作上實際所需知識的做法，因為這兩者都基於一個錯誤的面試思路，那就是用面試來考察你懂不懂什麼的。面試不是用來考察你懂不懂什麼的，而是用來考察你有沒有解決問題的能力的，以及將來和你一起解決問題是否容易。我知道中國絕大多數人在經歷了十多年應試教育後，無論是站在面試者的角度來看，還是若干年後成為面試官了從面試官的角度來看，都只會用這種方式來思考問題——「面試」嘛，有個「試」字不就應該跟「考試」差不多咯，而我們習慣的考試就是考察你是否懂某個知識咯，只要死記硬背就可以了。然而真正好的面試不是這樣做的，有興趣的可以去看我之前寫的那篇《理想的技術面試過程》。
回到問題上來，我認為正確的面試方式是這樣子的：現在你來我這裡面試，我就告訴你我們在做一輛車子的原型，現在少了一個輪子問你怎麼辦。沒錯，我就是要讓你重新發明輪子。誰不知道樓下 7-11 有輪子賣，但我就想知道你會如何解決沒有輪子的問題。
你可以從各種聽起來非常愚蠢的方法開始，例如問我這個原型是不是只是用來展出的，是的話把車子放在展廳一角然後讓缺了輪子的一側對著角落，這樣子隨便拿幾塊磚頭把車撐起來就可以了，反正沒人會去看車子的那一側。然後我會告訴你，展廳的天花不可能打開，所以我們不能直接用吊車把原型放進去，最終原型在展廳外面卸下來後你還是是要想個辦法把它弄進去。你可能會說，那就用埃及人用圓木搬動大石塊的方法咯，在原型的底下放幾條滾動的圓木至少能讓它推得動吧。這聽起來還是比較蠢，但我會告訴你這個思路的方向是正確的。這個討論延續下去，最終你還是會提出用金屬做輪子外面再包一圈橡膠的做法，從而完成了重新發明輪子的過程。
之後我會把你帶到車間里，告訴你這裡有你所需的所有電動工具和原材料，你把你剛才發明的那個輪子造出來吧。有些人手藝非常好，一下子就能做出來一個非常好的輪子。有些人無論說得輪子有多圓，做出來的東西永遠只能是方形的。大多數人介乎兩者之間，對此我會說你不如把你造出來的輪子裝到原型上試試看是否合適，不合適的話拿下來再調整一下。
這是正常的面試流程。我不指望你一開始能夠給我一個輪子，我也知道外面賣的輪子很便宜，但我需要驗證你有沒有遇到問題後解決問題的能力，這包括思維和動手兩方面。在這個比喻的基礎上，我們可以來探討一下面試過程中遇到的各種面試者。
那些不懂演算法同時也非常拒絕面試演算法的面試者，就如同一條汽車流水線上的工人來面試汽車工程師一樣。「沒有輪子？老闆你這不是耍我么。我能夠純熟地把輪胎和軸承對齊，然後用電動工具把所有螺絲都擰緊。但沒有輪子這就不是我的問題了。這要麼是採購的問題，要麼是倉管的問題，反正輪胎沒有出現在流水線上我就什麼都做不了。如果說沒有電動工具，我可以去找兩把手動工具來，用腳踩兩下也能擰緊，但沒有輪胎真的不是我能負責的。」
當然這都不是最搞笑的，還有更搞笑的類型。ACM/ICPC 競賽選手或者是面試前專門在網上刷題的面試者，基本上一上來就「哦，你要個輪子是吧。我知道怎麼造輪子，你給我工具和材料就行了」，然後就以極快的速度造了一個輪子出來，裝上去也沒有任何問題。有一定的概率我在仔細檢查後發現，這個輪子是用鉚釘裝上去的，所以拆不下來了，橡膠是一次充氣後完全密封的，因此漏氣之後不可能再打氣。不過想想也合理，這類工程師專業做撞擊測試，所以在他們的世界裡面任何東西造出來都不是長期使用的，而是拿去測試一下，通過或通不過都立即變廢品。
還有一些情況是這樣子的，例如我問超大整數乘法然後對方說用 Python 直接用乘號，又或者說我問快速排序對方說用 Haskell 一行寫完。這就如同一個面試者打開公文包掏出一個輪子說「我這正好有一個，不知道是否合適？」呃……你的百寶袋裡面還有什麼？
最後從面試官的角度來說，面試 ACM/ICPC 競賽選手往往都很無聊。他們能夠給出一個完美的輪子，但我不覺得我能從他們身上學到新東西。（面試過足夠多的人後，要見到一個比已知完美輪子更完美的輪子其實非常難。）更有趣的面試者會說，「你知道嗎，其實中國古代獨輪手推車的輪子設計得比古羅馬戰車的輪子要合理」。其實我不知道你在說什麼，但如果你能夠把整套理論說得自圓其說的話我覺得你至少有點思維能力，同時你還真的對輪子感興趣。事後我可能會去搜索一下看看你說的理論是否正確，但至少我會學到點新東西。先亮明觀點：身為程序員，演算法知識100%是必要的！
本人從事的不是什麼高大上的研究工作，跟數據挖掘模式識別自然語言處理雲計算大數據blahblah全都不沾邊。做過一段時間的J2EE開發，現在主要做基於HTML5的前台開發。看到這兒很多人要說了，不就是個做網頁的嘛，做網頁還用的上演算法？不就是表單驗證提交一下？我的回答是絕對用的上！
舉個例子，很多人在微博上見過tagcloud分析圖，展示的是一些關鍵字的出現頻率：
這裡不談文本檢索這些，只說對已知數據如何安排各個關鍵字的位置進行渲染。這是個很典型的結合實際的演算法問題，在此我用到了wordle演算法，這和我們上學時常談到的那些演算法不太一樣，但很多核心思路（例如空間換時間）還是相通的。感興趣的同學可以自行了解。
這裡不談文本檢索這些，只說對已知數據如何安排各個關鍵字的位置進行渲染。這是個很典型的結合實際的演算法問題，在此我用到了wordle演算法，這和我們上學時常談到的那些演算法不太一樣，但很多核心思路（例如空間換時間）還是相通的。感興趣的同學可以自行了解。
接下來說說面試的問題。正式工作近9年，一直在coding的第一線，近年來也經常參與對技術人員的面試工作。我和同事們對面試時要不要涉及到演算法的問題沒有絲毫分歧，仍然是有必要。但演算法問題如何問，也是有講究的。我反對上來就指定一個演算法讓面試者寫答案，例如前面有知友提到的寫個快速排序之類的。這樣的做法有掉書袋的嫌疑，而且除了證明對方為了面試做過精心準備，其他方面根本考核不出來。
自己在面試中經常會問的一個問題：
有一組長度為n的對象，每個對象里都有一個startTime和endTime，表示一個時間段。請面試者設計一個小演算法，把這些對象中時間段存在重合關係的所有對象列出來。
這個問題不難，但一定程度上能考驗面試者對演算法本身的理解和sense。對這個問題的典型討論過程是這樣的：
Candidate：我想可以作個雙重循環，把這些對象兩兩比較
me：好的，這顯然是個很直觀的方法。那麼按照你的方法，時間複雜度是多少呢？
Candidate：n^2吧
me：OK，那麼你看看是不是有改進的餘地
Candidate：……也許我可以先排序，後面還沒想好
me：根據什麼排序呢？
Candidate：startTime
me：好，那麼我們畫個圖來看看排好序後這些對象的分布
Candidate：……我想到了！blahblah
me：好的，那麼這個演算法的複雜度是多少？你能分析一下嗎？
Candidate：前面排序用快速排序是n*log(n)，後面的過程是線性的，所以總體就是n*log(n)
……
作為面試官，我曾經聽說過幾個面試者對我給他們的面試經歷評價為「明明小公司一個，面什麼演算法」。
後來我曾經找出了其中一些人的簡歷，回憶了一下面試過程，基本上他們都滿足以下四條中的兩條以上：
1、簡歷上4-5個項目經歷，結果一問，別說不是項目主持了，根本就是參與度極低，一問三不知。（我曾遇到過同一個大概不超過1萬行的項目在3個人簡歷上同時出現的，而且他們都不是項目主持）
2、簡歷上聲稱熟練掌握的內容，掌握程度僅限於最基本的使用，缺乏任何的設計分析能力。
3、對所面試的崗位毫無概念，不明白自己是否符合崗位描述上的必要條件
4、對面試提問思路不清晰，或思路表達不清晰。面對問題時，不是僅僅得不到完美的最終答案，而是思路一片空白。
5、堅決認為C++是王道，「我還是想做C++」，拒絕多語言工作和學習。但實際上C++掌握的並不好。
鄙公司（小公司招人不容易啊！）面試程序時，除非簡歷上寫明了ACM獲獎經歷，否則我給他們安排的所謂「演算法題」基本上不會超過二分查找的難度，而且其實並沒有太多思路上的擴展，僅僅是演算法實現而已。而且這僅限於我實在找不出任何的其它亮點，完全無法滿足一個C++崗位的要求，還堅持想從事C++崗位的時候才會進行這樣的提問。因為我們其實是相信員工在崗位上的成長的，面試時不允許查找資料，時間也有限，能解決的問題難度不如工作時所能解決的問題難度也是很正常的。但至少你要有點思路吧？二分查找不會寫個枚舉也好吧？白卷是鬧哪樣？
結果他們認為是因為演算法題表現不好而被我拒絕了。
除了鄙公司，以我在大公司的被面試以及面試經驗，雖然連基本的演算法題都答不出實在是一件值得鄙視和懷疑的事情，但我依然覺得如果你各方面能力均表現優秀，十分符合崗位所需的要求，其實是不太會因為一個複雜的演算法題沒有答上來而直接被掛掉的。當然，如果你在面試演算法題時毫無思路，或缺乏基本的演算法複雜度分析等能力，被扣分也幾乎是一定的。你被各方面都不比你差，演算法問題表現比你更強的面試者幹掉，也是很有可能的。
說了那麼多，總結起來只有一句：「因為公司面演算法而義憤填膺的，肯定是面試掛掉了而不知道自己究竟為什麼掛掉了的。」
我覺得未來的面試都改成綜藝節目那種形式，四個人一組，現場用答題板答題，這樣被刷掉的就不會有那麼多怨言了……
PS: 愛抱怨的還是少數。我遇到的面試者中，還是有不少雖然我沒有錄取（不符合崗位需求），但性格和溝通上還是很喜歡的孩子的。
======================================================
演算法題是用來衡量你思考和解決問題的能力的。如果是大公司的研發崗位，面一些很難的演算法題我也不覺得為過，當然，不代表一定要答出最完美的答案，更重要的是你的思考、溝通、驗證、以及執行過程。我當初在面試百度的時候，面的是一個算是很高端的字元串匹配題，最完美的答案（改進版AC自動機）我當時是既不知道又是即使知道了也寫不出來，然而我給出了我能力範圍內最漂亮的答案（後綴數組），複雜度雖然多了一個lgN，但面試官也看到了我的分析能力以及思考過程的清晰、方案的完整度以及快速可實施性，後來一樣還是過了。至於「ACM級別」，我想你太小瞧ACM了，真的，就這道題目，在ACM圈子裡是最low的模板題而已，稍微集訓過幾個月的人都會，完全不值得討論……
至於「沒本事不要設立高門檻」，我倒是覺得，不管有沒有本事，有錢就有資格設置高門檻。至於門檻是設在這種看似不直接產生作用的演算法能力上，還是設在什麼管理、項目經驗上，還是設在外貌性別上，這是企業站在自己的角度根據自己的需求選擇的，你覺得不合適，大可選擇別的企業，而不是到處抱怨。大企業，以及大企業出身的管理人員，尤其是面試應屆畢業生的時候，都有可能會更傾向於成長型的員工。這種情況下，不面演算法面什麼？面你行業背景嗎？面你項目經歷嗎？
可笑死了，沒本事就嘲笑別人沒本事。在微博上看到的：「玩演算法的碼農，打拚靠藍條，像是法師。數學就等於藍條最大值，數學差，魔法值不高，很快就到瓶頸了。外語影響回藍速度。經驗和智力加急速和穿透的。不玩演算法的碼農，像是戰士，打拚靠血條，體質加生命，精神加生命回復，經驗和敏捷加急速和破甲。」
這題又成功的引起我的吐槽欲了。
面試到底應該問什麼題？
現在發現好多小公司的人事與面試官根本對自己的項目所需要什麼樣的人不清楚不了解不關心。
一種面試官就是，我也不知道要什麼樣的人，基礎過關就成，從網上搜來的不知道什麼時候
也不知道哪家公司還是哪個無聊人寫的面試題，來，同學，先做上一份吧。
做完了看看成績，嗯，不錯嘛，全然不管人家答的題和你要的人有沒有相關性。
員工入職後，這不能做那不能做，原因是你項目相關的東西，面試的時候都沒問。
另一種面試官，寫一堆的演算法呀，邏輯呀，力求找個高手，
低層工作的程序員誰會那個，幹活一個比一個快，也不見得還記得幾個演算法。
真正記得住演算法的人你感覺不錯，人家開的工資你老闆又不同意。
面試官同學，你現實點兒成嗎？
要麼你找老闆多要點兒工資來請人，
要麼你就按老闆給的工資請的合適的人。
老想以老闆給的工資請個高手來，還總是埋怨現在的人水平太差，
看看行情成嘛，別浪費自己和大家的時間。
－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－
對於真正想招人來幹活不是招來供著的，
請明確以下幾點。
招15K以下的程序員，就別問演算法什麼的了，多問點兒你項目中可能出現的問題
看看人家的解決思路，對當前項目中用到的技術的熟悉程度，
性能調優的思路，看看說話辦事兒靠譜不，溝通上有沒有問題。
如果你說你們簡歷太多來面試的太多，你們還沒找到人，
那一定是你們招聘簡歷寫的太爛，一上來就這個精通，那個熟練，
是個人就可以投，招得到合適的人才怪，只能是浪費大家的時間。
我說說我的理解，很多時候其實是記不清演算法的細枝末節，工作中用到了自然可以查資料查文檔，甚至本來就不用知道那些細枝末節，能知道大體怎麼用性能如何瓶頸在何處如果要改進可以從什麼方面入手就行了。
但面試的時候不一樣，面試官一個勁追問細節，甚至要提筆現場實現一個詳細版本要考慮各種邊界情況什麼的（我了個去沒有文檔沒有IDE我連String類有沒有內置subString這種函數都不記得）難免讓人心裡沒底。
舉個例子我以前實習的時候遇到過一個問題，可以歸結為資源分配，用一個圖模型去建模，最後化成一個線性規劃模型。我覺得如果要面試，問到這裡就差不多了。最多問問迭代求解和直接求解的區別和各自的優點，演算法複雜度什麼的，理論性強一點還可以問問原對偶問題……至於把梯度下降或者矩陣求逆都要現場寫一遍，那就沒必要了。
當然了，面演算法崗位和面開發崗位側重點也不同，還是要結合具體崗位說的。如果是前面有人提到的PHP工程師或者網頁前端，我覺得在實際工作中用到什麼高深演算法的機會應該很少了，面試時候多問問實際的細枝末節才是更能看出水平的。
如果以求職者的角度來看，很多求職者的項目與技能和這些面試演算法題有出入和差別，所以出現了leetcode，劍指Offer等專門應試面試演算法的網站或書籍（個人極度反感，但是現實就是大部分面試就要考這些類型的，你不刷題不看就是容易被斃掉）。所以很多求職者認為自己的技能還沒有表現出來，就被面試的演算法直接給槍斃掉了，自然有所不服，無論你認為這是多麼簡單的演算法，也許他在工作的時候，根本和這些演算法完全不搭邊，工作個幾年不忘光才怪。
那麼除了演算法以外，如何挖掘出求職者的閃光點，這也是對面試官的一個考驗，因為考驗演算法的不外乎就一個根本目的：他到底聰不聰明。但是演算法不好，就一定證明他不聰明，或者工作能力不好了嗎？我覺得不一定。這就是要看面試官和面試者的交談了，面試官去儘力挖掘，面試者去儘力表達推銷自己，這就是一個交互的過程。就說二叉樹。我大二學數據結構，大作業的一部分是自己實現一個平衡二叉樹，沒有任何問題。要是那個時候別人來問我各種細節，毫無壓力。
然後我現在研二，自那次大作業以後再也沒有實現過平衡二叉樹。需要使用各種索引的時候都是無論是自己實現還是直接調用庫，都不是平衡二叉樹。然後現在要是來問我關於平衡二叉樹的各種細節，當然我還記得左旋右旋左右旋右左旋，但你要我把所有的指針賦值都準確回答出來，我一定辦不到。包括其他很多經典演算法，思想我都有印象，細節我只能抱歉。
這類知識性的東西不經過長時間多次反覆是不會形成長期記憶的。所以才會有臨時查的情況產生。而且就算形成了長期記憶，這跟騎自行車這種技能還不一樣。只要時間夠長，總會忘掉的。
我覺得面試者反對的不是問演算法，而是單純地考察這些跟他工作無關的知識。換句話說你就算不問演算法，而是問一個寫前端的Sql查詢怎麼優化或者問一個挖數據的怎麼做編譯器，人家一樣會受不了。因為他需要花時間去特地準備。而這準備又跟他的工作無關（面試之前的工作）。
如果面試官問的演算法與面試者的工作相關，他卻答不上來，確實可以判斷他之前的工作有問題，進而他的能力也許有問題。如果無關，這就成了單純的應試。我們都知道應試教育在人們心目中是什麼樣的存在。討厭什麼的就可以理解了吧。
現階段，面試者也許認為演算法是基礎，人人都該懂，所以才問演算法。萬一過兩年，面試者認為體系結構是基礎，人人都該懂，這個題目就會改成問體系結構的了。那麼計算機科學或者工作所需的編程實踐里到底什麼是基礎？什麼人人都該懂？我也不知道，反正我不覺得演算法是。
當然，面試也和應試教育一樣。問的問題也許並不好，但是足夠公平就行。現階段也沒有別的更好的問題可以問。畢竟不能指望面試官先了解應試者的背景再有針對性地提問。再加上現在大家爭著找工作的市場情況。所以作為應試者，還是安心準備為上。再說，不管有用沒用，知識多了總沒有壞處。
註：本答案只表達了對面試問演算法的部分反對，並未提出任何面試提問的建議方案。
個人認為記憶各種演算法的具體實現沒什麼太大意義，更有意義的是了解什麼時候應該用什麼樣的演算法。
比較好的辦法，就是提出一個在某種具體情境下的問題。同時給面試者一台可以聯網的電腦。面試官可以坐在後面看他是如何搜索，搜索什麼樣的內容。以及如何選擇，實現，改造演算法以適應這種具體情境的。
能從網上直接搜出來答案的問題都不算問題的。
當然我只是做夢而已。「工作中用不到這麼多演算法」就是個錯覺。
有個演算法能漂亮地解決一個問題，我不知道，然後自己倒騰了一個弱弱的方法。嘿，你猜怎麼著？能跑！於是我告訴自己，這工作果然用不上什麼高深的演算法。
直到有一天，冒出個競爭對手的產品比我快1000倍。
我覺得是題目太簡單導致的問題。
面試官覺得，我擦，那麼簡單都不會。
面試者覺得，我擦，沒法調試沒法查資料我怎麼寫的對，這種基礎題目寫錯就沒分啊。
然後不歡而散。
面演算法的時候，我一般允許對方做不出來，但是至少要給一個解決思路。就算你告訴我你用谷歌一下可以解決也比遇到演算法題就放棄反感大驚小怪好得多。
如果面社招的，我出的題目一般都是可以用暴力解決掉的搜索題這種難度的 ，我直接允許對方上網查資料，給予對方一台裝好開發環境的電腦去解決，甚至是來面試前給一個homework。
題目不難，所以有的同學用暴力解決，有的會用簡單的搜索，也有的會用A*這類比較漂亮的解答方案。從而區分度還是很好的
我覺一直得比較重要的是對問題的解決能力，至於你用什麼工具我並不在意，我所提供的工作環境網路都是暢通的，能夠找到有用資料的能力也彌足珍貴，遠比單純的說背個二叉樹遍歷好太多了。
一家之言，僅供參考，如果覺得這種面試深得汝心，也歡迎投簡歷給我哦，工作地點是上海
-----更新-----
目前暫時不需要招人了，感謝各位支持。。。
其實是這樣的：
招聘者希望招到屬性好能升級能進化的人才
而一部分應聘者只想一輩子搬磚，甚至希望少搬磚多拿錢。
我個人覺得呢，這種基礎知識的考察無可厚非。又不是招聘WEB UI工程師非要讓你寫個散列表，那才叫抬杠呢。特別是對於應屆生，也沒啥好問的啊。而且問各種問題，只是想得到一個相對全面一點的評估。至於那些被一道題難住了就覺得不爽了要各種抱怨的人，就不用招了。實際工作中那麼多頭疼的問題，還要不要幹下去了？
有現成的輪子當然可以用，但是沒有輪子呢？像一些生產系統，會用到一些特殊的演算法，人家就只能提供數學公式。具體的實現，一般都沒有現成的輪子，得自己造。但是那些連數組的快速排序 二叉樹的遍歷都扯不清楚的人，這時候還能指望他們來解決問題？
給大家出一道某矽谷大公司的演算法面試題，並給出解答過程，讓大家體驗一下如何去面試
演算法題案例：
Given an input string and a dictionary of words,
segment the input string into a space-separated
sequence of dictionary words if possible. For
example, if the input string is "applepie" and
dictionary contains a standard set of English words,
then we would return the string "apple pie" as output.
簡單說就是給定字典，對無空格的短語切詞。這裡可以考慮一些情形，你先問面試官：
如果輸入的剛好是字典中的一個單詞怎麼辦？（特殊例子）
我是不是只要考慮切成2個單詞的情況？（不僅僅2個，但可以從2個開始）
如果輸入的根本無法切分呢？（就返回空）
有沒有一些單詞拼寫或者助詞縮寫形式（如im = i am，如果在字典中沒有就不算)
如果可以切分多種合理的詞？（返回一種就行）
要不要用一些字典的高級數據結構（trie, heap, suffix tree)（不需要理解）
字典有哪些操作的方式？（就是詞的查詢）
字典有多大？（正常英語詞典，內存足夠）
這些問題時幫助你理解和簡化題目，也考察出你對演算法和數據結構的熟練度。
簡單化的方案：
就把它拆成兩個詞。分別驗證前後是否在字典中。這個直接簡單，也讓面試者心裡有底。下面是python的代碼實例：
def segment_string(input, dict):
len = len(input)
for i in range(len):
prefix = input[0:i+1]
if prefix in dict:
suffix = input[i+1:]
if suffix in dict:
return prefix + " " + suffix
return ""
下面考慮怎麼推廣到一般的情況，有種遞歸的辦法，在上面的基礎上稍微改動一下
def segment_string(input, dict):
if input in dict: return input
len = len(input)
for i in range(len):
prefix = input[0:i+1]
if prefix in dict:
suffix = input[i+1:]
seg_suffix = segment_string(suffix, dict)
if seg_suffix != "":
return prefix + " " + seg_suffix
return ""
給出解答還要分析複雜度，就是所謂的 大O分析，這種遞歸的做法很多人不清楚怎麼計算，但你可以想像 如果單純想 字典裡面只有一個字元組合a，aa, aaa... 輸入也是aaa... 你就發現就是全組合的可能性，答案O(2^N)。
還可以做的更好么？
如果大家清楚動態規劃或者memoization，可以進一步節約計算，這是一種空間換時間的技巧，但大家能思考它的複雜度嗎？如果我說是O(N^2), 大家有辦法去證明嗎？
memory = {}
def segment_string(input, dict):
if input in dict: return input
if input in memory: return memory[input]
len = len(input)
for i in range(len):
prefix = input[0:i+1]
if prefix in dict:
suffix = input[i+1:]
seg_suffix = segment_string(suffix, dict)
if seg_suffix != "":
memory[input] = prefix + " " + seg_suffix
return prefix + " " + seg_suffix
memory[input] = ""
return ""
這道題目就展示了不同層次的優化，首先是一道有現實意義的問題，就是做單詞自動識別，它也不需要特定領域的知識，當然遞歸你還是要知道的。在面試過程中，我可以給你一些提示，但最終你走到哪一步，就看你的能力。並且如果你實現了優化解法，我可以繼續問當字典大到內存放不下如何？
1. 演算法很重要
2. 演算法和數據結構，是當年NOI給我留下最多的財富之一，到現在我還是分分鐘完爆大學的所有同學
3. 面試帶演算法，沒問題，畢竟都是按萬算的工資，演算法可以看一個程序猿很多方面的能力，比如代碼風格，比如思維，比如邊界處理，你是可以工作中用搜索的方式解決，但你不懂的話得來的答案並不一定符合你team的風格或者你公司的業務，沒有哪個演算法是一層不變的
4. 但是面試不應該僅僅停留在演算法上，搜索發達的今天，懂得獲得信息的能力一樣重要
5. 最後，演算法和數據結構是你通往高階程序猿的必由之路，不懂這個，你看得懂個屁源碼，用開源的東西看不懂代碼=慢性自殺，天坑懂不懂
演算法是邏輯的體現，也是創新的基礎。若你不學不知，就會出現明明有成熟演算法卻要自寫低效代碼的情況，也會出現沒有演算法就無解不能自寫一段的情況，然而有了演算法卻要改進一下讓效率更高的情況卻是絕對不可能出現了。coder和碼農，區別就這麼多。或許一家公司只需要碼農，但你不能否定人家對coder的追求。
連二叉樹等基本問題都回答不上的人弱爆了好嘛？還有說出[不面演算法會死啊]這種話的人和北大青鳥三個月出來的技工沒什麼區別，遠遠談不上優秀。
演算法的掌握可以分為三個級別:
level 1. 基本不會。
level 2. 出題的人挖了一個坑，然後你憑藉自己的經驗很輕鬆的跳進去了，然後出題的人很滿意。
level 3. 自己發明了一個演算法 證了它的複雜度，並且複雜度貌似還不錯。那麼寫幾頁紙投給J.ACM上讓同僚們挑挑刺吧！
連二叉樹問題都不會的屬於level 1。
面試通過的（不管是國內面試還是人們眼中美國NB閃閃公司總部的面試）或者IOI拿了金牌！或者ACM/ICPC final 拿了世界總冠軍！ 他們也就是level 2。
level 3 的人就是那些你們在演算法書上看到的XX（某人名）演算法，XX theorem的 XX。
讓我們從上帝視角來觀察，處在level 1的那些人 你們還好意思說[不問演算法會死啊]這種話嗎?想要成為優秀的人趕緊回家閉門修鍊吧。對於90%的參加演算法競賽人，同學們你們也別覺得他們有多NB，他們也就是level2的水平，水一水面試，刷刷題，打打比賽。會把問題套到具體演算法上，複製粘貼一下模板而已。一個智商正常勤快點的人什麼都不做刷一年題可以成為那90%的人。level3的人中很多很少寫代碼或者甚至不！會！寫代碼你造嗎？
其實還存在level4, 他們就是研究基礎數學的數！學！家！。他們中NB的人對著level3的人說：你們別搞了，你們搞的這些都是數學裡最非主流大家最不屑於搞的東西。呵呵。
貌似跑題啦，不過碼農還要說我不會演算法可是我有項目經驗啊， 其實項目經驗也只是多寫點代碼，多一點調試經驗，多知道幾個API而已，這還不一樣是低端嗎？ 唉，其實整個碼農行業 以及絕大多數行業 差不多都是這樣低端的存在 大家混口飯吃而已。
演算法不是沒用，只不過在大部分初級工作里用不到。
我很討厭數學，看見那些抽象的數字就會特別煩躁。。
碼農就碼農，沒什麼不服氣的，我就願意當個碼農，我也就是個碼農級別的。
覺得碼農和coder之間的關係就好像建築師和工人的關係。
建築師厲害，但是沒工人蓋房子能行嗎？
分個等級也沒什麼，大牛們繼續加油寫好用的框架。我們碼農就來負責給客戶實現需求。這樣不是挺好嗎？
公司招人我覺得需要先搞清楚自己究竟是想招一個大牛還是碼農。
假設一家公司某個軟體崗位需要招人，你如果作為面試官，肯定是希望找一個有相關背景的人。
比如招聘一個搜索引擎類的人才，面試的時候，肯定要問相關搜索演算法如何實現，各個演算法之間有何優劣，甚至讓你出示一下你在相關領域的論文等等。你說會讓你當時寫一段二叉樹排序么？
又比如招聘一個無線通信的基帶信號處理軟體工程師，面試問題肯定是64QAM信號如何解調，IRC演算法什麼情況會比MRC演算法靈敏度高2dB，信道編解碼中卷積如何處理，各種調製方式使用哪些演算法等等。你說會當場讓你寫一個矩陣求逆的代碼么？
面試時考演算法，只有三種情況：第一種是工作密切相關，這種情況下，問的演算法可就不是快速排序、二分查找這種本科生的東西了。
第二種情況，就是你的技術背景不匹配崗位要求。什麼樣的候選人不匹配崗位要求還會得到面試機會？本科應屆生（碩士以上基本會在本行業中有所建樹）。
對應屆生面試，真的想不出什麼好的面試題來考察能力。應屆生完全是一張白紙，你問他相關行業知識，這不是難為他么？而演算法是基礎，是基本功，是應屆生能力和崗位需求唯一能匹配的地方。
還有一種情況，就是這個崗位太新了，市場上沒有幾個業內人士。那想招個合適的人，只有面試演算法了。比如google就經常面試演算法（而且還特難）。
回到題主的問題，工作中的演算法是相當艱深的，每個演算法背後都是一堆paper。面試問本科應屆生肯定是問一些很簡單的演算法了。為何還讓候選人很生氣，我覺得主要還是因為很多面試官面試社招生也面試演算法了。
對於我自己，我作為面試官，如果是找個新手來培養，面試個排序啊的演算法還是很有用的；如果找個有相關背景的，問的問題都是圍繞崗位要求而展開的。每個行業的圈子都不大，就那麼些人，大家都發過paper，身上多少都有幾個專利，兜兩圈都能攀上關係，你說面試的時候出個快速排序，無論出題的還是做題的，老臉都沒處放。
說說我最近面試人時的經歷
1、應屆生：很好奇，現在應屆生的簡歷上為啥寫了N多條項目經驗。一旦問起，多數連項目的整體框架都說不清楚，再問及自己負責的模塊，要不就是很邊角的東西，要不連邊角都說不上。一般這種基本可以無視了。一般對於稍好的應屆生，我不會問太多項目經驗之類的，因為很多人在這方面很欠缺。學校里應以學習為主，所以我會問一些基礎的東西，比如簡歷上所述語言的一些語法、特性、數據結構之類的。能把這些說清楚，再能說明白一點小演算法的，應該就很不錯了。這些人至少在適當的時間在做適當的事情。有基礎，上手就會很快，帶這種新人應該不會很累。回想起我當年入行的艱辛，還是很樂意給新人一些機會的。
2、3年左右工作經驗：這類人有一定的開發能力，也積累了不少代碼經驗。對此類人士，我一般會關注簡歷上的項目內容，會問一些項目類型，所用到的關鍵技術，自己負責什麼，數據流程怎麼樣，有哪些核心技術，怎麼處理等細節，如果這些能說清楚，說明在簡歷上還是誠實的，可以加分。
3、3年以上：除了問上一條的內容外，還會問一些系統架構、對方擅長領域的一些技術等，因為這類人士技術很可能比樓主要牛，有時樓主也會把自己遇到的問題當成面試題拋給對方，看看對方有沒有好的解決思路。對於此類人士，樓主還是比較緊慎的，甚至還會查找一些面試者擅長技術的一些知識，提前做一番功課，不至於到時太丟人，樓主也是很愛面子滴。
歪題了。至於演算法，樓主會問一些，但都是簡單的，常用的，常識性的東西，不會問一些比較變態之類的。因為上次招的那個人（此君已被解僱）面試時，我另一同事問的一些演算法對答如流，後來得知此君有一本厚厚的面試寶典。實際上此君能力極差，差到啥程度，年紀比樓主大，工作經歷長，一個很簡單的功能，此君實現了一周多還沒弄好。期間樓主無數次告訴他該 怎麼做，邏輯怎麼處理，注意事項是啥，就差告訴他每句代碼怎麼寫了。最後樓主無奈地自己實現了，用兩個小時而已。由於人是同事同意錄用的，樓主勉強讓此君過了試用期，在其後工作中的表現甚至不如同期來的應屆生。最終解僱了事。
日薄西山……紙巾盒……我好像知道了點什麼……
話說現在的應屆生對於演算法的不重視，我認為有一部分原因是學校/學院對演算法的不重視。我所在的學院是軟體學院，關於演算法的課程，僅僅有一門選修課。
此外，期末的考核方式也有問題，只是在紙上寫一些選擇填空，計算，畫畫步驟，寫寫偽碼。最難的題目，也就是無空間優化版的 0-1 背包了。
其它課程的考核中，也幾乎沒有對演算法性能的要求，只要大家寫出功能就 OK。所以久而久之大家就缺少了某種精益求精的精神。
還有我覺得一些同學觀念有問題，總覺得實際項目當中大部分代碼對於演算法的要求不高。其實學習演算法一方面是掌握一些常用的演算法，另一方面是學會設計和分析自己寫的演算法。有的時候自己擼了一段代碼出來，雖然能用，但是可能性能經不起考驗。此外，就算項目中使用高深的演算法的代碼不多，但是這卻是一個區分優秀碼農和平庸碼農的地方啊。
推薦閱讀：