最糟糕的編程面試題
多年前，我寫了一篇關于我所鄙視的某些類型的面試題。今天我想討論一個更具體的問題，而不僅是類型。我從來沒有問過自己這個問題，但我已經看有人在實際面試中提這個問題，我正式提名它為最糟糕的編程面試題。
在之前的公司里，有個同事經常問這個問題，那次是我***次在面試時聽到它。這家公司結對面試，兩個工程師，一個候選人。有一天，我和他作為一對，去面試一些杯具的應聘者。我覺得應聘者其實表現不錯，然后我的同事拋出了這個問題。應聘者結結巴巴地回答，很明顯他囧了。在面試后的聚會，所有面試他的工程師都向他豎起了大拇指，只有我搭檔反對雇用他，只因“任何稱職的工程師都應該能夠回答它”。他確鑿地說不能跟那個人共存。值得一提的是，這個故事有個大團圓結局，我們不顧我搭檔的抗議，還是招了那個人，并在幾個月內炒了我搭檔，而那個應聘者仍在那家公司，干得好好的。
無論如何，我認為有這個問題的面試都是“有問題”的，所以我想在這里說明為什么它幾乎是恐怖的一個面試題：
寫一個能檢測鏈表是否存在環路的函數。
看來像是的基本算法問題，對嗎？站起來，在白板上寫函數。很正常，對嗎？不是，這是不對的，別這么干。
1.這完全是不恰當的。
這是一個工作面試。你有一個實時的環境，跟你說話的人在面試著。緊張是很正常的。而那種帶有“靈關一閃”的智力題是最壞的問題。你的大腦將致力于思考“該死，我正搞砸這個面試”而不是關注手邊的問題。
人們喜歡“看到應聘者如何思考”，但智力題無助于此。正因為它是智力題。你只能希望智力題給你“恍然大悟”。有時我聽到人們想知道應聘者如何處理壓力，但你應該知道，面試中本來就是有壓力的。
問人難題完全是浪費時間，這樣做只是考察到應聘者以前有沒看過這題。或者說考察了他們的演技（當他們聽說過這問題并知道答案卻假裝沒聽說，然后裝模作樣逐步推導以得出答案）。
這條問題是最浪費時間的。你還問為什么？好，想象一下如果一個人真的是***次聽到這個問題，然后你期望他推出答案。
對于這條題，一般來說的“正確”的答案是龜兔算法，在鏈表頭放兩個指針，一個是一步走兩個節點，另一個則一步一點；如果走著走著指針指向同一個節點，那就代表有環路了。
當然，還有更簡單的答案，例如，將所有走過的節點標記為“走過”，或者從每個點出發，看能不能回答該點，又或者在遍歷過程中做哈希，看有沒有重復。但當你拋出這些答案時，面試官又會加條件，要求使用更少的內存或時間或不能改原本的數據結構。而***的答案就是龜兔。
是否一開始就該考慮到這么多？無論如何，看來你很覺得你能考慮周到。鏈表這種數據結構是1955年由Allen Newell，Cliff Shaw 和 Herbert A. Simon 發現的。而“正確”的鏈表環路檢測算法，則叫做“Floyd 環查找算法”，以紀念發現者Robert W. Floyd，那是1967年的事。
1955至1967之間，這個問題是開放的，就是說，無數考數學或計算機博士的人都可能將它寫進論文里。即使那么多人在鉆研著，這個問題還是12年無解。
你真的覺得你行嗎，用20分鐘，僅憑超越所有學者的壓力，搞定這個曾經12年無解的難題？看來是不行的，你覺得行，只不過是因為你看過答案，然后在面試中，你”似曾相識“、”靈關一閃“。
2.這完全是不切實際的
如果上面給的理由還不能讓你恥笑那個爛問題，那你再想想，這個問題是否真的有用于日常工作。
我的意思是：你怎么會在實際中碰到有環的鏈表？
我并不是說叫你故意搞出一個有指回自身的鏈表，而是說，無端端會有這樣的東西？
鏈表這種數據結構不是抽象的東西，棧或隊列才是，你或者會在一些抽象的數據結構中用到鏈表這種實在的東西。例如棧，你就用來壓入，彈出，查看，是吧？那怎么會造成環呢？沒有人想把它搞成一團的吧？
即使你自己寫個鏈表，你也不會想做出這種樣子。看下java的LinkedList類，你是無法從外部去操控它的next和prev的，你只能取得***個或***一個，添加節點到某一位置，按位置或值刪除節點。
看下java源碼就知道，真的沒有：
- private static class Entry <E> {
- E element;
- java.util.LinkedList.Entry<E> next;
- java.util.LinkedList.Entry<E> previous;
- Entry(E e, java.util.LinkedList.Entry<E> entry, java.util.LinkedList.Entry<E> entry1) {
- /* compiled code */
- }
- }
它是一個私有靜態類，你無法從外部實例化它。你不能直接操控next和prev，因為它們倆代表了鏈表的狀態，它們就該這樣被封裝起來。
如果你真的把鏈表搞成有環了，那說明你寫錯。寫錯的話，你***重新寫對它，而不是寫個“檢測環”的方法。
“檢測環”的方法就該這樣寫：
- public class LinkedList {
- public boolean containsCycle() {
- return false;
- }
- }
如果你的鏈表寫對的話，“龜兔算法”返回的結果也跟這個方法一樣。
現實中你是很少有機會親手寫個鏈表的，即使有，你也別寫個能造成環的方法。造成環的方法，只能是“留后門”，“元編程”，“反射”。既然是這樣故意的話，那么繞過你的“檢測環”也是輕而易舉的。
結論
很多面試題，都中了以上其中一點，太過困難或者與工作無關。
而這個問題，兩點都中了。
如果有人給到你滿意的答案，就說明那個人死記硬背，無他。因回答不了而被你否決的人，說不定還比你更適合這份實務。
鏈表環路檢測：別問了。
更新：有位評論者說如果問題問的是有向圖，且每個節點的出度最多只有，即是問“檢測這個有向圖有沒有環”。搞圖的話，你確實可能會向API用戶提供修改每點的指向的方法，這看上去符合實際。但是，還是那句話，你只是在考察應聘者把CS課程記住了多少，或者你只想隨便問問，又或者你想聽聽他說除了龜兔算法以外的低效算法。
原文鏈接： nomachetejuggling 翻譯： 伯樂在線 - unblock
