2018年那一輪迅雷校園招聘的客戶端在線筆試我到現(xiàn)在還記得拿到試卷時(shí)的感受選擇題量不小編程題不是純粹的LeetCode風(fēng)格而是帶業(yè)務(wù)場(chǎng)景的。當(dāng)時(shí)用的在線筆試平臺(tái)會(huì)實(shí)時(shí)倒計(jì)時(shí)兩個(gè)多小時(shí)看著多真正動(dòng)起手來(lái)才發(fā)現(xiàn)每一段都要精打細(xì)算?？嫉膬?nèi)容橫跨數(shù)據(jù)結(jié)構(gòu)、網(wǎng)絡(luò)、并發(fā)和客戶端基礎(chǔ)幾乎把計(jì)算機(jī)專業(yè)核心課都過(guò)了一遍。這篇文章不打算復(fù)述原題筆試題目本身有保密要求而且過(guò)了這么多年逐字回憶也沒(méi)有意義。我想做的是把這一類下載工具廠商客戶端崗的筆試邏輯拆開(kāi)來(lái)講它為什么考這些、高頻考點(diǎn)背后對(duì)應(yīng)什么能力模型、編程題拿到手應(yīng)該按什么順序思考、以及那些你準(zhǔn)備LeetCode時(shí)根本不會(huì)注意到的坑。對(duì)準(zhǔn)備迅雷以及騰訊、網(wǎng)易這類有重客戶端業(yè)務(wù)公司校招筆試的同學(xué)來(lái)說(shuō)應(yīng)該能直接派上用場(chǎng)。1. 迅雷這份筆試卷的出題邏輯客戶端崗位要的不是刷題機(jī)器先說(shuō)一個(gè)很多人對(duì)筆試的誤解以為刷題量夠了就能過(guò)。放在純算法崗或許成立但迅雷這種以下載工具起家的公司客戶端崗筆試的底層邏輯完全不一樣。它考的不是你能不能做出難題而是你能不能建立起從業(yè)務(wù)場(chǎng)景到技術(shù)方案的映射能力。1.1 迅雷客戶端崗位的核心能力模型迅雷做的是下載工具客戶端形態(tài)覆蓋Windows、macOS、移動(dòng)端。這類產(chǎn)品的核心技術(shù)痛點(diǎn)是大文件傳輸、弱網(wǎng)環(huán)境下的穩(wěn)定性、多任務(wù)并發(fā)調(diào)度、磁盤(pán)讀寫(xiě)優(yōu)化、以及長(zhǎng)時(shí)間運(yùn)行下的內(nèi)存控制。這就決定了它的客戶端崗位在選人時(shí)最看重的不是你會(huì)多少冷門(mén)算法而是下面四層能力第一層是計(jì)算機(jī)基礎(chǔ)包括數(shù)據(jù)結(jié)構(gòu)、操作系統(tǒng)、計(jì)算機(jī)網(wǎng)絡(luò)這是筆試選擇題的主戰(zhàn)場(chǎng)也是后續(xù)所有技術(shù)討論的地基。第二層是網(wǎng)絡(luò)編程能力TCP/UDP協(xié)議細(xì)節(jié)、HTTP協(xié)議擴(kuò)展頭、斷點(diǎn)續(xù)傳機(jī)制、P2P通信模型這些東西在迅雷的實(shí)際業(yè)務(wù)里每天都在被調(diào)用。第三層是并發(fā)處理能力多線程下載、線程池調(diào)度、任務(wù)隊(duì)列、鎖與同步下載器本質(zhì)上就是一個(gè)高并發(fā)的任務(wù)調(diào)度系統(tǒng)。第四層才是客戶端工程化能力包括內(nèi)存管理、UI渲染優(yōu)化、緩存策略。如果你只看前三層會(huì)覺(jué)得這是通用后臺(tái)崗的考核范圍這也正是迅雷筆試比較特別的地方它把網(wǎng)絡(luò)和并發(fā)的權(quán)重抬得非常高因?yàn)橄螺d場(chǎng)景天然依賴這兩塊知識(shí)。1.2 題型結(jié)構(gòu)與時(shí)間分配2018年那場(chǎng)筆試是線上進(jìn)行整體結(jié)構(gòu)大概是單選題加多選題一共30道左右覆蓋數(shù)據(jù)結(jié)構(gòu)、操作系統(tǒng)、網(wǎng)絡(luò)、C/Java基礎(chǔ)簡(jiǎn)答題兩到三道考察方案設(shè)計(jì)類的題目比如斷點(diǎn)續(xù)傳的實(shí)現(xiàn)思路編程題兩道難度中等偏上一道偏算法一道偏設(shè)計(jì)。整場(chǎng)限時(shí)在120到150分鐘之間。我當(dāng)時(shí)的策略是選擇題控制在60分鐘內(nèi)簡(jiǎn)答題25分鐘編程題留足50分鐘最后剩一點(diǎn)時(shí)間檢查。這個(gè)節(jié)奏看起來(lái)簡(jiǎn)單但實(shí)際操作中很多人栽在選擇填空上糾結(jié)太久導(dǎo)致編程題沒(méi)有時(shí)間寫(xiě)。1.3 與純算法筆試的核心差異同樣是客戶端方向字節(jié)和騰訊的筆試可能更偏動(dòng)態(tài)規(guī)劃、DFS/BFS這類標(biāo)準(zhǔn)算法題而迅雷的題目里明顯帶著業(yè)務(wù)痕跡。舉個(gè)例子同樣是考分塊這個(gè)概念純算法題會(huì)問(wèn)一個(gè)數(shù)組分成K份求最小最大值迅雷可能就會(huì)包裝成一個(gè)文件分片后并行下載如何設(shè)計(jì)調(diào)度策略。這個(gè)差異給備考帶來(lái)的啟示是刷題當(dāng)然要刷但不能只刷題。你需要刻意訓(xùn)練自己把算法題還原成業(yè)務(wù)場(chǎng)景的能力或者反過(guò)來(lái)看到下載、緩存、并發(fā)這些關(guān)鍵詞時(shí)能快速想到底層的數(shù)據(jù)結(jié)構(gòu)和算法。2. 數(shù)據(jù)結(jié)構(gòu)和算法題不是最難的但一定是最能拉分的這部分是選擇題和編程題的公共基礎(chǔ)。從通過(guò)率來(lái)看算法題反而是拉開(kāi)差距的關(guān)鍵。原因很簡(jiǎn)單網(wǎng)絡(luò)和并發(fā)題大家多少能說(shuō)幾句但算法題會(huì)就是會(huì)不會(huì)就是不會(huì)編不出來(lái)。2.1 選擇題里的數(shù)據(jù)結(jié)構(gòu)高頻考點(diǎn)就迅雷這張卷子來(lái)說(shuō)以下幾塊幾乎是每年必考棧與隊(duì)列的對(duì)比、單調(diào)棧的典型應(yīng)用場(chǎng)景比如下一個(gè)更大元素這個(gè)知識(shí)點(diǎn)在選擇題里經(jīng)常和括號(hào)匹配、表達(dá)式求值混在一起考。二叉樹(shù)的三種遍歷順序、已知前序中序求后序這種題只要畫(huà)圖推一遍就不會(huì)錯(cuò)。哈希表的沖突處理方式拉鏈法和開(kāi)放定址法的優(yōu)缺點(diǎn)。各類排序算法的時(shí)間復(fù)雜度、穩(wěn)定性對(duì)比以及什么時(shí)候用快排、什么時(shí)候用堆排。這些東西看著基礎(chǔ)但線上筆試有個(gè)特點(diǎn)你沒(méi)法用編譯器驗(yàn)證心里如果模糊就只能蒙。所以我建議備考時(shí)把每個(gè)數(shù)據(jù)結(jié)構(gòu)的操作復(fù)雜度表、應(yīng)用場(chǎng)景整理成一張速記表考前十分鐘掃一遍。2.2 迅雷偏愛(ài)的算法題風(fēng)格合并、分塊、Top K如果給迅雷筆試算法題貼標(biāo)簽我的答案是兩個(gè)詞分治和合并。這兩個(gè)詞非常貼合下載場(chǎng)景——一個(gè)大文件拆分多個(gè)分片下載下載完再合并多個(gè)任務(wù)并發(fā)執(zhí)行結(jié)果匯集排序。所以你在刷題時(shí)會(huì)發(fā)現(xiàn)合并兩個(gè)有序鏈表合并K個(gè)有序數(shù)組尋找Top K大元素這類題目出現(xiàn)頻率極高。另一個(gè)高頻方向是字符串處理和鏈表的邊界操作。字符串的題目通常不會(huì)太難但非?？技?xì)節(jié)比如去除空格、反轉(zhuǎn)單詞順序這類。鏈表的題目則偏愛(ài)反轉(zhuǎn)、環(huán)檢測(cè)、刪除倒數(shù)第N個(gè)節(jié)點(diǎn)這些題難度不大關(guān)鍵是在筆試環(huán)境下不能出錯(cuò)。2.3 典型例題解析合并K個(gè)有序鏈表我拿一道最典型的題來(lái)說(shuō)明筆試中的解題節(jié)奏。題目描述給定K個(gè)有序鏈表每個(gè)鏈表元素都是升序排列請(qǐng)把它們合并成一個(gè)有序鏈表。拿到題先不要直接寫(xiě)代碼先建立思路。最容易想到的方案是順序合并先合并前兩個(gè)再把結(jié)果和第三個(gè)合并以此類推。假設(shè)每個(gè)鏈表平均長(zhǎng)度是NK個(gè)鏈表這樣做的時(shí)間復(fù)雜度是O(K^2 * N)因?yàn)槊亢喜⒁淮味家闅v當(dāng)前結(jié)果鏈表。稍微好一點(diǎn)的方案是兩兩合并也就是歸并思路時(shí)間復(fù)雜度降到O(K * N * logK)這個(gè)方案在筆試中足夠用而且代碼復(fù)雜度不高。最優(yōu)方案是用小根堆維護(hù)K個(gè)鏈表的當(dāng)前頭節(jié)點(diǎn)每次取出最小值再放入該節(jié)點(diǎn)的后繼時(shí)間復(fù)雜度同為O(K * N * logK)但常數(shù)更小。筆試環(huán)境下我推薦直接用優(yōu)先隊(duì)列方案代碼清晰不容易出錯(cuò)struct ListNode { int val; ListNode* next; ListNode(int x) : val(x), next(nullptr) {} }; struct cmp { bool operator()(ListNode* a, ListNode* b) { return a-val b-val; } }; ListNode* mergeKLists(vectorListNode* lists) { priority_queueListNode*, vectorListNode*, cmp pq; for (auto head : lists) { if (head) pq.push(head); } ListNode dummy(0); ListNode* tail dummy; while (!pq.empty()) { ListNode* node pq.top(); pq.pop(); tail-next node; tail node; if (node-next) pq.push(node-next); } return dummy.next; }邊界條件有三個(gè)鏈表數(shù)組為空、數(shù)組中某個(gè)鏈表為空、所有節(jié)點(diǎn)取完后堆為空。這三個(gè)情況在代碼里都自然覆蓋了但你在寫(xiě)完代碼后一定要主動(dòng)檢查一遍。2.4 典型例題解析海量數(shù)據(jù)中的Top K問(wèn)題另一道迅雷風(fēng)格很濃的題是Top K。比如某個(gè)下載服務(wù)一天產(chǎn)生海量日志每行記錄一個(gè)下載任務(wù)的耗時(shí)找出耗時(shí)最長(zhǎng)的K條記錄。這道題在筆試選擇題里會(huì)考思路在編程題里會(huì)考實(shí)現(xiàn)。核心答案是維護(hù)一個(gè)大小為K的小根堆遍歷數(shù)據(jù)時(shí)如果當(dāng)前元素比堆頂大就彈出堆頂并插入當(dāng)前元素。遍歷結(jié)束后堆里的K個(gè)元素就是答案。時(shí)間復(fù)雜度O(N * logK)空間復(fù)雜度O(K)。這里有一個(gè)非常容易錯(cuò)的理解點(diǎn)為什么是小根堆而不是大根堆。因?yàn)槲覀円Ａ糇畲蟮腒個(gè)元素最小的那個(gè)在堆頂方便隨時(shí)被更大的元素淘汰。如果你用大根堆堆頂是最大的元素新元素進(jìn)來(lái)時(shí)根本無(wú)法判斷該不該淘汰堆頂。迅雷筆試?yán)镞@個(gè)知識(shí)點(diǎn)出現(xiàn)過(guò)不止一次而且會(huì)換包裝給你一個(gè)數(shù)據(jù)流隨時(shí)查詢當(dāng)前的中位數(shù)給你100億個(gè)整數(shù)找出出現(xiàn)頻率最高的100個(gè)。本質(zhì)上都是堆這個(gè)數(shù)據(jù)結(jié)構(gòu)在解決只關(guān)心局部極值的問(wèn)題。3. 網(wǎng)絡(luò)與并發(fā)下載場(chǎng)景下必考的系統(tǒng)知識(shí)如果把算法題比作筆試的骨架那網(wǎng)絡(luò)和并發(fā)就是迅雷筆試的血肉。這一部分的分值占比通常能達(dá)到三成以上而且選擇題、簡(jiǎn)答題、編程題里都會(huì)出現(xiàn)它的影子。3.1 TCP協(xié)議永遠(yuǎn)繞不開(kāi)的基礎(chǔ)TCP的知識(shí)點(diǎn)在任何公司筆試?yán)锒际潜乜嫉谘咐椎木碜永锼目疾焐疃葧?huì)更深一些。除了三次握手、四次揮手這種送分題還會(huì)考滑動(dòng)窗口、擁塞控制、以及TIME_WAIT狀態(tài)的理解。舉個(gè)例子選擇題可能會(huì)這樣出一個(gè)客戶端主動(dòng)關(guān)閉連接后進(jìn)入TIME_WAIT狀態(tài)需要等待多長(zhǎng)時(shí)間為什么需要這個(gè)狀態(tài)。答案大家都知道等待2MSL但原因需要說(shuō)完整第一保證主動(dòng)關(guān)閉方最后一個(gè)ACK能夠到達(dá)對(duì)方如果丟失對(duì)方會(huì)重發(fā)FIN第二讓舊連接的報(bào)文在網(wǎng)絡(luò)中自然消失避免影響新連接。這個(gè)知識(shí)點(diǎn)為什么迅雷愛(ài)考因?yàn)橄螺d工具需要頻繁地創(chuàng)建和銷(xiāo)毀TCP連接TIME_WAIT狀態(tài)的連接數(shù)量如果過(guò)多會(huì)導(dǎo)致本地端口資源耗盡這是下載器實(shí)際開(kāi)發(fā)中會(huì)真實(shí)遇到的問(wèn)題。3.2 HTTP與斷點(diǎn)續(xù)傳一道題吃透協(xié)議頭斷點(diǎn)續(xù)傳是迅雷筆試簡(jiǎn)答題的常客幾乎每年都有。它考察的是你對(duì)HTTP協(xié)議的理解深度。斷點(diǎn)續(xù)傳的核心是HTTP的Range頭?？蛻舳嗽谡?qǐng)求時(shí)可以帶上Range: bytes0-1023服務(wù)端如果支持段請(qǐng)求會(huì)返回206 Partial Content并且在響應(yīng)頭中帶上Content-Range: bytes 0-1023/2048告訴客戶端當(dāng)前傳輸?shù)氖悄囊欢?、文件總大小是多少。為了確保續(xù)傳時(shí)文件沒(méi)有被修改還需要用到ETag或Last-Modified頭?？蛻舳讼劝l(fā)送一個(gè)帶If-Range的請(qǐng)求如果ETag匹配說(shuō)明文件沒(méi)變服務(wù)端返回206如果不匹配說(shuō)明文件已經(jīng)被修改服務(wù)端返回200攜帶完整文件客戶端需要丟掉已下載內(nèi)容重新開(kāi)始。以HTTP基礎(chǔ)加Range頭為核心再包上校驗(yàn)頭這就是一個(gè)完整的斷點(diǎn)續(xù)傳方案。簡(jiǎn)答題里如果考這個(gè)答題結(jié)構(gòu)可以這樣組織先講斷點(diǎn)續(xù)傳要解決什么問(wèn)題再講HTTP協(xié)議如何支持最后講客戶端如何記錄下載進(jìn)度、如何校驗(yàn)文件完整性。3.3 P2P下載與多線程分片調(diào)度如果說(shuō)斷點(diǎn)續(xù)傳是必答題那P2P相關(guān)的題目就是迅雷的特色題。作為P2P下載技術(shù)的代表產(chǎn)品迅雷對(duì)P2P原理的考察非常自然。這里的知識(shí)點(diǎn)包括P2P網(wǎng)絡(luò)的節(jié)點(diǎn)發(fā)現(xiàn)機(jī)制、種子文件的解析、分片索引信息的交換、節(jié)點(diǎn)之間的數(shù)據(jù)塊傳輸。筆試通常不會(huì)考得很深但至少會(huì)出一道題讓你解釋為什么多個(gè)客戶端同時(shí)下載同一個(gè)文件時(shí)越多人下載速度越快。答案的核心是P2P網(wǎng)絡(luò)中每個(gè)下載者同時(shí)也是上傳者?？蛻舳薃下載了文件的第1到第10個(gè)分片客戶端B就可以直接從A獲取這些分片而不必都去服務(wù)器拉取。下載者越多可用的數(shù)據(jù)來(lái)源越多整體吞吐量越高。與之關(guān)聯(lián)的還有一個(gè)高頻考點(diǎn)多線程分片下載。為什么要分片下載因?yàn)閱蜹CP連接受擁塞控制影響吞吐量有限多個(gè)連接并行可以顯著提升下載速度。但分片又帶來(lái)新問(wèn)題分片大小怎么確定、怎么記錄每個(gè)分片的狀態(tài)、分片下載完成后如何校驗(yàn)拼接、某個(gè)分片下載失敗是否需要重試。這就是一個(gè)完整的任務(wù)調(diào)度系統(tǒng)。3.4 簡(jiǎn)答題實(shí)戰(zhàn)設(shè)計(jì)一個(gè)支持?jǐn)帱c(diǎn)續(xù)傳的下載器我把這類題的答題模板整理一下筆試時(shí)可以直接套先交代背景下載任務(wù)包含文件元數(shù)據(jù)、分片列表、下載進(jìn)度。然后說(shuō)明分片策略將文件按照固定大小如1MB切分為多個(gè)分片每個(gè)分片獨(dú)立下載。接著講記錄機(jī)制本地維護(hù)一個(gè)下載狀態(tài)文件記錄已下載分片的信息包括分片序號(hào)、偏移量、長(zhǎng)度、校驗(yàn)值。再講網(wǎng)絡(luò)請(qǐng)求使用HTTP Range頭請(qǐng)求指定分片校驗(yàn)通過(guò)后標(biāo)記為完成。最后講異?；謴?fù)下載中斷后重新啟動(dòng)時(shí)讀取狀態(tài)文件跳過(guò)已完成和校驗(yàn)通過(guò)的下載任務(wù)只對(duì)未完成的分片發(fā)起請(qǐng)求。這個(gè)模板把是什么、怎么做、怎么恢復(fù)串起來(lái)了邏輯完整即使不要求寫(xiě)代碼也能拿到大部分分。4. 客戶端專項(xiàng)內(nèi)存、線程調(diào)度和渲染的實(shí)戰(zhàn)考點(diǎn)迅雷的客戶端覆蓋多個(gè)平臺(tái)筆試專項(xiàng)部分會(huì)考查C和Java兩套體系。如果你投的是Windows客戶端方向C知識(shí)是重頭如果投的是Android/iOS方向平臺(tái)相關(guān)的知識(shí)占比會(huì)更高。但無(wú)論哪個(gè)平臺(tái)下面這幾類題幾乎是公共的。4.1 內(nèi)存管理從C智能指針到Android泄漏C方向的第一高頻考點(diǎn)是智能指針。unique_ptr獨(dú)占所有權(quán)shared_ptr共享所有權(quán)并用引用計(jì)數(shù)控制生命周期weak_ptr用于打破循環(huán)引用。選擇題經(jīng)常給出一個(gè)多線程場(chǎng)景問(wèn)shared_ptr是否線程安全。答案是不完全安全引用計(jì)數(shù)本身是原子操作但指向的對(duì)象是否線程安全需要你自己保證。Java/Android方向則愛(ài)考內(nèi)存泄漏場(chǎng)景最常見(jiàn)的四個(gè)靜態(tài)變量持有Activity引用、內(nèi)部類隱式持有外部類引用、Handler延遲消息持有Activity、資源未關(guān)閉。筆試如果讓你分析一個(gè)內(nèi)存泄漏問(wèn)題以及如何排查你要說(shuō)出工具鏈Android Studio的Memory Profiler或者用LeakCanary自動(dòng)檢測(cè)然后根據(jù)引用鏈定位到具體持有者。4.2 多線程與任務(wù)調(diào)度鎖、等待隊(duì)列和生產(chǎn)者消費(fèi)者下載器是一個(gè)典型的生產(chǎn)者消費(fèi)者模型。一個(gè)或多個(gè)線程負(fù)責(zé)從網(wǎng)絡(luò)拉取數(shù)據(jù)放入內(nèi)存緩沖區(qū)另一些線程負(fù)責(zé)把緩沖區(qū)的數(shù)據(jù)寫(xiě)入磁盤(pán)。筆試選擇題里這個(gè)模型對(duì)應(yīng)的問(wèn)題包括緩沖區(qū)用什么數(shù)據(jù)結(jié)構(gòu)、如何保證線程安全、緩沖區(qū)滿了怎么辦、緩沖區(qū)空了怎么辦。答案通常是基于鎖和條件變量實(shí)現(xiàn)互斥鎖保護(hù)共享緩沖區(qū)兩個(gè)條件變量分別表示緩沖區(qū)不為滿和緩沖區(qū)不為空生產(chǎn)者等待不滿條件消費(fèi)者等待不空條件。如果你用C寫(xiě)直接用std::condition_variable配合std::mutex代碼很簡(jiǎn)潔。我會(huì)在編程題部分再展開(kāi)一次這里先記住一個(gè)核心結(jié)論凡是考察并發(fā)最終都要落到一個(gè)可運(yùn)行的、無(wú)死鎖、無(wú)忙等待的實(shí)現(xiàn)上。4.3 UI渲染與卡頓優(yōu)化客戶端才有的考點(diǎn)這一塊在通用后臺(tái)崗筆試?yán)锿耆粫?huì)出現(xiàn)但客戶端崗幾乎必考。核心問(wèn)題是為什么界面會(huì)卡頓如何優(yōu)化。標(biāo)準(zhǔn)答案是UI線程每秒需要完成60幀的渲染每幀的預(yù)算約16.6毫秒。如果主線程上有耗時(shí)的磁盤(pán)IO、網(wǎng)絡(luò)請(qǐng)求或復(fù)雜布局就會(huì)超過(guò)預(yù)算導(dǎo)致丟幀、卡頓。優(yōu)化方向包括耗時(shí)操作放子線程、布局層級(jí)扁平化、使用視圖復(fù)用、圖片按需加載、減少過(guò)度繪制。迅雷的下載界面有進(jìn)度條、速度曲線、任務(wù)列表這些高頻刷新場(chǎng)景對(duì)UI性能要求不低所以這個(gè)考點(diǎn)非常有業(yè)務(wù)相關(guān)性。備課時(shí)建議把16.6毫秒主線程不執(zhí)行耗時(shí)操作寫(xiě)在筆記本第一行。4.4 緩存與持久化從LRU到磁盤(pán)策略客戶端經(jīng)常需要緩存數(shù)據(jù)緩存相關(guān)的題目里L(fēng)RU是大熱門(mén)。LRU全稱Least Recently Used核心思想是淘汰最久沒(méi)被訪問(wèn)的數(shù)據(jù)。筆試會(huì)考兩種形式一種是選擇題讓你選LRU的底層數(shù)據(jù)結(jié)構(gòu)另一種是編程題讓你實(shí)現(xiàn)一個(gè)LRU Cache。最經(jīng)典的解法是哈希表加雙向鏈表哈希表保證O(1)查找雙向鏈表保證O(1)插入和刪除。后面編程題部分我再給出完整代碼。磁盤(pán)緩存策略的簡(jiǎn)答題也不少見(jiàn)焦點(diǎn)問(wèn)題是下載了一半的文件要不要寫(xiě)入磁盤(pán)什么時(shí)候?qū)懭搿Ｗ顑?yōu)策略是數(shù)據(jù)先寫(xiě)入頁(yè)緩存達(dá)到一定閾值后批量刷新到磁盤(pán)避免頻繁小IO同時(shí)定期調(diào)用fsync確保數(shù)據(jù)落盤(pán)。筆試不需要寫(xiě)得非常底層把批量寫(xiě)、延遲寫(xiě)、定期落盤(pán)這三個(gè)核心策略講清楚就夠了。5. 兩道典型編程題從讀題到AC的完整推演編程題是所有在線筆試的壓軸大題分值高、時(shí)間緊最容易心態(tài)崩。這里我拿兩道非常貼近迅雷考點(diǎn)的典型題完整演示一遍從讀題到AC的思考鏈路你可以在筆試時(shí)照著這個(gè)流程執(zhí)行。5.1 第一類編程題模擬分片下載的完成率統(tǒng)計(jì)題目大意是某下載任務(wù)把一個(gè)文件分成N個(gè)分片每個(gè)分片有唯一編號(hào)?，F(xiàn)在給出一個(gè)日志文件里面是無(wú)數(shù)條分片編號(hào)-狀態(tài)開(kāi)始/完成的記錄請(qǐng)統(tǒng)計(jì)當(dāng)前任務(wù)的整體完成率并且輸出所有已完成且順序正確的分片區(qū)間。拿到題先不要急著寫(xiě)先定義清楚輸入輸出輸入第一行是分片總數(shù)N接下來(lái)若干行是日志記錄最后讀到一個(gè)結(jié)束標(biāo)記。輸出格式需要你計(jì)算完成百分比并輸出已完成分片的最大連續(xù)區(qū)間。核心解法思路用一個(gè)布爾數(shù)組標(biāo)記每個(gè)分片是否完成遍歷日志更新數(shù)組最后一次循環(huán)統(tǒng)計(jì)連續(xù)完成的區(qū)間同時(shí)計(jì)算完成數(shù)除以總數(shù)得到百分比。這個(gè)方案時(shí)間復(fù)雜度和空間復(fù)雜度都是O(N)完全夠用。筆試寫(xiě)代碼時(shí)的關(guān)鍵點(diǎn)是要把輸入循環(huán)寫(xiě)對(duì)。用C的while (cin a b)來(lái)讀取日志遇到EOF就結(jié)束然后在循環(huán)里做狀態(tài)更新。這個(gè)過(guò)程中最容易漏掉的是一個(gè)分片可能被多次標(biāo)記開(kāi)始但完成只能生效一次以及輸入的編號(hào)是0-based還是1-based一定要按題目要求來(lái)。5.2 第二類編程題實(shí)現(xiàn)一個(gè)LRU Cache這道題在客戶端崗筆試中出現(xiàn)頻率非常高因?yàn)樗瑫r(shí)考察了哈希表、鏈表、以及最近使用策略的業(yè)務(wù)理解。題目通常這樣描述設(shè)計(jì)一個(gè)LRU緩存支持get(key)和put(key, value)兩個(gè)操作get在key不存在時(shí)返回-1put在緩存滿時(shí)淘汰最久未使用的key。分析思路要分三步走。第一步確定需要什么數(shù)據(jù)結(jié)構(gòu)get需要O(1)所以必須有哈希表put需要O(1)插入刪除同時(shí)要維護(hù)訪問(wèn)順序所以要用雙向鏈表。第二步設(shè)計(jì)哈希表的value存鏈表節(jié)點(diǎn)的指針這樣才能在O(1)時(shí)間內(nèi)把節(jié)點(diǎn)移動(dòng)到鏈表頭部。第三步把接口理清楚訪問(wèn)某個(gè)key時(shí)先在哈希表拿到節(jié)點(diǎn)然后把它摘下來(lái)放到鏈表頭部插入新key時(shí)先判斷容量是否已滿滿了就刪除鏈表尾部節(jié)點(diǎn)并刪除哈希表對(duì)應(yīng)項(xiàng)。代碼實(shí)現(xiàn)如下class LRUCache { private: struct Node { int key, value; Node* prev; Node* next; Node(int k, int v) : key(k), value(v), prev(nullptr), next(nullptr) {} }; unordered_mapint, Node* cache; Node* head; Node* tail; int capacity; int size; void addToHead(Node* node) { node-next head-next; node-prev head; head-next-prev node; head-next node; } void removeNode(Node* node) { node-prev-next node-next; node-next-prev node-prev; } void moveToHead(Node* node) { removeNode(node); addToHead(node); } public: LRUCache(int capacity) : capacity(capacity), size(0) { head new Node(0, 0); tail new Node(0, 0); head-next tail; tail-prev head; } int get(int key) { if (!cache.count(key)) return -1; Node* node cache[key]; moveToHead(node); return node-value; } void put(int key, int value) { if (cache.count(key)) { Node* node cache[key]; node-value value; moveToHead(node); return; } Node* newNode new Node(key, value); cache[key] newNode; addToHead(newNode); size; if (size capacity) { Node* removed tail-prev; removeNode(removed); cache.erase(removed-key); delete removed; size--; } } };這段代碼里最容易被忽略的邊界是兩個(gè)哨兵節(jié)點(diǎn)head和tail。有了它們鏈表在為空時(shí)也能保證操作統(tǒng)一不用處理大量空指針判斷。筆試環(huán)境下我強(qiáng)烈建議所有雙向鏈表都加上哨兵節(jié)點(diǎn)。另一個(gè)易錯(cuò)點(diǎn)是put已經(jīng)存在的key時(shí)一定要先更新value再移動(dòng)到頭部不能先移動(dòng)再更新否則節(jié)點(diǎn)順序會(huì)亂。最后刪除節(jié)點(diǎn)時(shí)要同時(shí)從哈希表erase并delete節(jié)點(diǎn)避免內(nèi)存泄漏。5.3 在線筆試的評(píng)測(cè)機(jī)制與自測(cè)方法很多線上筆試平臺(tái)不會(huì)告訴你為什么沒(méi)通過(guò)某個(gè)測(cè)試用例只會(huì)告訴你過(guò)了百分之多少。所以提交前一定要自己測(cè)試邊界情況空輸入、只有一個(gè)元素、滿容量時(shí)重復(fù)put、get不存在的key、連續(xù)get同一個(gè)key。還有兩個(gè)很關(guān)鍵的紀(jì)律第一不要向標(biāo)準(zhǔn)輸出打印任何調(diào)試信息評(píng)測(cè)系統(tǒng)只認(rèn)你該輸出的結(jié)果多一個(gè)字符都算WA。第二如果題目要求多組測(cè)試用例一定要用循環(huán)讀取到EOF而不是只處理一組數(shù)據(jù)。很多同學(xué)算法本身寫(xiě)對(duì)了卻因?yàn)檩斎胙h(huán)寫(xiě)錯(cuò)而只拿到部分分?jǐn)?shù)。6. 考場(chǎng)實(shí)戰(zhàn)時(shí)間分配、環(huán)境檢查和心態(tài)控制筆試不只是考你會(huì)不會(huì)還考你在限時(shí)環(huán)境里能不能穩(wěn)定輸出。這個(gè)話題學(xué)校不教但實(shí)戰(zhàn)里非常關(guān)鍵。6.1 提前把線上筆試環(huán)境踩熟2018年的在線筆試平臺(tái)已經(jīng)比較成熟但你還是應(yīng)該提前兩天模擬一次打開(kāi)平臺(tái)、切到自己要用的編程語(yǔ)言、復(fù)制粘貼一段測(cè)試代碼跑通編譯。千萬(wàn)別等到開(kāi)考了才發(fā)現(xiàn)編譯器版本太低不支持C11的某些特性或者本地IDE能用但平臺(tái)不認(rèn)。另外平臺(tái)有一些隱藏規(guī)則要提前搞清楚編程題允許使用哪些語(yǔ)言不同語(yǔ)言對(duì)輸入輸出的處理模板是什么是否支持從本地粘貼代碼。如果不確定寧可多花五分鐘在正式考試前測(cè)試環(huán)境。6.2 三個(gè)時(shí)間節(jié)點(diǎn)守住兩條線我把筆試時(shí)間分為三條線時(shí)間進(jìn)度線、得分進(jìn)度線、心態(tài)防線。時(shí)間進(jìn)度線是試卷開(kāi)考30分鐘選擇題必須完成一半以上60分鐘時(shí)選擇題和簡(jiǎn)答題必須全部結(jié)束開(kāi)始進(jìn)入編程題。得分進(jìn)度線是選擇題不確定的題先標(biāo)記不要消耗大量時(shí)間編程題優(yōu)先選擇思路最清晰的題做即使算法不是最優(yōu)也要先寫(xiě)一版能過(guò)基礎(chǔ)用例的解法。什么叫先拿基礎(chǔ)分就是如果一道編程題最優(yōu)解法是動(dòng)態(tài)規(guī)劃但你一下子想不出來(lái)可以先寫(xiě)遞歸暴力版本通過(guò)部分用例拿到分再回頭優(yōu)化。筆試的OJ通常按通過(guò)的測(cè)試用例數(shù)給分暴力解法往往能拿三成到五成的分?jǐn)?shù)比空著強(qiáng)得多。6.3 有取舍地做選擇題多選寧可少選在線筆試的選擇題里多選題的計(jì)分規(guī)則通常是少選得部分分多選不得分。所以多選題沒(méi)有十足把握的選項(xiàng)就不要選這就是寧可少選不可錯(cuò)選原則。單選則要優(yōu)先排除明顯錯(cuò)誤的選項(xiàng)再在剩下的里面選。另一個(gè)容易踩的坑是有些題是每題多少分答錯(cuò)扣分這和普通考試不一樣。答題前先看清題目說(shuō)明如果答錯(cuò)有倒扣那不確定的題不要隨便蒙留空反而更安全。6.4 筆試結(jié)束后的復(fù)盤(pán)動(dòng)作筆試結(jié)束后不要馬上松懈趁記憶還熱立刻把剛才不確定的題目記下來(lái)。我的習(xí)慣是用手機(jī)備忘錄列出選擇題不確定的知識(shí)點(diǎn)清單比如TCP的某個(gè)狀態(tài)、哈希表的某個(gè)沖突處理方式。筆試結(jié)束的當(dāng)晚對(duì)照這個(gè)清單翻書(shū)補(bǔ)漏。補(bǔ)漏的意義在于校招筆試往往不止一輪同一家公司的筆試和面試知識(shí)點(diǎn)高度重疊你這次不確定的很可能就是面試官下一輪要問(wèn)的。把筆試當(dāng)成一次免費(fèi)的知識(shí)點(diǎn)掃描你會(huì)少走很多彎路。最后再分享一個(gè)我后來(lái)才意識(shí)到的小技巧筆試前一周與其繼續(xù)刷難題不如把斷點(diǎn)續(xù)傳、TCP狀態(tài)、LRU、多線程下載這幾個(gè)主題各寫(xiě)一遍完整的知識(shí)框架每個(gè)主題用300字寫(xiě)清核心原理應(yīng)用場(chǎng)景可能被問(wèn)到的細(xì)節(jié)。我當(dāng)年寫(xiě)了厚厚一沓筆試時(shí)遇到相關(guān)題目手速和判斷力明顯不一樣。這套方法到今天依然適用推薦給每一個(gè)準(zhǔn)備客戶端方向校招筆試的同學(xué)。