從一道面試題談?wù)勔痪€大廠碼農(nóng)應(yīng)該具備的基本能力

求職面試在絕大部分人來(lái)說(shuō)都是必不可少的，自己作為求職者也參與了不少面試（無(wú)論成功或者失?。鳛榧夹g(shù)面試官參與面試也有四五年的經(jīng)驗(yàn)，在面試過(guò)程中也見(jiàn)識(shí)到了各種各樣的人(有厲害的，也有奇葩的)。在這里也只想談?wù)勛约旱囊恍┛捶ǎ?strong>我說(shuō)的不一定對(duì)，有不同的意見(jiàn)可以留言參與討論。

面試本來(lái)就是一個(gè)雙向選擇的過(guò)程，面試官和候選人的地位本應(yīng)該是一個(gè)平等的位置，面試官希望通過(guò)簡(jiǎn)單的交流溝通可以對(duì)候選人的技術(shù)，溝通等有一定了解進(jìn)而確定候選人是否匹配相應(yīng)的職位。個(gè)人認(rèn)為一場(chǎng)成功的面試最好是能夠讓求職者和面試官都有一定的收獲（曾經(jīng)也遇到過(guò)在某次面試后，HR 告訴我有候選人特意跟她反饋要表達(dá)對(duì)面試官的感謝，因?yàn)樽屗苡惺斋@，這當(dāng)然還是讓我感到非常高興的），每次參與面試，也希望自己能達(dá)到這個(gè)目標(biāo)。對(duì)于候選人來(lái)說(shuō)能從面試過(guò)程了解自己的不足或者交流探討面試問(wèn)題；對(duì)于面試官來(lái)說(shuō)能了解候選人的技術(shù)和項(xiàng)目，在交流探討中也是一次學(xué)習(xí)和鞏固。 另外面試能否通過(guò)最終強(qiáng)調(diào)的是職位匹配，一個(gè)蘿卜一個(gè)坑，蘿卜太大或太小都不一定合適。所以有時(shí)候面試沒(méi)通過(guò)并不是候選人不夠優(yōu)秀，也有可能是候選人過(guò)于優(yōu)秀（例如本來(lái)只想招聘 P6，結(jié)果來(lái)了一個(gè) P8的候選人肯定不合適）。

因?yàn)槊嬖嚂r(shí)間有限，1個(gè)小時(shí)(一般情況)的時(shí)間很難去全面了解候選人的技術(shù)實(shí)力，因此在面試過(guò)程中很難做到絕對(duì)的公平。舉個(gè)簡(jiǎn)單的例子，面試官出一道題目，候選人 A 可能曾經(jīng)做過(guò)或見(jiàn)過(guò)，所以能夠比較輕松地回答出這個(gè)問(wèn)題，而候選人 B 沒(méi)有做過(guò)，雖然不能答出讓面試官滿意的答案，但 B 提供了一些解題的思路，雖然最終并沒(méi)有答出這道題目，這就一定說(shuō)明候選人 B 比 A 差么? 并不是吧。

下面就從這道題目說(shuō)起，這道題目是我在過(guò)往的面試中經(jīng)?？疾斓囊坏李}目。

實(shí)現(xiàn)一個(gè)函數(shù)，完成 開(kāi)根號(hào) 的操作，方法簽名如下：

double sqrt(int v, double t)

要求：

1. 不能調(diào)用系統(tǒng)庫(kù)函數(shù)，諸如 Math.sqrt(v) 之類的；

2. 假設(shè)計(jì)算出的結(jié)果為 r，要求滿足這個(gè)條件：  ，其中 是真實(shí)的值， t 為給定的一個(gè)誤差范圍，例如0.1等，即你計(jì)算出的值要在給定的誤差范圍內(nèi)。 

3. 實(shí)現(xiàn)語(yǔ)言不限，你條件可以比上述更加苛刻，但不能寬松。例如調(diào)用你的接口 sqrt(9, 0.21) 返回值屬于 [2.79, 3.21] 這個(gè)區(qū)間的任意一個(gè)都滿足條件。

看到這里，其實(shí)你可以 拿出筆和紙，嘗試解答一下，需要注意的是答案要滿足給定的誤差條件，歡迎溝通交流。其實(shí)這個(gè)題目是就是 leetcode 上原題稍加變化得到，做過(guò)的肯定覺(jué)得 leetcode 其他題目來(lái)說(shuō)相對(duì)比較簡(jiǎn)單。但沒(méi)做過(guò)也沒(méi)關(guān)系，如果在面試官的提示下能夠最終把這道題目解出來(lái)，在我看來(lái)也 OK 的，甚至有可能比刷過(guò)題記住解題答案的更好（當(dāng)然刷過(guò)題目本身的肯定會(huì)圍繞這個(gè)題目穿插其他小問(wèn)題的）。

其實(shí)剛開(kāi)始，我認(rèn)為這道題目比較簡(jiǎn)單，至少在給予提示后，理想情況下大部分一線coding的程序員都可以給出實(shí)實(shí)在在 code 的。然而“理想很豐滿，現(xiàn)實(shí)很骨感”，事實(shí)并非如此，然而在面試很很多人之后， 發(fā)現(xiàn)此道題目并不簡(jiǎn)單，如果你能寫出來(lái)，說(shuō)明你已經(jīng)比很多人優(yōu)秀了（至少在我過(guò)往的社招面試經(jīng)歷中）。 

當(dāng)被問(wèn)起這道題目之后，可能遇到的答案如下。

題目給出后，我一般首先明確候選人弄清楚了題目的含義然后會(huì)給一兩分鐘讓候選人先思考一下。

面試官：你有什么思路嗎？
求職者： 沒(méi)有啊。

可能候選人內(nèi)心OS是: “你出這樣的題目是不是有病啊，明明有 lib 函數(shù)可以直接用的”。(之前同組有其他小伙伴確實(shí)有遇到這樣的候選人，語(yǔ)言雖沒(méi)這樣夸張，大意是：實(shí)際工作中會(huì)出現(xiàn)這樣的問(wèn)題嗎? 我直接給你百度一個(gè)就行了)

在此強(qiáng)調(diào)，面試這道題目并不是想強(qiáng)調(diào)這個(gè)題目本身，期望以這道題目為契機(jī)，考察候選人在分析問(wèn)題和解決問(wèn)題的能力，在交流過(guò)程中所體現(xiàn)的邏輯推理和思維方式等，當(dāng)然最后也會(huì)看看實(shí)實(shí)在在的 Code，從編碼過(guò)程中看候選人的編程習(xí)慣，風(fēng)格等等。

也有候選人剛開(kāi)始抱著那個(gè)約束誤差范圍的不等式研究 N 久，然后沒(méi)有然后了的。剛開(kāi)始看這個(gè)條件當(dāng)然好，但如果這個(gè)不等式?jīng)]有思路可以先放一放，沒(méi)必要在那苦熬。

面試官：這樣吧，如果我問(wèn)題 根號(hào)10 等于多少？你怎么回答？
求職者：3點(diǎn)幾吧。
面試官：你怎么知道是3 點(diǎn)幾，因?yàn)槟阒?開(kāi)根號(hào)是3，想象一下，你也可以完全用程序幫忙模擬你大腦思考的過(guò)程。
求職者： 我再想想……

其實(shí)這里是希望提醒候選人，我們首先是要解題，然后才考慮效率。即不管用什么方法能夠給出一個(gè)答案的，這個(gè)時(shí)候候選人可能進(jìn)入下一個(gè)階段了。

在實(shí)際工作場(chǎng)景中其實(shí)也是一樣，遇到一個(gè)問(wèn)題，首先我們要想到的是如何解決這個(gè)實(shí)際問(wèn)題，有了最基礎(chǔ)的解決方案之后再談優(yōu)化。

實(shí)際面試過(guò)程中也有人是直接到這個(gè)階段的。

先用一個(gè)循環(huán)找到 r，使得 r^2 是離給定 v 最近的平方數(shù)，即你希望算根號(hào)10 ，先找到3，因?yàn)?^2=9 。

然后再用一個(gè)循環(huán)， 每次 r+=t ，直到 r^2 > v  為止。

面試官：這個(gè)方法從理論上講， 是一個(gè)可行的方案，設(shè)想一下，如果我的精度要求很高，希望計(jì)算的 v 也很大，如 sqrt(v = 10000000, t = 0.000001) 之類的，調(diào)用你這個(gè)方法效率是不是很低，這個(gè)時(shí)候應(yīng)該怎么優(yōu)化?
求職者：這樣的話，我這個(gè)方法效率確實(shí)比較低，不過(guò)可以這樣優(yōu)化，比如設(shè)置一個(gè)步長(zhǎng)，一次迭代后，如果沒(méi)有達(dá)到預(yù)期，可以不斷修改這個(gè)步長(zhǎng)來(lái)增大逼近真實(shí)值的速度，比如10倍誤差，100倍誤差等。

其實(shí)，在與候選人的不斷交流中可以看出候選人的 Problem Solving 的能力，這也是面試考察中的一點(diǎn)。例如關(guān)于上面問(wèn)題的優(yōu)化，也可能用于在實(shí)際工作中遇到的問(wèn)題。

例如，我們?cè)趯?shí)際工作中可能經(jīng)常會(huì)寫一些異步的回調(diào)通知接口等，這個(gè)接口可能是其他團(tuán)隊(duì)維護(hù)的，有可能由于網(wǎng)絡(luò)問(wèn)題等回調(diào)接口可能會(huì)失敗進(jìn)而需要重試，對(duì)于重試的機(jī)制其實(shí)就可以借鑒上面的“步長(zhǎng)”機(jī)制，第一次回調(diào)失敗， 我等待 1s 后重試，失敗再重試，也許間隔 1s 不太恰當(dāng)，是否可以修改等待的步長(zhǎng)，等待比如 5s，10s？等等再重試直到成功。為什么要這樣做? 也許對(duì)方 server 本來(lái)現(xiàn)在就處于峰值，你不停的重試不但沒(méi)有增加你接口調(diào)用成功的機(jī)會(huì)，反而增加對(duì)方 server 的負(fù)擔(dān)。

額，跑題了，回到這個(gè)問(wèn)題本身，繼續(xù)

面試官：恩，這樣做確實(shí)可以優(yōu)化。但從本質(zhì)上講，假設(shè)我們不考慮誤差的話，這個(gè)題目其實(shí)就是在一個(gè)有序的列表里面去搜索滿足條件的特定的值。剛剛你的方法是一個(gè)線性的搜索方案。常見(jiàn)的搜索還有其他什么嗎？

求職者：二分搜索？

面試官：對(duì)呀，你可以嘗試想想能否借用一下這個(gè)思路來(lái)解決這個(gè)問(wèn)題。

當(dāng)然，部分候選人提示二分后，就直接能夠 get 到點(diǎn)，并且能夠?qū)懗龆执篌w框架，但可能結(jié)束條件寫的有點(diǎn)問(wèn)題。

如果候選人還沒(méi)有思路，就會(huì)繼續(xù)

面試官：這樣理解吧，你剛剛的搜索整數(shù)部分的過(guò)程其實(shí)是線性的，一個(gè)一個(gè)數(shù)去暴力窮舉。借助二分的意思就是，比如算 根號(hào)10，你搜索范圍是 [0, 10] (其實(shí)除了幾個(gè)數(shù)之外范圍可以更小[0, v/2]，你能證明么?)。

• 因?yàn)?^2 = 25 > 10 ， 所以 r 屬于[0, 5)   

• 因?yàn)?5/2) ^2 = 6.25 < 10 ， 所以 r 屬于 (2.5, 5)   

• 因?yàn)?3.75^2 = 14.0625 > 10) ，所以 r 屬于 (2.5, 3.75)   

• 繼續(xù)，如果你結(jié)束條件不太確定，可以暫時(shí)不管…

提示到這里，感覺(jué)已經(jīng)相對(duì)比較明顯了。

面試官： 你現(xiàn)在明白了嗎？
求職者：明白了。
面試官：那你寫一下代碼吧。

一個(gè)二分查找，算法思路都結(jié)合例子講一遍了，在候選人回答明白的情況下，理想當(dāng)中，作為一線開(kāi)發(fā)者寫出來(lái)應(yīng)該不成問(wèn)題吧。然而…理想和現(xiàn)實(shí)還是有差距的。
很多人都喜歡用遞歸寫，可是很多人遞歸里面的最重要的結(jié)束條件都木有， 一些邊界條件等等都木有。所以一般情況下，代碼寫完后，我會(huì)讓候選人自己寫測(cè)試用例。

面試官：寫好了是吧，你寫幾個(gè)測(cè)試用例吧，假設(shè)這個(gè)接口是別人寫的，你應(yīng)該從哪幾個(gè)角度去測(cè)試。
求職者：sqrt(-4, 0.21)，哎呀，我這里忘了判斷了。改一下代碼。
求職者：sqrt(0, 0.21)，sqrt(4, 0.21)… 還有問(wèn)題，再改改。
面試官：……

為什么要?jiǎng)e人提示要測(cè)試用例，才去 check 自己寫的代碼的正確性呢。有的候選人寫的代碼，就不拿一些異常情況去 check，就用上面講的 sqrt(10, 0.21) 的例子都得不到預(yù)期結(jié)果。

能夠到達(dá)這一個(gè)步驟的人已經(jīng)較少了，如果你有較全測(cè)試用例和邊界條件的判斷，再加上后面的結(jié)束條件能夠正確，基本上這道題目就算滿意了。

本質(zhì)上講，這個(gè)算法就是一個(gè)迭代逼近的過(guò)程，用二分的思路后，關(guān)鍵就在于什么時(shí)候結(jié)束。 題目中已經(jīng)給了誤差條件  ，難點(diǎn)在于其中的不知道，不太方便直接進(jìn)行計(jì)算判斷。不少人用一個(gè)另外的結(jié)束條件來(lái)進(jìn)行了判斷即：  ，其實(shí)這兩個(gè)條件是不一樣的。

對(duì)于這個(gè)結(jié)束條件，你有什么看法嗎? 能證明你的想法嗎?

當(dāng)然本題還有一些其他的數(shù)學(xué)解法，例如用牛頓迭代法，梯度下降法(最速下降法)，泰勒公式展開(kāi)等等。如果候選人能想到這些，說(shuō)明他還是有一定數(shù)學(xué)基礎(chǔ)的，如果愿意可以讓他講講。（考察這道題目本意并不是期望候選人用這些數(shù)學(xué)方法解的。）

對(duì)于這道題目，你有什么比較好的思路嗎?  歡迎留言參與討論。

1. 問(wèn)：為什么題目中的 v 的類型是 int？
   答：還真沒(méi)有理由，double 也無(wú)所謂，可能僅僅是因?yàn)?leetcode 上原題計(jì)算的數(shù)是 int 吧。

2. 問(wèn)：我能正確答對(duì)這道題目就一定能通過(guò)這次面試嗎？
   答：強(qiáng)調(diào)一下，面試中考察這樣一個(gè)題目，并不是僅僅考察這道題目本身，不是說(shuō)你將這道題做對(duì)了，就能通過(guò)面試，反之也不是說(shuō)你沒(méi)做對(duì)這道題目就一定不能通過(guò)我們的面試。我們通過(guò)這道題目為契機(jī)，希望考察的是候選人在分析問(wèn)題解決問(wèn)題的能力，在交流過(guò)程中所體現(xiàn)的邏輯推理和思維方式等，當(dāng)然也有最后實(shí)實(shí)在在的 code。

3. 問(wèn)：這不是一道數(shù)學(xué)題目嗎，為什么程序員面試需要考察這樣的數(shù)學(xué)問(wèn)題？
   答：同上，不是考察這道題目本身。另外，這也可以說(shuō)不是一道數(shù)學(xué)題目，當(dāng)然能用數(shù)學(xué)的方式解答。候選人能用數(shù)學(xué)的方式解答也算正確。

4. 問(wèn)：二分是這道題目的標(biāo)準(zhǔn)答案嗎？我能用其他解法嗎？
   答：同上，題目沒(méi)有標(biāo)準(zhǔn)答案，就算你用最暴力的算法搜索出來(lái)也是正確的解法，其他數(shù)學(xué)方法也對(duì)。

5. 問(wèn)：這道題目這么簡(jiǎn)單，牛頓迭代分分鐘秒掉，是不是太簡(jiǎn)單了？
   答: 給你點(diǎn)贊。

6. 問(wèn)：這題目在說(shuō)什么，我搞了半天沒(méi)看懂，這TM是啥？
   答：如果確實(shí)認(rèn)真看完整篇文章或跟面試官交流了那么久，還是根本不明白這到底說(shuō)的是一個(gè)什么問(wèn)題。那就別管了吧，隨他去吧，可能不是目標(biāo)用戶而已。

7. 問(wèn)：我在實(shí)際工作中根本就不會(huì)遇到這樣的問(wèn)題，你問(wèn)這個(gè)有什么用？
   答：同第2條答案。

8. 問(wèn)：你們公司還缺人么，面試會(huì)考察哪些點(diǎn)?
   答：有興趣或者有其他問(wèn)題可以戳我郵箱，郵箱地址：aUB0YW5nbGVpLm1l。 面試考察可能會(huì)涉及：CS 基礎(chǔ)/Code/數(shù)據(jù)結(jié)構(gòu)和算法/解決問(wèn)題/項(xiàng)目經(jīng)驗(yàn)/系統(tǒng)設(shè)計(jì)/溝通團(tuán)隊(duì)協(xié)作等等。

   
   

本文題目是“從一道面試題談?wù)勔痪€大廠碼農(nóng)應(yīng)該具備的基本能力”，其實(shí)，上面大部分內(nèi)容只談到了這道題目本身(也穿插了一些對(duì)這道題目的分析和理解)。上述題目的場(chǎng)景是社招面試中的，對(duì)于這樣的題目來(lái)說(shuō)校招的反饋會(huì)更好。因?yàn)樵谛Ｉ赡軐?duì)于工作經(jīng)驗(yàn)，項(xiàng)目經(jīng)驗(yàn)等比較欠缺，所以只好用一些比較固定的算法來(lái)面試進(jìn)行篩選（本質(zhì)上跟學(xué)?？荚嚊](méi)有太大的區(qū)別）。 

但這種類似的題目在社招場(chǎng)景下就完全不適用嗎？社招的的同學(xué)寫不出來(lái)就有很充分的理由嗎？或許你在工作場(chǎng)景中不會(huì)遇到實(shí)際這種題目，但我其實(shí)想表達(dá)的是，作為在最前線寫代碼的碼農(nóng)，在別人講解了二分算法且自己也能理解的情況下，能寫出這個(gè)二分算法應(yīng)該不算太難？相當(dāng)于一個(gè)需求，大家討論了算法實(shí)現(xiàn)和解法，需要你把它變成能跑的 code 而已。

其實(shí)這篇文章最開(kāi)始叫“從一道面試題談?wù)勔痪€碼農(nóng)應(yīng)該具備的基本能力”，幾年前發(fā)出來(lái)被噴了，后來(lái)想想似乎被噴也有點(diǎn)道理，因?yàn)樵谌粘Ｓ行﹫?chǎng)景下，“復(fù)制粘貼”工程師貌似也夠用了，遇到問(wèn)題有更高水平的人來(lái)幫你解決就行，大家都一樣的話，怎么體現(xiàn)高手水平呢？但從用人單位角度想，當(dāng)然是更希望招聘更加優(yōu)秀的選手，怎樣體現(xiàn)優(yōu)秀呢？候選人基數(shù)太大，怎么篩選，其實(shí)也就“高考”一樣嘛，通過(guò)“考試”擇優(yōu)錄取而已。

我們就不去討論是否每個(gè)寫代碼的人都需要有這樣的能力（好像答案也是顯而易見(jiàn)并不是）。但我建議咱們一線的程序員們（特指有上進(jìn)心的一線程序員）應(yīng)該對(duì)一些基本的數(shù)據(jù)結(jié)構(gòu)和算法有所了解，對(duì)常見(jiàn)的算法復(fù)雜度有所了解? 或者至少應(yīng)該有這樣的追求吧？比如二分搜索復(fù)雜度為什么是 。之前遇到過(guò)比如有的候選人，Java 開(kāi)發(fā)七八年經(jīng)驗(yàn)了，簡(jiǎn)歷描述精通 Java，但不清楚 ArrayList, HashMap 內(nèi)部大概是怎么做的（我理解，不管什么都需要知道大致的實(shí)現(xiàn)原理才有可能去優(yōu)化遇到的各種性能問(wèn)題吧？）。還有什么熟練掌握 Vim，結(jié)果其實(shí)就是熟練掌握如何打開(kāi)和關(guān)閉 vim。還有的候選人口頭表達(dá)頭頭是道，結(jié)果落實(shí)到寫代碼就根本下不了筆。

有時(shí)候感覺(jué)大部分程序員都被大量的需求壓迫著，被產(chǎn)品經(jīng)理催促著，倉(cāng)促地碼著繁瑣的業(yè)務(wù)代碼，不斷的改著 Bug 又引入新的 Bug。 業(yè)務(wù)代碼重要么，當(dāng)然重要（代碼就是服務(wù)于具體業(yè)務(wù)的），但同時(shí)也還是希望我們不要拋棄一些基礎(chǔ)的東西，多培養(yǎng)一下我們的編程素養(yǎng)。我們?cè)谟镁幊陶Z(yǔ)言，利用各種工具來(lái)實(shí)現(xiàn)我們想要達(dá)到的目的的時(shí)候，能做到“知其然，知其所以然”豈不更好？

特別推薦一個(gè)分享架構(gòu)+算法的優(yōu)質(zhì)內(nèi)容，還沒(méi)關(guān)注的小伙伴，可以長(zhǎng)按關(guān)注一下：
長(zhǎng)按訂閱更多精彩▼
如有收獲，點(diǎn)個(gè)在看，誠(chéng)摯感謝