大型科技公司通常都主張必須進行算法面試，因為他們的規模過大，無法承受低效代碼帶來的巨額成本。但一次的算法面試真的能體現一個人真正的實力嗎？
作者 | Dan Luu
譯者 | 彎月，責編 | 屠敏
以下為譯文：
每當我問時尚科技大公司的人，算法測試有什麼必要時，通常他們都會說：「我們的系統過於龐大，我們不能允許任何人不小心編寫某個 O(n^2) 的算法而導致系統宕機。」這句話的可笑之處在於：儘管我為這些公司做出的很大一部分貢獻就是解決電話面試級別的算法問題，但我還是沒辦法通過面試！當我說這話的時候，人們常常以為我的意思是我的面試有一半都失敗了。實際上我面試失敗次數超過了一半。
當我將自己的面試經歷寫成文章時，有人認為我的文章太無聊了，因為我的很多面試都失敗了。他們認為，我應該將這些失敗的經歷總結成表格，因為沒人願意讀一篇長達一萬字的文章，而本章本身只是講述了一系列的失敗經歷。我大約經歷了40次面試，然而可能只通過了1-2次（甚至可以說是零）。
為了說明上述我提到的「電話面試級別的算法問題」，我們先來看幾個例子。
我曾在一家大公司任職，公司的某個團隊編寫了一個核心庫，實現了可變數組。在每次調整大小時，如果數組的後備存儲溢出，那麼這個實現就會添加固定數量的元素，並將舊數組複製到新分配的數組中——僅僅是一個稍大一點的數組。這是實現可變數組的經典反例，因為這樣做會導致調整數組大小所需的時間呈線性增長（而不是平攤常數）。這是平攤分析中最常提到的一個經典的例子。
可能有些人不熟悉大型科技公司電話面試的算法問題，我遇到過的問題包括：
-
一個「簡單」的編程/算法問題，也許之前還有一個「非常簡單」的熱身問題。
-
一系列「非常容易」的編程/算法問題。
-
一堆腦筋急轉彎問題（對於全面的人才來說這種問題很罕見，但是對於低級或與績效掛鈎的職位來說並不罕見）。
他們認為這類數組的實現是非常簡單的問題，因此被劃分到了「非常容易」的類別，通常在「真正」的電話面試問題中，這只是一個熱身問題，後來還有許多類似的簡單問題。然而，可變數組在這家公司的所有JVM代碼中，造成了大約1%的垃圾回收壓力（所有代碼中這個可變數組造成的內存分配占第二位），還造成了不可忽視的CPU占用率。幸運的是，他們沒有把這個實現當作通用的可變數組使用，只用於了一個半專用的程序，也因此「僅」造成了所有垃圾回收任務的1%。然而，如果面試的時候被問到這個問題，就讓人感覺好像它們絕大多數的團隊成員都能夠在面試中正確地實現這個功能。我能解決這個問題，而且解決這個問題後為我的老闆帶來的收益比我這輩子賺得錢都多。
這個問題占用的內存分配排在第二位，而排名第一的是將一對 long 值轉化為字節數組，這個實現同樣來自同一個核心庫。似乎他們編寫了這個操作的原因是，有人編寫（也許是複製粘貼）了一個哈希函數，其輸入為一個字節數組，後來又將這個函數修改成：接受兩個字節數組，並依次進行操作，因此這個哈希函數的接口為(byte[], byte[])。為了使用兩個 long 調用這個函數，他們使用了工具庫中的一個非常便利的轉換函數，將 long 轉換成 byte。這個函數除了分配 byte 並將 long 填充到其中外，還可以反轉 long 的字節（似乎這個函數本來的用途是將 long 值轉換成有序的網絡字節。）
不幸的是，想把這樣一個函數寫得更為合理是一項大工程，因此我的解決辦法是將哈希函數的接口變更為接受一對 long（而不是一對字節數組），然後讓這個函數執行字節反轉，而不是將其作為一個單獨的步驟執行（因為這個哈希函數已經打亂了字節的順序，因此不需要額外的工作）。由於去除了這些不必要的資源分配，我的老闆因此而獲得收益比我這輩子賺得錢都多。
理論上說，常數級別的提高速度並不是算法問題，但是算法面試中還是會出現這樣的問題。作為後續的算法問題，他們經常問我：「你能提高代碼的速度嗎？」這些問題的答案往往涉及簡單的優化，以及性能改善。
舉一個例子說明我在面試中遇到的問題：將ID保存成整數，但是根據題目的語境，你知道這個ID是緊密壓縮過的值，因此你可以將這些ID保存成比特。比特的面試問題與現實世界中存在大量冗餘的數組實現有所不同，因為在現實世界裡這個問題的解決方案與預期的答案相距甚遠，因此可能不會有人要求你進行常數級別的提高速度。更可能的是，在走到這一步的時候你的面試很可能已經失敗了。
下面這個例子來自另一個公司，BitFunnel （Bing中使用的搜索引擎）的配置問題，這是面試級別的算法問題的例子。
我無法在本文中通過寥寥幾筆說清楚這個解決方案，簡單來說，你需要配置一組布隆過濾器。方法之一是編寫一個黑盒優化函數，通過梯度下降來嘗試尋找最佳解決方案。據我所知，這種方法總是會產生一些奇怪的特性，而最終的配置也不會太理想，只能通過降低布隆過濾器的緊密程度（即投入更多資源，也就是更多錢）來解決這個問題。
為了創建更好的解決方案，你會發現 BitFunnel 中的基本操作相當於機率相乘，因此，對於任何特定配置，你只需要將多個機率相乘，即可確定該配置的執行方式。由於配置的空間並不是很大，因此只需要用幾個for循環，在可能的配置空間中進行疊代，然後挑選出最佳的配置集合。但這也不完全正確，因為機率相乘假設了一種現實中並不成立的獨立性，但這種方法似乎效果還不錯，就像樸素貝葉斯垃圾郵件過濾器也假設電子郵件中兩個單詞的出現機率是獨立的。如果你想要完整的解決方案，則需要詳細算出非獨立的機率，儘管這超出了面試的範圍。
以上就是我想到的三個例子，每次在總結最常見的十道面試題時，我總是會想到這些問題，如果我坐下來認真寫出每個經歷過的面試題，那麼可能會超過一百個。就我個人知道的其他人經歷過的考題，那麼肯定不止一百個。無論是本文提到的例子，還是我未能詳盡敘述的例子，這些考題都有以下共性：
-
這些問題都可以表述成面試問題。
-
如果表述成面試問題，則你必然希望相關團隊中的大多數人（或者所有人）都能夠在面試要求的時間內給出正確答案。
-
因解決這些問題而節省的年成本比我這輩子掙的錢都多。
-
我們可以合理地假設這些問題已經出現很長一段時間了，否則它們就不會作為面試題了。
在本文的開頭，我曾提到大型科技公司通常都主張必須進行算法面試，因為他們的規模過大，無法承受低效代碼帶來的巨額成本。根據我的經驗，我工作過的每家公司都有這樣的算法面試。為了招到有能力的人來解決工作中的算法問題，僅憑面試中的算法考題是行不通的。
原因之一在於，即使大公司的目的是為了設法確保員工能夠解決算法難題，那麼這種做法也會激勵許多甚至大多數開發人員避免將這種能力變成金錢。
上述例子的三個解決方案中，有兩個已用於生產，還有一個沒有。如果換一個團隊，而且我不固執地堅持下去的話（也就是說，並非是下面的情況之一：假設我有理由相信我的團隊會接受我的解決方案；或團隊需要我站出來提出解決方案；或者我固執地堅持到底，直到他們採用我的解決方案），我的解決方案得到實際應用的機率也就這麼多，即三分之二。
你可以執拗地說這個成功率（三分之二）已經很高了。如果我隨便加入了一個團隊，那麼很有可能效率既不是這個團隊的目標，也不是這個組織的目標。這個公司可能已經花費了大量的精力來激勵團隊實現各自的目標（否則制定目標的意義何在？），如果要求他們接受我的解決方案，那麼他們需要測試、集成、部署更改，還需要承擔部署風險（因為所有部署的風險都不可能為零）。那就等於說，我在要求團隊冒風險做一些對他們來說毫無價值的工作。儘管有時人們也會罔顧激勵措施，採用不同的解決方案，但他們不太可能花費大量的業餘時間來尋求效率的提高，他們會將正常的工作時間花在與團隊目標相符的工作上。
假設有一家公司的目標不是為了確保開發人員可以通過算法測驗，而是為了激勵開發人員使用相對高效的算法。我不認為在這種情形下上述三個問題會被遺留至今，經過了這麼多年，還未能得到解決。再假設有一家公司在評測代碼時會觀察調用頻率最高的代碼，以尋找計算最繁重的那一部分庫。在這兩種假設下，「竅門」不涉及任何算法問題，只需要多看就行了，完全可以通過激勵措施解決。第三個例子並非不可避免的，因為沒有標準的工具可以告訴你問題所在。然而，你也可以將結果歸結為某種算法問題，因為這個例子正是了IR領域獲得過「最佳論文獎」的某篇論文的核心部分，但實際上這個「技巧」只用到了高中數學，這意味著真正的技巧是，只要有足夠的時間，利用高中數學的方法就能解決。
在我工作過的公司中，的確有一家「不會在面試中問算法問題，他們更加重視那些對公司發展有利的方面」。在這家公司工作期間，我發現只有一個解決方案似乎可以滿足上述例子（如果這家公司規模更大，則可以滿足所有條件，但是由於這家公司的規模有限，所以提高效率並沒有那麼重要，雖然我付出了很多心血，但為公司帶來的年收益並不會超過我這輩子掙的錢）。
我認為，我只找到了這麼一個例子的主要原因在於，很多人認為他們的工作就是讓公司變得越來越好，所以能夠直接帶來高價值的解決方案根本不存在，因為系統就是這樣設計的，想找到改進的方面並不容易。雖然例外的情況很少，但是確實有人會努力做正確的事情，而不是被迫罔顧公司整體的利益而向眼前的利益屈服，這些人可能會搶在我之前就已經解決掉了這些算法問題。
這家公司的算法/編程部分面試比較容易，比主流技術大公司的電話面試容易多了，而且我們基本上沒有進行系統設計面試。
有一陣子，我們嘗試了一下現場算法面試，雖然很難，但是在大公司的電話面試中其實很常見。後來我們取消了這些面試題，因為我們面試過的畢業生中，沒人能答出這些問題（我們沒有給經驗豐富的候選人這樣的問題）。可能是我們公司的名聲不夠大，來我們公司面試的人都未能答出這些問題，所以我們根本無法像別家公司那樣，通過時髦的方法過濾候選人。在當代關於面試的討論中，我們的做法通常被稱為「降低標準」，但是我想不明白既然我們的工作所需的門檻很低（有時甚至沒有）的時候，為什麼我們要把門檻設得那麼高。而且，在有些情況下，雖然你想設置門檻，但門檻只有2寸高，人家可以輕鬆地邁過去。
從實際的生產力來看，這家公司是我工作過的公司中生產力最高的一家。我認為，其中的原因是文化上的，而且太複雜，無法在本文中進行全面探討，但我認為我們的討論有幫助性，因為我們了解到我們無法通過算法測驗篩選出完美的候選人，而且我們假設如果我們的文化是做正確的事，而不是專注於眼前的目標，那麼人們就會在工作中承擔相應的工作。
如果有些公司希望人們在工作中解決面試級別的算法問題，那麼他們可以通過激勵措施達成這一目標。為此，我們需要付出額外的努力或想別的辦法，而不是僅憑在白板上解決算法問題過濾面試者。
原文：https://danluu.com/algorithms-interviews/
本文為 CSDN 翻譯，轉載請註明來源出處。