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