騰訊2016研發(fā)工程師筆試題二這份卷子到底在考什么以及我復(fù)盤后悟出的解題套路每年校招季總有讀者在后臺(tái)問(wèn)我騰訊研發(fā)工程師的筆試題到底該怎么準(zhǔn)備老實(shí)說(shuō)單獨(dú)刷“某一年真題”的意義不大但如果你拿到的是2016年那一批二卷認(rèn)真拆一遍反而很有價(jià)值——因?yàn)槟且荒甑念}目風(fēng)格非常典型不考偏題怪題四平八穩(wěn)地覆蓋了C/C內(nèi)存布局、指針與數(shù)組的糾纏、操作系統(tǒng)進(jìn)程與線程、TCP協(xié)議細(xì)節(jié)、數(shù)據(jù)結(jié)構(gòu)的復(fù)雜度邊界。換句話說(shuō)它考的不是你背了多少API而是你對(duì)計(jì)算機(jī)基礎(chǔ)到底有沒(méi)有“真的懂”。這篇文章我就以2016研發(fā)工程師筆試題二為線索把這份卷子背后涉及的考點(diǎn)掰開揉碎講一遍。無(wú)論你是正在準(zhǔn)備校招的應(yīng)屆生還是工作幾年想回頭補(bǔ)基礎(chǔ)的工程師這篇文章都能幫你建立一套“看到題目就知道它在考什么”的反射框架。1. C/C指針與數(shù)組2016年那批題里最陰險(xiǎn)的“送分題”陷阱先說(shuō)一個(gè)我在復(fù)盤時(shí)印象最深的點(diǎn)這份卷子C/C部分的題目表面看全是基礎(chǔ)實(shí)際上處處埋雷。尤其是指針和數(shù)組的關(guān)系幾乎每年必考而2016年二卷里的相關(guān)題目恰恰是區(qū)分“背過(guò)書”和“真會(huì)”的分水嶺。1.1 sizeof、strlen與數(shù)組名退化一個(gè)字節(jié)數(shù)引發(fā)的血案當(dāng)年的選擇題里有一道非常經(jīng)典的題定義一個(gè)字符數(shù)組char str[] Hello問(wèn)sizeof(str)和strlen(str)分別是多少。看起來(lái)簡(jiǎn)單但很多人會(huì)栽在“數(shù)組名什么時(shí)候退化成指針”這個(gè)點(diǎn)上。sizeof(str)在數(shù)組定義所在的作用域內(nèi)返回的是整個(gè)數(shù)組占用的字節(jié)數(shù)。Hello是字符串字面量末尾隱含一個(gè)\0所以數(shù)組實(shí)際大小是6個(gè)字節(jié)。而strlen(str)是運(yùn)行時(shí)函數(shù)它從首地址開始數(shù)一直到遇到\0為止所以返回值是5。如果是void func(char arr[])在函數(shù)參數(shù)里char arr[]和char* arr是完全等價(jià)的此時(shí)sizeof(arr)返回的是指針大小64位平臺(tái)是8字節(jié)32位平臺(tái)是4字節(jié)而不是數(shù)組大小。這是數(shù)組名退化的典型場(chǎng)景數(shù)組名作為sizeof的操作數(shù)時(shí)不退化作為函數(shù)實(shí)參時(shí)退化成指向首元素的指針作為表達(dá)式參與運(yùn)算時(shí)也退化。很多人在筆試?yán)飳戝e(cuò)不是因?yàn)椴恢纒izeof和strlen的區(qū)別而是沒(méi)搞清“數(shù)組名在什么場(chǎng)景下不退化”。我復(fù)盤2016年這道題時(shí)專門把這三種情況列了一遍場(chǎng)景數(shù)組名行為sizeof結(jié)果數(shù)組定義作用域內(nèi)代表整個(gè)數(shù)組整個(gè)數(shù)組字節(jié)數(shù)函數(shù)參數(shù)傳遞退化為指針指針大小表達(dá)式運(yùn)算退化為首元素地址按指針處理這里的關(guān)鍵是sizeof是編譯期運(yùn)算符它在編譯時(shí)就能確定結(jié)果而strlen是庫(kù)函數(shù)必須在運(yùn)行時(shí)掃描內(nèi)存。理解這一點(diǎn)后你就能推斷出sizeof不會(huì)觸發(fā)數(shù)組名退化因?yàn)樗鼔焊恍枰罃?shù)組首地址只需要知道類型。1.2 指針運(yùn)算與二維數(shù)組*(a1)[2]這類表達(dá)式怎么拆2016年二卷里還有一道讓我印象深刻的二維數(shù)組題大意是定義int a[3][4]問(wèn)*(a1)[2]或者*(*(a1)2)這類表達(dá)式的值是什么。這種題的本質(zhì)是考察a、a[0]、a[0][0]在類型上有什么區(qū)別。核心規(guī)律只有一條數(shù)組名在表達(dá)式中退化指向首元素而二維數(shù)組的首元素是a[0]a[0]又是一個(gè)一維數(shù)組。所以a的類型是int (*)[4]即指向包含4個(gè)int的一維數(shù)組的指針a1指向a[1]也就是整個(gè)第二行*(a1)取出第二行這個(gè)數(shù)組類型退化為int*指向a[1][0]*(a1)2就是在第二行內(nèi)偏移2個(gè)int指向a[1][2]*(*(a1)2)最終取出a[1][2]的值。最容易錯(cuò)的寫法是*(a1)[2]。這里要特別注意運(yùn)算符優(yōu)先級(jí)[]的下標(biāo)優(yōu)先級(jí)高于*解引用所以*(a1)[2]實(shí)際上等價(jià)于*((a1)[2])即先做下標(biāo)運(yùn)算(a1)[2]這等價(jià)于a[3]再解引用就是a[3][0]。這已經(jīng)越界了——a[3]超出了a[0]到a[2]的范圍。我在給新人講這道題時(shí)都會(huì)強(qiáng)調(diào)一個(gè)習(xí)慣遇到復(fù)雜表達(dá)式先畫括號(hào)再翻譯成“指針往哪走、走幾步”。不要試圖心算筆試時(shí)草稿紙上畫一個(gè)二維數(shù)組的內(nèi)存格子圖比什么都管用。1.3 筆試題里的C對(duì)象模型內(nèi)存布局與虛函數(shù)指針2016年二卷的C部分考了一道帶虛函數(shù)的類繼承題。這類題考察的核心是C對(duì)象模型一個(gè)對(duì)象的內(nèi)存布局是什么樣的虛函數(shù)指針?lè)旁谀睦锒嘀乩^承時(shí)怎么偏移。簡(jiǎn)單說(shuō)一個(gè)類如果含有虛函數(shù)編譯器會(huì)給這個(gè)類生成一張?zhí)摵瘮?shù)表vtable每個(gè)對(duì)象里自動(dòng)增加一個(gè)虛函數(shù)指針vptr指向這張表。對(duì)象的內(nèi)存布局通常是vptr在最前面低地址然后是成員變量。繼承時(shí)如果子類覆蓋了父類的虛函數(shù)子類的vptr指向的虛函數(shù)表里對(duì)應(yīng)表項(xiàng)會(huì)被替換為子類的實(shí)現(xiàn)。筆試中常見的考法有兩種問(wèn)sizeof一個(gè)含有虛函數(shù)的對(duì)象是多少。比如一個(gè)類有int a和virtual void f()在64位平臺(tái)下int占4字節(jié)vptr占8字節(jié)由于對(duì)齊對(duì)象大小是16字節(jié)不是12字節(jié)因?yàn)橐獙?duì)齊到8字節(jié)邊界。問(wèn)通過(guò)基類指針調(diào)用虛函數(shù)時(shí)實(shí)際調(diào)用的是哪個(gè)版本。這考察的是動(dòng)態(tài)綁定如果函數(shù)是虛的調(diào)用走vptr查表如果不是虛的編譯期根據(jù)靜態(tài)類型決定。這類題目說(shuō)難不難但很考驗(yàn)?zāi)阌袥](méi)有真正讀過(guò)對(duì)象布局。我建議備考時(shí)拿gcc的-fdump-class-hierarchy編譯選項(xiàng)把類的布局dump出來(lái)看一眼一目了然。比死記硬背“vptr在對(duì)象頭”要可靠得多。1.4 復(fù)盤心得為什么C/C在騰訊筆試題里占比這么重從2016年這批題目來(lái)看C/C相關(guān)考點(diǎn)占了近三分之一的分值。這和騰訊的技術(shù)棧選擇有直接關(guān)系——很多底層組件、網(wǎng)絡(luò)框架、游戲引擎都是用C/C寫的研發(fā)工程師如果連內(nèi)存和指針都玩不轉(zhuǎn)后續(xù)培養(yǎng)成本會(huì)非常高。所以筆試階段他們就會(huì)用這些“基礎(chǔ)但易錯(cuò)”的題目做過(guò)濾。備考時(shí)不要只刷LeetCode一定要專門補(bǔ)一遍C/C的語(yǔ)言細(xì)節(jié)特別是《深入理解計(jì)算機(jī)系統(tǒng)》第三章《C Primer》的前半部分把指針、數(shù)組、內(nèi)存布局、虛函數(shù)這幾塊徹底吃透。2. 操作系統(tǒng)與Linux進(jìn)程、線程與內(nèi)存分布這些知識(shí)點(diǎn)是2016年卷子的“半壁江山”如果說(shuō)C/C是騰訊筆試的第一大考點(diǎn)那操作系統(tǒng)絕對(duì)能排第二。2016研發(fā)工程師筆試題二里進(jìn)程與線程、內(nèi)存管理、死鎖、Linux命令這些題目大概占了四分之一。這一節(jié)我重點(diǎn)復(fù)盤幾類高頻題目和它們背后的原理。2.1 進(jìn)程和線程一個(gè)fork()出來(lái)的問(wèn)題能繞暈多少人我記得那份卷子里有一道典型的fork題程序一開始調(diào)用一次fork()然后父進(jìn)程和子進(jìn)程分別再調(diào)用一次fork()問(wèn)最后總共有多少個(gè)進(jìn)程。這種題考察的核心是fork的語(yǔ)義fork調(diào)用一次返回兩次父進(jìn)程返回子進(jìn)程PID子進(jìn)程返回0。解題的正確姿勢(shì)是畫進(jìn)程樹。假設(shè)進(jìn)程P0開始P0調(diào)用第一次fork產(chǎn)生P1此時(shí)進(jìn)程數(shù)變?yōu)?P0和P1各自繼續(xù)執(zhí)行到第二次forkP0產(chǎn)生P2P1產(chǎn)生P3進(jìn)程數(shù)變?yōu)?。所以答案是4個(gè)進(jìn)程。但實(shí)際筆試題目會(huì)比這個(gè)復(fù)雜比如可能在fork之后還有if分支子進(jìn)程和父進(jìn)程走不同的代碼路徑或者嵌套多個(gè)fork。這時(shí)候唯一可靠的方法就是逐層畫樹不要試圖心算。還有一個(gè)高頻考點(diǎn)是fork之后變量是否共享。很多人以為fork出來(lái)的子進(jìn)程和父進(jìn)程共享所有變量這是錯(cuò)的。fork采用的是寫時(shí)拷貝COW機(jī)制剛fork完時(shí)子進(jìn)程和父進(jìn)程確實(shí)指向同一份物理內(nèi)存頁(yè)但只要有一方嘗試寫入內(nèi)核就會(huì)為它分配新的物理頁(yè)并拷貝內(nèi)容。所以從程序員的視角看fork之后父子進(jìn)程的地址空間是隔離的子進(jìn)程對(duì)變量的修改不會(huì)影響父進(jìn)程。我在講解時(shí)會(huì)用一個(gè)生活化的類比f(wàn)ork就像復(fù)印一份文檔復(fù)印完兩人各拿一份你用筆在你的復(fù)印件上寫東西不會(huì)影響我手上的原件。雖然底層在寫之前其實(shí)是共享同一張紙但你一落筆它就自動(dòng)復(fù)制了。這個(gè)機(jī)制理解透了遇到“fork后的全局變量”這類題就永遠(yuǎn)不會(huì)錯(cuò)。2.2 同步與互斥信號(hào)量、互斥鎖和死鎖的四個(gè)必要條件2016年卷子里有一道經(jīng)典的生產(chǎn)者消費(fèi)者問(wèn)題要求用信號(hào)量寫出偽代碼并解釋為什么這樣設(shè)計(jì)可以避免死鎖和競(jìng)態(tài)。這類題的解題框架是固定的生產(chǎn)者要“先申請(qǐng)空緩沖區(qū)信號(hào)量再申請(qǐng)互斥鎖”消費(fèi)者要“先申請(qǐng)滿緩沖區(qū)信號(hào)量再申請(qǐng)互斥鎖”。這里有一個(gè)容易忽略的細(xì)節(jié)為什么必須先申請(qǐng)資源信號(hào)量、后申請(qǐng)互斥鎖因?yàn)槿绻秧樞蚍催^(guò)來(lái)——先鎖緩沖區(qū)再等空位——一旦緩沖區(qū)滿了生產(chǎn)者會(huì)拿著鎖阻塞等待消費(fèi)者又進(jìn)不去緩沖區(qū)消費(fèi)就死鎖了。死鎖的四個(gè)必要條件——互斥、持有并等待、不可剝奪、循環(huán)等待——是必背內(nèi)容但更重要的是遇到題目會(huì)判斷。比如“兩個(gè)線程各自持有一把鎖然后嘗試獲取對(duì)方的鎖”這就是典型的循環(huán)等待。再比如“銀行家算法”的題目考察的是如何通過(guò)資源分配的安全性檢查避免系統(tǒng)進(jìn)入不安全狀態(tài)。我在做這道題復(fù)盤時(shí)最深的體會(huì)是筆試?yán)锟妓梨i從來(lái)不直接問(wèn)“什么是死鎖”而是給出一個(gè)并發(fā)場(chǎng)景讓你分析是否可能死鎖或者讓你寫出不會(huì)死鎖的同步代碼。所以備考時(shí)要多看經(jīng)典并發(fā)場(chǎng)景生產(chǎn)者消費(fèi)者、讀者寫者、哲學(xué)家就餐每一道都要能獨(dú)立默寫偽代碼并說(shuō)清楚每個(gè)信號(hào)量初始值為什么是這個(gè)數(shù)。2.3 Linux基礎(chǔ)命令與系統(tǒng)編程筆試中“題面最短、信息量最大”的部分2016年二卷的Linux題也很有意思比如給出某個(gè)命令的執(zhí)行結(jié)果讓你反推命令是什么或者問(wèn)某個(gè)命令的某個(gè)參數(shù)是干嘛的。這類題本質(zhì)考的是經(jīng)驗(yàn)積累不抱佛腳很難拿分。高頻的Linux命令考察點(diǎn)包括grep文本搜索常配合-v反選、-E擴(kuò)展正則、-r遞歸搜索awk按列處理文本awk {print $1, $3}這種是最基礎(chǔ)的sed流編輯器筆試常考s/old/new/g這種替換語(yǔ)法ps和top進(jìn)程查看ps -ef、top -H顯示線程是出現(xiàn)過(guò)的高頻寫法netstat/ss端口與連接狀態(tài)查看筆試喜歡讓你找出監(jiān)聽某個(gè)端口的進(jìn)程chmod權(quán)限修改chmod 755 file的含義要含得清清楚楚。我見過(guò)太多人在筆試?yán)飹煸谶@類題上原因不是不會(huì)Linux而是沒(méi)有系統(tǒng)整理過(guò)命令的常用參數(shù)。這里我建議準(zhǔn)備一個(gè)在線速查表把所有高頻命令、高頻參數(shù)記一遍不用背全部但常見的幾十個(gè)參數(shù)一定要看到就能說(shuō)出用途。2.4 內(nèi)存管理?xiàng)！⒍选⑷謪^(qū)、常量區(qū)一個(gè)對(duì)象到底活在哪個(gè)區(qū)操作系統(tǒng)和C/C經(jīng)常被放在一起考的一個(gè)點(diǎn)是內(nèi)存分區(qū)。2016年卷子里有一道題給了一段代碼問(wèn)某個(gè)變量、某個(gè)指針、某個(gè)字符串常量分別存在哪個(gè)區(qū)域。這里我總結(jié)一套通用判斷流程如果是函數(shù)內(nèi)定義的普通局部變量在棧區(qū)stack如果是malloc/new申請(qǐng)的在堆區(qū)heap指針變量本身在棧上如果指針是局部變量的話如果是函數(shù)外的全局變量或static修飾的變量在全局區(qū)/靜態(tài)區(qū).data段或.bss段如果是字符串字面量一般在只讀常量區(qū).rodata編譯器通常會(huì)把它們放到只讀段。有一個(gè)經(jīng)典誤區(qū)需要特別提醒char *p hello和char arr[] hello完全不同。前者p指針在棧上假設(shè)是局部變量但它指向的字符串字面量在只讀常量區(qū)試圖p[0] H會(huì)觸發(fā)未定義行為通常是段錯(cuò)誤后者arr是棧上數(shù)組字符串內(nèi)容被拷貝到棧里修改arr[0]是合法的。這一類題在筆試中屬于“一分都不能丟”的基礎(chǔ)題但丟分率極高。復(fù)盤2016年這批題目時(shí)我發(fā)現(xiàn)錯(cuò)誤幾乎全部出在“沒(méi)區(qū)分指針變量本身和它指向的內(nèi)存區(qū)域”上。記住指針變量自己的位置和它指向的位置是兩回事答題時(shí)分開判斷。3. 計(jì)算機(jī)網(wǎng)絡(luò)與數(shù)據(jù)結(jié)構(gòu)騰訊筆試題里最“實(shí)用”的一趴考的是你寫沒(méi)寫過(guò)真實(shí)代碼2016研發(fā)工程師筆試題二里的網(wǎng)絡(luò)題和數(shù)據(jù)機(jī)構(gòu)題我個(gè)人認(rèn)為是整份卷子里性價(jià)比最高的部分。為什么因?yàn)榫W(wǎng)絡(luò)題只要你理解TCP/IP的分層思想很多題可以從原理上推導(dǎo)出來(lái)不需要死記硬背而數(shù)據(jù)結(jié)構(gòu)題只要刷過(guò)一定量的LeetCode基本都能找到思路。3.1 TCP三次握手與四次揮手不只是背狀態(tài)還要理解為什么騰訊筆試的網(wǎng)絡(luò)題幾乎每年都會(huì)考TCP。2016年二卷里有一道連線題要求把TCP連接建立和斷開過(guò)程中的狀態(tài)變換排序。本質(zhì)上考的就是三次握手和四次揮手的狀態(tài)遷移。三次握手客戶端發(fā)送SYN進(jìn)入SYN_SENT狀態(tài)服務(wù)端收到SYN回復(fù)SYNACK進(jìn)入SYN_RCVD狀態(tài)客戶端收到SYNACK回復(fù)ACK進(jìn)入ESTABLISHED狀態(tài)服務(wù)端收到ACK后也進(jìn)入ESTABLISHED。四次揮手主動(dòng)關(guān)閉方發(fā)送FIN進(jìn)入FIN_WAIT_1被動(dòng)關(guān)閉方回復(fù)ACK進(jìn)入CLOSE_WAIT主動(dòng)方收到ACK進(jìn)入FIN_WAIT_2被動(dòng)方發(fā)送完數(shù)據(jù)后發(fā)送FIN進(jìn)入LAST_ACK主動(dòng)方回復(fù)ACK進(jìn)入TIME_WAIT等2MSL后關(guān)閉被動(dòng)方收到ACK后進(jìn)入CLOSED。很多資料只讓背狀態(tài)名但筆試真正想考察的是你是否理解為什么揮手需要四次而不是三次因?yàn)門CP是全雙工的每個(gè)方向上的連接必須單獨(dú)關(guān)閉。發(fā)送FIN只表示“我這邊沒(méi)有數(shù)據(jù)要發(fā)了”但不代表“我不接收你的數(shù)據(jù)了”所以被動(dòng)方要先ACK等自己的數(shù)據(jù)發(fā)完再FIN。還有一種更細(xì)的考法為什么主動(dòng)關(guān)閉方要進(jìn)入TIME_WAIT并且等2MSL原因有兩個(gè)一是確保最后一個(gè)ACK能被對(duì)方收到如果丟了可以重發(fā)二是讓舊連接的所有報(bào)文在網(wǎng)絡(luò)中自然消失避免干擾后續(xù)使用相同端口的新連接。這個(gè)“為什么”比狀態(tài)名本身重要得多答題時(shí)如果能寫出來(lái)就是加分項(xiàng)。3.2 HTTP與狀態(tài)碼、Session與Cookie研發(fā)工程師必須張口就來(lái)的基礎(chǔ)2016年的網(wǎng)絡(luò)題還有一個(gè)高頻方向是HTTP。我記得有一道題給了幾個(gè)HTTP狀態(tài)碼讓選出含義錯(cuò)誤的項(xiàng)。這要求你對(duì)常見狀態(tài)碼非常敏感200 OK請(qǐng)求成功301 Moved Permanently永久重定向302 Found臨時(shí)重定向304 Not Modified資源未修改可使用緩存401 Unauthorized未認(rèn)證403 Forbidden已認(rèn)證但無(wú)權(quán)限404 Not Found資源不存在500 Internal Server Error服務(wù)器內(nèi)部錯(cuò)誤502 Bad Gateway網(wǎng)關(guān)錯(cuò)誤503 Service Unavailable服務(wù)不可用。另外一道題考察Session和Cookie的區(qū)別。這類題在研發(fā)崗筆試?yán)飵缀鯇儆谒头诸}但并不保證每個(gè)人都拿得到。核心區(qū)別是維度的對(duì)比CookieSession存儲(chǔ)位置瀏覽器端服務(wù)器端安全性較容易被篡改較安全大小限制單條約4KB取決于服務(wù)器配置生命周期可長(zhǎng)期存在一般隨會(huì)話結(jié)束失效衍生考法如果一個(gè)系統(tǒng)部署了多臺(tái)服務(wù)器Session存在單機(jī)上會(huì)導(dǎo)致用戶請(qǐng)求被負(fù)載均衡到其他機(jī)器時(shí)Session丟失。解決方案包括Session共享、Sticky Session、或者把Session數(shù)據(jù)放到Redis等外部存儲(chǔ)。這類分布式場(chǎng)景題在2016年之后的筆試題里越來(lái)越常見。3.3 數(shù)據(jù)結(jié)構(gòu)復(fù)雜度與典型算法從排序到二叉樹邊界條件才是判分點(diǎn)2016研發(fā)工程師筆試題二的數(shù)據(jù)結(jié)構(gòu)部分至少有一道排序算法選擇/復(fù)雜度計(jì)算題以及一道二叉樹相關(guān)題。排序算法的高頻考點(diǎn)是各排序算法的平均/最壞時(shí)間復(fù)雜度、空間復(fù)雜度、穩(wěn)定性以及適用場(chǎng)景。這里我建議準(zhǔn)備一張表筆試前過(guò)一遍排序算法平均時(shí)間復(fù)雜度最壞時(shí)間復(fù)雜度空間復(fù)雜度穩(wěn)定嗎冒泡排序O(n^2)O(n^2)O(1)穩(wěn)定快速排序O(n log n)O(n^2)O(log n)不穩(wěn)定歸并排序O(n log n)O(n log n)O(n)穩(wěn)定堆排序O(n log n)O(n log n)O(1)不穩(wěn)定插入排序O(n^2)O(n^2)O(1)穩(wěn)定希爾排序約O(n^1.3)O(n^2)O(1)不穩(wěn)定快排的最壞情況是每次選的基準(zhǔn)都是最大或最小值導(dǎo)致劃分極不均衡。一個(gè)進(jìn)階考點(diǎn)是如何在數(shù)據(jù)基本有序時(shí)避免快排退化常見方案是隨機(jī)選擇基準(zhǔn)或者在小區(qū)間內(nèi)改用插入排序。如果筆試問(wèn)“數(shù)據(jù)量很大但內(nèi)存不夠應(yīng)該用什么排序算法”答案通常是歸并排序外部排序的基礎(chǔ)因?yàn)樗梢苑謮K讀入、逐層合并。二叉樹的題目也很有代表性。比如給定前序遍歷和中序遍歷要求重建二叉樹并輸出后序遍歷。這個(gè)題我從2016年一直看到現(xiàn)在每年都有類似版本。解法不復(fù)雜前序遍歷的第一個(gè)節(jié)點(diǎn)是根在中序遍歷里找到根的位置左邊屬于左子樹右邊屬于右子樹然后遞歸。關(guān)鍵是把邊界條件寫對(duì)——遞歸時(shí)左子樹的區(qū)間是[inStart, rootIndex-1]右子樹是[rootIndex1, inEnd]別把端點(diǎn)搞混。3.4 算法題里的“隱藏要求”復(fù)雜度和邊界條件的表達(dá)質(zhì)量也是評(píng)分項(xiàng)我復(fù)盤2016年這批筆試時(shí)注意到一個(gè)現(xiàn)象騰訊的算法題通常不要求寫完整可運(yùn)行的工程代碼但會(huì)給出一定的偽代碼空間。這意味著你可以用偽代碼表達(dá)但必須在注釋或關(guān)鍵步驟中體現(xiàn)出對(duì)時(shí)間復(fù)雜度和邊界條件的理解。比如一道經(jīng)典題找出一個(gè)數(shù)組里出現(xiàn)次數(shù)超過(guò)一半的數(shù)字。常規(guī)思路是排序后取中位數(shù)時(shí)間復(fù)雜度O(n log n)。但這道題的最優(yōu)解是Boyer-Moore投票算法時(shí)間復(fù)雜度O(n)、空間復(fù)雜度O(1)。如果你在規(guī)定空間里寫出了這個(gè)解法并且在代碼里說(shuō)明“因?yàn)楹蜻x值要么是目標(biāo)值要么可以被其他值抵消”面試官是能看出來(lái)你真的懂這塊知識(shí)點(diǎn)的。另外邊界條件一定要單獨(dú)處理比如數(shù)組為空、只有一個(gè)元素、不存在超過(guò)一半的數(shù)字等。很多人在LeetCode上刷題時(shí)習(xí)慣主函數(shù)只跑happy path筆試?yán)锞蜁?huì)漏掉這種用例。我的建議是每次寫完算法題花30秒列出所有邊界輸入在注釋里寫明你的代碼是怎么處理它們的。這是性價(jià)比極高的加分項(xiàng)。4. 沙盤推演用2016年二的幾道經(jīng)典題完整走一遍解題鏈路這一節(jié)我想換一種方式來(lái)做復(fù)盤不再按知識(shí)點(diǎn)逐個(gè)講而是選取幾道我記憶中2016年二卷里非常有代表性的題目按照“讀題-識(shí)別考點(diǎn)-設(shè)計(jì)解法-易錯(cuò)點(diǎn)”這個(gè)鏈路完整推演一遍。這樣你也能看到我在拿到一道題時(shí)是怎么思考的。4.1 一道C語(yǔ)言綜合題從變量定義到內(nèi)存分區(qū)考的是系統(tǒng)思維題目大概是這樣的寫出下面代碼中a、p、str、ptr等變量或常量分別存儲(chǔ)在哪里以及它們的值。#include stdio.h #include stdlib.h int global_var 10; static int static_var 20; int main() { int local_var 30; int *ptr (int *)malloc(sizeof(int) * 4); char *str hello; char arr[] world; static int local_static 40; return 0; }識(shí)別考點(diǎn)這里考的不只是一個(gè)內(nèi)存分區(qū)而是多個(gè)內(nèi)存區(qū)域的綜合判斷。推演過(guò)程global_var是全局變量有初值存儲(chǔ)在.data段static_var是靜態(tài)變量有初值也存儲(chǔ)在.data段雖然它在文件作用域但加上static不影響存儲(chǔ)位置只影響鏈接可見性local_var是局部變量存儲(chǔ)在棧區(qū)ptr本身是一個(gè)局部指針變量存儲(chǔ)在棧區(qū)但它指向的malloc分配的內(nèi)存存儲(chǔ)在堆區(qū)堆內(nèi)存未初始化里面是隨機(jī)數(shù)據(jù)str是局部指針變量存儲(chǔ)在棧區(qū)它指向的字符串常量hello存儲(chǔ)在只讀數(shù)據(jù)段.rodataarr是局部數(shù)組數(shù)組名代表?xiàng)Ｉ系囊粔K連續(xù)內(nèi)存內(nèi)容是從只讀區(qū)拷貝過(guò)來(lái)的world注意arr本身在棧上local_static是函數(shù)內(nèi)靜態(tài)變量存儲(chǔ)在.data段或.bss取決于是否有初值。易錯(cuò)點(diǎn)最容易錯(cuò)的是char *str hello和char arr[] world的區(qū)別其次是忘了ptr變量本身在棧上而不是在堆上。很多人一看到malloc就條件反射地寫“堆”但題目問(wèn)的是指針變量自身的位置不是指向的位置。答題時(shí)最好在題目旁邊畫一個(gè)簡(jiǎn)易的內(nèi)存分區(qū)圖把每個(gè)變量都標(biāo)進(jìn)去基本不會(huì)錯(cuò)。這道題我的經(jīng)驗(yàn)是遇到“變量存儲(chǔ)位置”的題目先畫棧、堆、全局區(qū)、常量區(qū)四個(gè)方塊然后逐個(gè)變量歸類不要憑記憶直接寫答案否則很容易在細(xì)節(jié)處丟分。4.2 一道網(wǎng)絡(luò)綜合題TCP狀態(tài)診斷與連接管理另一道讓我印象深刻的題目是給出一段TCP連接的抓包截圖包含狀態(tài)和序列號(hào)的轉(zhuǎn)換要求判斷連接是否正常建立以及序列號(hào)的含義。識(shí)別考點(diǎn)TCP連接建立過(guò)程中序列號(hào)和確認(rèn)號(hào)的語(yǔ)義。推演過(guò)程客戶端發(fā)送SYN序列號(hào)假設(shè)是x不帶數(shù)據(jù)包服務(wù)端回復(fù)SYNACK序列號(hào)為y確認(rèn)號(hào)為x1客戶端回復(fù)ACK確認(rèn)號(hào)為y1。這里有一個(gè)高頻考點(diǎn)為什么確認(rèn)號(hào)是對(duì)方序列號(hào)加1因?yàn)樵赟YN報(bào)文里SYN標(biāo)志位本身要消耗一個(gè)序列號(hào)所以即使沒(méi)有攜帶數(shù)據(jù)確認(rèn)號(hào)也要在對(duì)方初始序列號(hào)基礎(chǔ)上加1。這個(gè)細(xì)節(jié)如果不懂后面做TCP重傳和滑動(dòng)窗口題目時(shí)很容易出錯(cuò)。這類題目還經(jīng)常結(jié)合netstat輸出讓你根據(jù)某個(gè)端口的狀態(tài)判斷連接處于什么階段。比如看到TIME_WAIT狀態(tài)的連接很多說(shuō)明主動(dòng)關(guān)閉方的連接正在等待2MSL超時(shí)屬于正常現(xiàn)象但如果你發(fā)現(xiàn)CLOSE_WAIT大量堆積就要趕緊查一下應(yīng)用是否沒(méi)有正確關(guān)閉socket。易錯(cuò)點(diǎn)很多人會(huì)混淆CLOSE_WAIT和TIME_WAIT。這里我提供一個(gè)記憶技巧CLOSE_WAIT是被動(dòng)關(guān)閉方等待自己應(yīng)用層調(diào)用close的狀態(tài)TIME_WAIT是主動(dòng)關(guān)閉方在發(fā)完最后一個(gè)ACK后等待的狀態(tài)。誰(shuí)的機(jī)器上什么狀態(tài)多往往能反推出誰(shuí)是主動(dòng)方、誰(shuí)是被動(dòng)方、毛病出在哪個(gè)環(huán)節(jié)。4.3 一道數(shù)據(jù)結(jié)構(gòu)題給前序和中序遍歷重建二叉樹題目已知一棵二叉樹的前序遍歷序列為ABDCE中序遍歷序列為DBACE求后序遍歷序列。識(shí)別考點(diǎn)二叉樹的遍歷序列與樹結(jié)構(gòu)重建。推演過(guò)程前序遍歷第一個(gè)字符是A所以根節(jié)點(diǎn)是A在中序遍歷DBACE中找到A左邊是DBC沒(méi)有左子樹的前半部分右邊是CE不對(duì)中序是D B A C E所以A左邊是DB右邊是CE前序第二個(gè)字符是B它在A的左子樹根節(jié)點(diǎn)所以B是A的左孩子中序DB中B左邊是D所以D是B的左孩子B右邊為空沒(méi)有右孩子前序接下來(lái)是D驗(yàn)證了D是B左孩子然后是C說(shuō)明A的右子樹根是C中序CE中C左邊為空右邊是E所以E是C的右孩子后序遍歷順序是左-右-根所以結(jié)果是D B E C A。易錯(cuò)點(diǎn)如果中序序列中某個(gè)節(jié)點(diǎn)的左右子樹順序判斷錯(cuò)誤后面整個(gè)樹都會(huì)重建錯(cuò)。特別是當(dāng)某個(gè)節(jié)點(diǎn)只有左子樹或只有右子樹的時(shí)候很容易把空的位置搞混。我的習(xí)慣是每確定一個(gè)節(jié)點(diǎn)就在兩個(gè)序列里把該節(jié)點(diǎn)劃掉然后劃分子樹區(qū)間這樣不容易亂。這類題目在筆試中屬于“看起來(lái)復(fù)雜但實(shí)際有固定套路”的題型。只要掌握了遞歸劃分區(qū)間的思想刷兩三道類似的題就能完全掌握。4.4 從這幾道題看騰訊出題邏輯基礎(chǔ)、原理、邊界三者缺一不可推演完這三道題你會(huì)發(fā)現(xiàn)騰訊的筆試題有一個(gè)明顯特征題目本身不超綱但考察方式非常強(qiáng)調(diào)原理和邊界。它很少讓你從零寫一個(gè)紅黑樹或?qū)崿F(xiàn)一個(gè)線程池而是給你一個(gè)看似簡(jiǎn)單的場(chǎng)景考察你是不是真的理解背后的機(jī)制以及能不能處理正常情況之外的邊界。所以備考時(shí)不要只追求“刷了多少題”而要對(duì)每一個(gè)知識(shí)點(diǎn)問(wèn)自己三個(gè)問(wèn)題它的底層原理是什么它的邊界條件是什么如果我在真實(shí)系統(tǒng)里寫這段代碼哪里最可能出bug如果你能對(duì)大綱里的核心知識(shí)點(diǎn)都回答出這三個(gè)問(wèn)題那無(wú)論筆試題怎么變你都不會(huì)慌。5. 實(shí)戰(zhàn)復(fù)盤總結(jié)備考這道卷子我的時(shí)間分配和資料建議最后分享一下我在備考騰訊2016研發(fā)工程師筆試題二這類試卷時(shí)實(shí)際采用的時(shí)間分配和資料選擇。這套思路也適用于其他大廠以基礎(chǔ)為主的筆試題。5.1 時(shí)間分配按分值比重倒推復(fù)習(xí)優(yōu)先級(jí)如果你手頭有一份歷年真題最科學(xué)的做法不是順著做而是先統(tǒng)計(jì)考點(diǎn)分布再按分值倒推復(fù)習(xí)時(shí)間。以2016年二卷為例我當(dāng)時(shí)的統(tǒng)計(jì)結(jié)果大概是知識(shí)模塊估計(jì)分值占比建議復(fù)習(xí)時(shí)間占比C/C基礎(chǔ)與內(nèi)存模型30%25%操作系統(tǒng)與Linux25%25%網(wǎng)絡(luò)與分布式基礎(chǔ)20%20%數(shù)據(jù)結(jié)構(gòu)與算法20%25%其他邏輯題、智力題等5%5%注意算法復(fù)習(xí)時(shí)間占比我反而調(diào)高了5%因?yàn)閿?shù)據(jù)的結(jié)構(gòu)雖然分值不是最高但它是唯一一個(gè)“刷題效果立竿見影”的模塊多刷一道就多拿一道的分。而C/C基礎(chǔ)雖然分值高但邊際效益遞減吃透核心考點(diǎn)后再花大量時(shí)間死磕細(xì)節(jié)性價(jià)比不高。5.2 資料清單不貪多但每一本都要吃得透透的市面上準(zhǔn)備大廠筆試的資料實(shí)在太多我的建議是精讀三到四本不要貪多嚼不爛《深入理解計(jì)算機(jī)系統(tǒng)》CS:APP應(yīng)對(duì)C/C內(nèi)存布局、指針、進(jìn)程、虛擬內(nèi)存等考點(diǎn)是性價(jià)比最高的一本書。重點(diǎn)看第2、3、9章。《操作系統(tǒng)概念》恐龍書或國(guó)內(nèi)教材的進(jìn)程/線程、同步、死鎖、內(nèi)存管理章節(jié)操作系統(tǒng)筆試的考點(diǎn)覆蓋。《計(jì)算機(jī)網(wǎng)絡(luò)自頂向下方法》重點(diǎn)看TCP、HTTP、DNS等應(yīng)用層和傳輸層內(nèi)容。《劍指Offer》 LeetCode高頻題清單刷題的主力重點(diǎn)練數(shù)組、鏈表、二叉樹、動(dòng)態(tài)規(guī)劃和字符串題。Linux命令不建議專門看書直接在線上找一個(gè)命令速查手冊(cè)每天花20分鐘過(guò)一遍常用參數(shù)連續(xù)看一周就足夠了。筆試考Linux通常不會(huì)太深關(guān)鍵是“見過(guò)、有印象”。5.3 復(fù)盤時(shí)最容易忽略的盲區(qū)手寫代碼的規(guī)范度最后一個(gè)想提醒的點(diǎn)是筆試中手寫代碼包括偽代碼的規(guī)范度。有不少人算法思路很清晰但寫出來(lái)的代碼縮進(jìn)混亂、變量命名隨意、缺少注釋這在閱卷人眼里會(huì)大大扣分。我的建議是備考時(shí)就養(yǎng)成習(xí)慣縮進(jìn)統(tǒng)一最好用4空格變量名要有意義len、index、rootValue這類一眼能看懂核心邏輯旁邊加一行注釋說(shuō)明你“為什么這么做”寫完代碼后用幾秒鐘過(guò)一遍邊界條件在注釋里補(bǔ)充說(shuō)明。這樣做短期內(nèi)可能顯得慢但一旦形成習(xí)慣筆試時(shí)你不會(huì)覺得是負(fù)擔(dān)反而能幫你理清思路減少低級(jí)錯(cuò)誤。說(shuō)到底筆試不只是給閱卷人看的也是你自己思維過(guò)程的外化。寫得規(guī)范你的思路也會(huì)更清晰。回到騰訊2016研發(fā)工程師筆試題二這份卷子它雖然已經(jīng)是很多年前的題了但背后的考察邏輯放在今天依然成立基礎(chǔ)知識(shí)的深度理解、邊界條件的敏感性、以及把理論轉(zhuǎn)化為動(dòng)手實(shí)踐的能力。哪怕你不準(zhǔn)備去大廠按這個(gè)標(biāo)準(zhǔn)練習(xí)一遍對(duì)自己的技術(shù)底子也是一次實(shí)打?qū)嵉募庸獭?