1. 這份卷子真正想篩出什么樣的人我當(dāng)年參加滴滴出行2018校園招聘內(nèi)推筆試的時候崗位是系統(tǒng)開發(fā)工程師。說實(shí)話那個時間節(jié)點(diǎn)很多同學(xué)都在海投刷題刷到麻木但對“系統(tǒng)開發(fā)”這個崗位到底考什么其實(shí)沒幾個人想清楚了。我更傾向于把內(nèi)推筆試看成一次“預(yù)篩選技術(shù)摸底”它不像統(tǒng)考那樣完全按統(tǒng)一分?jǐn)?shù)線卡人而是在更短的時間里判斷你有沒有基礎(chǔ)的工程素養(yǎng)和系統(tǒng)思維。為什么這么說因?yàn)榈蔚蔚暮诵臉I(yè)務(wù)場景是出行調(diào)度系統(tǒng)開發(fā)工程師要面對的是海量訂單流、實(shí)時路徑匹配、多端狀態(tài)同步、高并發(fā)下的一致性保障這類問題。這類業(yè)務(wù)有三個特征高并發(fā)、強(qiáng)實(shí)時、狀態(tài)多。所以筆試考點(diǎn)不會只是純算法刷題它更像是把“操作系統(tǒng)、網(wǎng)絡(luò)、數(shù)據(jù)庫、Java并發(fā)、分布式常識”揉在一起用選擇題和編程題來考察你有沒有形成一套完整的系統(tǒng)認(rèn)知框架。我當(dāng)時看完卷子后最大的感受是它不是考“你會不會寫快排”而是考“你在高并發(fā)場景下敢不敢用快排”。這兩件事的差別非常大。前者是記憶問題后者是工程判斷問題。你背下了十種排序算法的手寫代碼但遇到“同一時刻數(shù)萬個司機(jī)上報(bào)位置服務(wù)端如何高效聚合熱點(diǎn)區(qū)域數(shù)據(jù)”這種題目時如果沒有分布式的概念沒有內(nèi)存分片和消息隊(duì)列的意識就只能寫出一個在單機(jī)上循環(huán)遍歷的玩具解法。再說說“系統(tǒng)開發(fā)工程師”和“算法工程師”“后端研發(fā)工程師”在筆試側(cè)重點(diǎn)上的差異。算法崗更看重模型理解、數(shù)學(xué)推導(dǎo)、數(shù)據(jù)結(jié)構(gòu)深度純后端研發(fā)崗更看重業(yè)務(wù)接口設(shè)計(jì)、數(shù)據(jù)庫建模、框架運(yùn)用而系統(tǒng)開發(fā)崗介于兩者之間它的題目會傾向于并發(fā)場景下的資源爭用、 分布式環(huán)境下的數(shù)據(jù)一致性、高吞吐系統(tǒng)的瓶頸分析。這就要求你不僅會寫代碼還要理解代碼跑在什么環(huán)境里、有哪些底層機(jī)制在支撐它。所以不要只刷LeetCode。你要知道內(nèi)推筆試的卷子通常在30到60分鐘內(nèi)就要完成一輪技術(shù)評估出題人沒有時間去考那些偏門冷知識他們只會挑“最能反映工程能力”的點(diǎn)來考。把這些點(diǎn)逐個吃透比盲目刷300道題劃算得多。以下是我對這份卷子考察范圍的復(fù)盤按出現(xiàn)頻率和重要性排序考察模塊典型考點(diǎn)為什么考數(shù)據(jù)結(jié)構(gòu)與算法鏈表、二叉樹、動態(tài)規(guī)劃、Top K問題基礎(chǔ)編碼能力快速判斷候選人代碼功底操作系統(tǒng)進(jìn)程線程、死鎖、虛擬內(nèi)存、IO模型高并發(fā)服務(wù)必須理解資源調(diào)度與隔離計(jì)算機(jī)網(wǎng)絡(luò)TCP握手、TIME_WAIT、HTTP狀態(tài)碼分布式系統(tǒng)繞不開網(wǎng)絡(luò)通信細(xì)節(jié)數(shù)據(jù)庫索引、事務(wù)隔離級別、SQL編寫業(yè)務(wù)數(shù)據(jù)落地與查詢性能保障Java基礎(chǔ)與并發(fā)JMM、HashMap并發(fā)問題、線程池主力開發(fā)語言的基礎(chǔ)掌握程度分布式常識CAP理論、負(fù)載均衡、緩存策略判斷候選人是否有系統(tǒng)級思維這個表格基本還原了那張卷子的出題骨架。你可以對照看看自己還有哪些薄弱項(xiàng)別等到筆試前一周才發(fā)現(xiàn)連TCP和UDP的區(qū)別都講不清楚。2. 核心考點(diǎn)逐個拆解每個知識點(diǎn)背后對應(yīng)什么工程問題2.1 數(shù)據(jù)結(jié)構(gòu)與算法不是考你會背而是考你會在什么場景下選它這一塊是筆試的重頭戲占分比通常最高。我列舉幾個當(dāng)年卷子中出現(xiàn)的高頻題并幫你把“知識點(diǎn)”和“工程場景”之間的那道橋搭起來。鏈表類題目比如“判斷鏈表是否有環(huán)”“找鏈表倒數(shù)第K個節(jié)點(diǎn)”幾乎所有大廠筆試都會出。滴滴考鏈表不是因?yàn)樗鼧I(yè)務(wù)里直接用到鏈表而是鏈表操作能很直接地暴露你對指針/引用、邊界條件、空間復(fù)雜度的掌控能力。當(dāng)時有一道題讓我印象深刻“給定兩個單鏈表找出它們的第一個公共節(jié)點(diǎn)。”這道題有哈希表法和雙指針法雙指針法的精妙之處在于兩個指針分別走完自己的鏈表后再走對方的鏈表最終在公共節(jié)點(diǎn)相遇。它體現(xiàn)的“用空間換時間或者用時間換空間”的權(quán)衡思維恰恰是系統(tǒng)開發(fā)中做資源規(guī)劃的核心思路。樹與圖遍歷也是必考。比如二叉樹層次遍歷、最近公共祖先、拓?fù)渑判颉Ｎ野选白罱沧嫦取眴为?dú)拎出來講因?yàn)檫@道題有兩個版本的考察方式普通二叉樹上找LCA和二叉搜索樹上找LCA。如果你能想到利用BST的性質(zhì)目標(biāo)值介于root和root之間時root就是LCA代碼會非常簡潔。出題人想看到的不是暴力解法而是你是否善于利用數(shù)據(jù)結(jié)構(gòu)的固有性質(zhì)來優(yōu)化算法。動態(tài)規(guī)劃考得不算深但一定會有一道。比如“最長上升子序列”“編輯距離”這類經(jīng)典題。我當(dāng)時拿到的是一個變形題“一個網(wǎng)格從左上角到右下角每次只能向右或向下求路徑上數(shù)字和的最小值?！边@題最基礎(chǔ)的解法是二維DP空間復(fù)雜度O(mn)優(yōu)化后可以壓縮到O(n)。在筆試場景下寫出二維DP就能拿大部分分?jǐn)?shù)但如果你能寫出滾動數(shù)組優(yōu)化并在注釋里說明“這個優(yōu)化將空間復(fù)雜度從O(mn)降到了O(n)”會明顯加分。因?yàn)樗故玖四悴皇撬烙浻脖矰P模板而是理解了狀態(tài)轉(zhuǎn)移過程中真正依賴哪些歷史狀態(tài)。Top K問題在滴滴筆試?yán)锍霈F(xiàn)頻率非常高因?yàn)椤罢页鰺岫茸罡叩腒個區(qū)域”“選出路況最好的K條路徑”這類業(yè)務(wù)需求太常見了。我不建議一上來就寫快速排序而是分情況討論數(shù)據(jù)量小、內(nèi)存放得下直接排序取前K簡單直觀。數(shù)據(jù)量很大、內(nèi)存放不下用堆維護(hù)大小為K的最小堆堆頂就是當(dāng)前第K大的元素。數(shù)據(jù)量極大且分散在多臺機(jī)器上先每臺機(jī)器求局部Top K再合并求全局Top K。我當(dāng)時筆試時選擇用堆實(shí)現(xiàn)因?yàn)榫碜用鞔_說了“數(shù)據(jù)規(guī)模為10億個整數(shù)內(nèi)存限制為256MB”。你一定得養(yǎng)成讀到約束條件再選算法的習(xí)慣這是系統(tǒng)開發(fā)工程師的基本素養(yǎng)。2.2 操作系統(tǒng)并發(fā)服務(wù)的底層地基操作系統(tǒng)的重要性很多刷題型選手會嚴(yán)重低估。我在筆試?yán)镉龅降腛S題不算難但覆蓋面很廣主要包括進(jìn)程與線程的區(qū)別。這道題幾乎必考。標(biāo)準(zhǔn)回答是進(jìn)程是資源分配的基本單位線程是CPU調(diào)度的基本單位進(jìn)程有獨(dú)立的地址空間線程共享所屬進(jìn)程的地址空間進(jìn)程切換開銷大線程切換開銷小。但如果你只答到這里只能拿一半分。出題人真正想聽到的是線程共享地址空間所以多線程編程時要格外注意數(shù)據(jù)同步這就是并發(fā)編程中鎖和原子類存在的前提。死鎖的四個必要條件互斥、持有并等待、不可剝奪、循環(huán)等待。光背概念不夠筆試常常會給你一段代碼問你“這段代碼是否會發(fā)生死鎖為什么”你得能準(zhǔn)確識別出四個條件分別在哪一行代碼中體現(xiàn)。我記得有一道題是經(jīng)典的“哲學(xué)家就餐問題變種”兩個線程各自持有了一把鎖又想獲取對方的鎖。你需要在答題時明確指出循環(huán)等待條件成立然后給出破解方法要么破壞持有并等待一次獲取所有資源要么破壞不可剝奪嘗試獲取鎖獲取不到就釋放已有鎖要么破壞循環(huán)等待規(guī)定獲取鎖的順序。虛擬內(nèi)存和頁面置換算法。這個概念用生活類比最好懂虛擬內(nèi)存就像一個只有十平方米的儲藏室但給你配了一份注明“每件物品放在哪個格子”的目錄。程序運(yùn)行時只把當(dāng)前需要的物品頁面拿進(jìn)儲藏室物理內(nèi)存其余放在倉庫磁盤。頁面不夠時就要決定把哪個物品送回倉庫這就是置換算法。LRU是筆試最常考的置換算法因?yàn)樗鼘?yīng)“最近最少使用”的業(yè)務(wù)直覺。這里我建議你親手寫一遍LRU緩存的實(shí)現(xiàn)用HashMap雙向鏈表這樣筆試遇到“設(shè)計(jì)一個LRU緩存”的題目時你直接就能給出O(1)時間復(fù)雜度的方案。IO模型阻塞IO、非阻塞IO、IO多路復(fù)用、異步IO。滴滴的系統(tǒng)開發(fā)崗特別愛考這個因?yàn)榉?wù)端接入大量司機(jī)和乘客的連接時不能用“一個線程處理一個連接”的模型那會直接把線程池打爆。你要能講清楚select/poll/epoll的區(qū)別尤其是epoll的紅黑樹就緒鏈表機(jī)制以及邊緣觸發(fā)和水平觸發(fā)的差異。這個知識點(diǎn)是面試后續(xù)深挖的高頻切入點(diǎn)筆試時遇到別只選個B就完事建議做題時順手在草稿紙上畫出事件流確認(rèn)自己理解沒有偏差。2.3 計(jì)算機(jī)網(wǎng)絡(luò)分布式系統(tǒng)的毛細(xì)血管網(wǎng)絡(luò)題基本上是送分題但也是很多人丟分的地方因?yàn)榧?xì)節(jié)太容易混淆。TCP三次握手。大家都能說出SYN、SYNACK、ACK的順序但筆試往往會讓算一算序列號的變化或者問“第三次握手失敗了會怎樣”。第三次握手失敗時服務(wù)端會超時重傳SYNACK如果多次重傳仍失敗則斷開連接。這個問題考的其實(shí)是TCP可靠傳輸?shù)臋C(jī)制本質(zhì)是“任何一方收到確認(rèn)前都不能確認(rèn)消息已經(jīng)被可靠送達(dá)”。TIME_WAIT是另一個高壓考點(diǎn)。主動關(guān)閉連接的一方會進(jìn)入TIME_WAIT狀態(tài)持續(xù)2MSL最大報(bào)文段生存時間。為什么要等2MSL因?yàn)橐_保最后一個ACK能讓對方收到——如果這個ACK丟了對方重傳FIN你還有時間響應(yīng)。同時也要讓舊連接中的所有報(bào)文在網(wǎng)絡(luò)中自然消亡避免污染新連接。這個機(jī)制在系統(tǒng)開發(fā)里非常重要高并發(fā)短連接場景下如果服務(wù)端大量進(jìn)入TIME_WAIT狀態(tài)會導(dǎo)致端口資源耗盡。當(dāng)時我看到卷子上這道題時就在心里慶幸自己曾經(jīng)處理過類似的生產(chǎn)問題不然真的只會背“TIME_WAIT是2MSL”而不知道它背后的工程意義。HTTP和HTTPS。狀態(tài)碼是必考項(xiàng)200、301、302、304、401、403、404、500、502、503每個都對應(yīng)一個具體場景。特別要注意304Not Modified和503Service Unavailable這種和系統(tǒng)架構(gòu)密切相關(guān)的狀態(tài)碼。304跟HTTP緩存機(jī)制掛鉤503則意味著服務(wù)過載或正在維護(hù)。如果你能把503和“服務(wù)限流、熔斷降級”聯(lián)系起來答那就遠(yuǎn)超及格線了。TCP vs UDP的選擇這個考點(diǎn)是送分中的送分題但要結(jié)合場景說才有說服力。TCP面向連接、可靠、有序適合文件傳輸、網(wǎng)頁訪問UDP無連接、不可靠、低延遲適合實(shí)時音視頻、游戲狀態(tài)同步。滴滴這類出行服務(wù)在車輛軌跡上報(bào)場景中有時候會采用UDP應(yīng)用層消息序號來兼顧實(shí)時性和一定程度的可靠性這個思路如果能在筆試題里提到會顯得你有真實(shí)場景認(rèn)知。2.4 數(shù)據(jù)庫業(yè)務(wù)數(shù)據(jù)落地的核心數(shù)據(jù)庫題在系統(tǒng)開發(fā)崗筆試?yán)镎嫉姆至勘群芏嗳讼胂笾写蟮枚?。索引是最核心的考點(diǎn)。InnoDB的BTree索引為什么用BTree而不是B-Tree或者紅黑樹因?yàn)锽Tree的非葉子節(jié)點(diǎn)不存儲數(shù)據(jù)可以在相同頁大小下容納更多鍵值樹更矮查詢更少IO同時葉子節(jié)點(diǎn)通過鏈表串聯(lián)范圍查詢非常高效。你應(yīng)該能畫出BTree的大致結(jié)構(gòu)并解釋聚簇索引和二級索引的區(qū)別以及什么情況下會發(fā)生回表。SQL題也是一定會出現(xiàn)的比如多表聯(lián)查、分組統(tǒng)計(jì)、子查詢。我建議你把“GROUP BY HAVING”的組合練熟因?yàn)樗目釉谟赪HERE是在分組前過濾HAVING是在分組后過濾。當(dāng)時卷子上有一道題“查每個城市訂單量超過10000的司機(jī)數(shù)”你必須知道過濾條件應(yīng)該放在HAVING還是WHERE放錯了返回結(jié)果就完全不對。事務(wù)隔離級別是數(shù)據(jù)庫另一個必考點(diǎn)。讀未提交、讀已提交、可重復(fù)讀、串行化這四級隔離性逐個增強(qiáng)并發(fā)性能逐個下降。MySQL InnoDB默認(rèn)是可重復(fù)讀。這個知識點(diǎn)要想答好不能只背名字要知道每個級別解決了什么問題讀未提交有臟讀問題讀已提交解決了臟讀但存在不可重復(fù)讀可重復(fù)讀解決了不可重復(fù)讀但默認(rèn)下仍可能有幻讀問題InnoDB通過間隙鎖解決串行化則徹底解決幻讀但性能最差。如果你能結(jié)合MVCC多版本并發(fā)控制說一下快照讀和當(dāng)前讀的區(qū)別那這道題你基本可以拿滿分。這個知識點(diǎn)的工程意義非常直接平臺從賬戶余額中扣款、司機(jī)發(fā)起提現(xiàn)、訂單狀態(tài)變更每一個都涉及事務(wù)的并發(fā)控制理解隔離級別就是理解業(yè)務(wù)一致性的底線。2.5 Java基礎(chǔ)與并發(fā)系統(tǒng)開發(fā)的主力語言如果筆試明確偏向Java那么Java并發(fā)編程這塊會被重點(diǎn)考察。HashMap的并發(fā)問題是一個老生常談但極其經(jīng)典的考法。JDK 1.7中HashMap并發(fā)put可能導(dǎo)致死循環(huán)鏈表環(huán)化JDK 1.8中改進(jìn)了鏈表插入方式和擴(kuò)容機(jī)制后不再有這個問題但仍然存在數(shù)據(jù)丟失的可能。你如果真的要答好這個點(diǎn)需要深入理解resize過程的頭插法和尾插法區(qū)別。我建議你不僅能說出結(jié)論還能畫一下鏈表遷移過程的示意圖這能幫你在筆試后的面試環(huán)節(jié)直接建立專業(yè)印象。線程池的考察很細(xì)corePoolSize、maximumPoolSize、workQueue之間的關(guān)系和任務(wù)提交流程。當(dāng)提交任務(wù)數(shù)超過corePoolSize時任務(wù)會進(jìn)入工作隊(duì)列進(jìn)行排隊(duì)而不是立刻創(chuàng)建新線程隊(duì)列也滿了才創(chuàng)建新線程直到maximumPoolSize仍然處理不過來才走拒絕策略。這里有一個很常見的誤區(qū)很多人以為只要提交任務(wù)就會創(chuàng)建線程到maximumPoolSize實(shí)際不是這樣。任務(wù)隊(duì)列的選型也會直接影響線程池行為LinkedBlockingQueue無界隊(duì)列基本不會觸發(fā)創(chuàng)建非核心線程而SynchronousQueue則不緩存任務(wù)來了任務(wù)就嘗試創(chuàng)建線程。這些細(xì)節(jié)在筆試選擇題中出現(xiàn)頻率非常高。并發(fā)工具類CountDownLatch、CyclicBarrier、Semaphore這三個要分清使用場景。CountDownLatch是“一個線程等待多個線程完成”CyclicBarrier是“多個線程互相等待同時到達(dá)某個屏障后繼續(xù)”Semaphore是“控制同時訪問某個資源的線程數(shù)”。我用一個類比幫你記憶CountDownLatch是公司年會集合所有人都到齊了大巴才能發(fā)車CyclicBarrier是百米賽跑所有運(yùn)動員都就位了裁判才能發(fā)令Semaphore是景區(qū)限流每天放固定人數(shù)進(jìn)去出來一個才放進(jìn)一個。這套類比在筆試考場上是很好用的速記策略。2.6 分布式系統(tǒng)常識高頻但容易失分最后一類考點(diǎn)是分布式系統(tǒng)的基礎(chǔ)常識。這部分不需要你讀過《數(shù)據(jù)密集型應(yīng)用系統(tǒng)設(shè)計(jì)》這種大部頭但至少要掌握幾個核心概念。CAP理論是必考。一致性Consistency、可用性Availability、分區(qū)容錯性Partition tolerance三者不可兼得。這里最容易被忽視的是分區(qū)容錯性在分布式系統(tǒng)中是必須滿足的因?yàn)榫W(wǎng)絡(luò)分區(qū)一定會發(fā)生你只能在C和A之間做取舍。這個洞察要答出來才能展現(xiàn)你真的理解了CAP的精髓而不只是背出了三個英文字母。緩存策略的考察通常結(jié)合業(yè)務(wù)場景比如“春運(yùn)搶票高峰期如何防止緩存穿透、緩存擊穿、緩存雪崩”。緩存穿透是查一個根本不存在的數(shù)據(jù)每次都要打到數(shù)據(jù)庫解決思路是緩存空值或布隆過濾器緩存擊穿是某個熱點(diǎn)key在過期瞬間大量請求打到DB解決思路是互斥鎖或熱點(diǎn)數(shù)據(jù)永不過期后臺更新緩存雪崩是大量key同時過期或者Redis集群宕機(jī)解決思路是過期時間加隨機(jī)值、多級緩存、熔斷降級。這套東西不是死知識它直接對應(yīng)出行業(yè)務(wù)中“秒級查詢熱點(diǎn)區(qū)域的實(shí)時路況”這種場景。負(fù)載均衡算法輪詢、加權(quán)輪詢、最少連接、一致性哈希。一致性哈希一定要搞懂因?yàn)樗诜植际骄彺婧蛿?shù)據(jù)分片中太常用了。你要能解釋“虛擬節(jié)點(diǎn)”解決了什么問題數(shù)據(jù)傾斜以及為什么加節(jié)點(diǎn)時只有少量數(shù)據(jù)需要遷移。我當(dāng)時筆試有一道判斷題“一致性哈希算法的節(jié)點(diǎn)數(shù)量變化時大部分key的映射位置會發(fā)生變化”這顯然是錯的但如果你沒有真正理解環(huán)形哈?？臻g很容易被繞進(jìn)去。3. 經(jīng)典筆試真題復(fù)盤從讀題到AC的完整思考過程3.1 編程題一Top K高頻元素原題大致是“給定一個非空的整數(shù)數(shù)組返回其中出現(xiàn)頻率前K高的元素要求時間復(fù)雜度優(yōu)于O(n log n)?！蔽夷玫筋}目后的第一個動作是確認(rèn)輸入約束。如果數(shù)組長度是百萬級別那直接Collections.sort 統(tǒng)計(jì)頻次的方案就是O(n log n)雖然能過但明顯不符合“優(yōu)于O(n log n)”的要求。正確的方向是用桶排序先遍歷一次數(shù)組用HashMap統(tǒng)計(jì)每個元素出現(xiàn)頻率然后創(chuàng)建一個“頻率桶”數(shù)組桶的下標(biāo)即頻率桶內(nèi)存放該頻率對應(yīng)的所有元素最后從高頻率桶向低頻率桶遍歷收集前K個元素。這個方案的時間復(fù)雜度是O(n)空間復(fù)雜度是O(n)。具體代碼Java版本public ListInteger topKFrequent(int[] nums, int k) { MapInteger, Integer freqMap new HashMap(); for (int num : nums) { freqMap.put(num, freqMap.getOrDefault(num, 0) 1); } ListInteger[] bucket new List[nums.length 1]; for (Map.EntryInteger, Integer entry : freqMap.entrySet()) { int freq entry.getValue(); if (bucket[freq] null) { bucket[freq] new ArrayList(); } bucket[freq].add(entry.getKey()); } ListInteger result new ArrayList(); for (int i bucket.length - 1; i 0 result.size() k; i--) { if (bucket[i] ! null) { result.addAll(bucket[i]); } } return result; }我當(dāng)時寫完后特意檢查了一個邊界情況如果數(shù)組中所有元素出現(xiàn)頻率都相同頻率桶數(shù)組的最右端可能同時存在多個不同的元素此時從桶末尾往前取時需要確保不超過K個。這里有個小技巧result.size() k不僅控制了循環(huán)終止還防止了數(shù)組越界。這道題在系統(tǒng)開發(fā)場景里的對應(yīng)是“統(tǒng)計(jì)一段時間內(nèi)最熱門的搜索詞”或“統(tǒng)計(jì)哪些區(qū)域呼叫量激增”所以你千萬別把它當(dāng)純算法題來做要意識到它是分布式系統(tǒng)中“分詞頻統(tǒng)計(jì)”的簡化模型否則面試追問“如果數(shù)據(jù)分散在100臺機(jī)器上你怎么統(tǒng)計(jì)”你會措手不及。3.2 編程題二設(shè)計(jì)一個支持GetMin的棧原題是“實(shí)現(xiàn)一個棧除了push、pop操作之外還要支持getMin操作要求所有操作的時間復(fù)雜度均為O(1)?！边@道題經(jīng)典到不能再經(jīng)典了但筆試現(xiàn)場很多人還是會寫錯。設(shè)計(jì)思路是使用兩個棧一個數(shù)據(jù)棧正常存取元素一個輔助棧專門記錄當(dāng)前的最小值。push時數(shù)據(jù)棧正常入棧輔助棧則壓入“當(dāng)前元素與輔助棧棧頂元素之間的較小值”。pop時兩個棧都出棧。關(guān)鍵細(xì)節(jié)在于輔助棧的元素個數(shù)和數(shù)據(jù)棧保持一致。這樣getMin時只需要返回輔助棧棧頂即可。如果輔助棧只在遇到更小值時入棧那么在最小值被pop出去后輔助棧的信息就不完整了。class MinStack { private DequeInteger dataStack; private DequeInteger minStack; public MinStack() { dataStack new ArrayDeque(); minStack new ArrayDeque(); } public void push(int x) { dataStack.push(x); if (minStack.isEmpty() || x minStack.peek()) { minStack.push(x); } } public void pop() { if (dataStack.pop().equals(minStack.peek())) { minStack.pop(); } } public int getMin() { return minStack.peek(); } }注意上面這段代碼輔助棧只在元素“小于等于當(dāng)前最小值”時才入棧pop時判斷數(shù)據(jù)棧彈出的元素是否等于輔助棧棧頂值是則輔助棧同步彈出。這個方案空間效率更高但需要仔細(xì)處理邊界。如果你在考場上對自己邊界處理沒有信心用“兩個棧同步增長”的方案更穩(wěn)妥代碼可讀性也更好。這道題考察的真正重點(diǎn)不是“雙棧技巧”而是你是否具備“空間換時間”的意識。系統(tǒng)開發(fā)里用緩存加速讀請求、用預(yù)計(jì)算減少重復(fù)計(jì)算本質(zhì)上和這道題是同一個思維模式。3.3 設(shè)計(jì)類簡答題訂單狀態(tài)機(jī)設(shè)計(jì)有一道題我印象特別深因?yàn)樗谶x擇題和編程題之外屬于一道簡短的設(shè)計(jì)題“請?jiān)O(shè)計(jì)一個訂單狀態(tài)機(jī)并說明狀態(tài)流轉(zhuǎn)的觸發(fā)條件?！庇唵螤顟B(tài)是出行系統(tǒng)的心臟。你至少得畫出幾個核心狀態(tài)已創(chuàng)建、已接單、已到達(dá)上車點(diǎn)、行程中、已到達(dá)目的地、已支付、已取消。每個狀態(tài)遷移都有觸發(fā)方和條件已創(chuàng)建到已接單乘客下單成功后司機(jī)接單。已接單到已到達(dá)上車點(diǎn)司機(jī)到達(dá)乘客定位的上車點(diǎn)App端自動或司機(jī)手動確認(rèn)。已到達(dá)上車點(diǎn)到行程中乘客上車司機(jī)點(diǎn)擊開始行程。行程中到已到達(dá)目的地司機(jī)點(diǎn)擊結(jié)束行程。已到達(dá)目的地到已支付乘客支付訂單支持余額、免密支付等。這里出題人想看的不是狀態(tài)枚舉而是你是否考慮了異常分支司機(jī)取消、乘客取消、超時未接單自動取消、行程中發(fā)生事故需要緊急終止這些都是狀態(tài)機(jī)設(shè)計(jì)中的隱性要求。我當(dāng)時在答案里補(bǔ)了一句“所有狀態(tài)遷移需要保證冪等性和操作記錄便于對賬和問題追蹤”明顯感覺到面試官在后續(xù)面試中特別關(guān)注了這一點(diǎn)。狀態(tài)機(jī)設(shè)計(jì)的原則叫“單一事實(shí)來源”簡單說就是同一個訂單的狀態(tài)在任何時刻都只能有一個權(quán)威定義不能App端認(rèn)為已接單、服務(wù)端認(rèn)為已創(chuàng)建。在分布式環(huán)境下這個“權(quán)威”通常由服務(wù)端數(shù)據(jù)庫中的訂單狀態(tài)字段決定客戶端的狀態(tài)展示只是一個投影。4. 筆試現(xiàn)場的答題節(jié)奏與得分策略這一節(jié)我講講“怎么做題”本身。很多同學(xué)明明知識點(diǎn)都會但因?yàn)楣?jié)奏不對、取舍不對最終分?jǐn)?shù)不理想。先列一個我自己的時間分配參考假設(shè)筆試總時長120分鐘選擇填空占60分鐘編程題占60分鐘題型建議耗時策略選擇題30分鐘一遍過不確定的標(biāo)記后優(yōu)先跳過不要糾結(jié)填空題15分鐘多數(shù)是概念補(bǔ)充和簡單計(jì)算快速作答編程題第一題20分鐘先想清楚再動手保證AC一題編程題第二題15分鐘如果第一題順利這里可以試更高難度否則優(yōu)先保證第一題正確剩余時間10分鐘回頭處理標(biāo)記的選擇題難題整理草稿紙上的思路為什么選擇題要“限時跳過”因?yàn)檫x擇題一道也就一兩分你在某道TCP細(xì)節(jié)題上耗了十分鐘就是拿后面編程題的得分機(jī)會去冒險(xiǎn)。編程題通常是按用例通過比例給分的AC一道簡單題拿到的分?jǐn)?shù)遠(yuǎn)比糾結(jié)三道選擇題的總分更實(shí)在。編程題的答題順序也有講究先做“題目描述最清晰、輸入輸出格式最明確”的那道通常它是整張卷子里最水的。不要以為題號靠后的題一定難有的卷子第一題反而是最惡心的超長題干閱讀題。先把好拿的分拿到手心態(tài)會穩(wěn)定很多。再講一個老手才懂的經(jīng)驗(yàn)筆試時要把自己的想法寫在代碼注釋里。比如“如果數(shù)據(jù)量超過內(nèi)存限制可以采用外部排序”或者“此處使用堆是因?yàn)樾枰l繁獲取Top K元素”即使代碼沒完全跑通閱卷人看到你的思考路徑也會給過程分。校招筆試的時間窗口有限不可能每個方案都完美落地你把思路表達(dá)出來本身就是一種展示。編程題如果一時沒有最優(yōu)解先寫暴力解也有價(jià)值。暴力解能保證你拿到一定比例的測試用例分?jǐn)?shù)而且暴力解的代碼相對簡單不容易出現(xiàn)低級語法錯誤。寫完暴力解后再標(biāo)注一行“TODO優(yōu)化為O(n)解法”至少說明你清楚問題在哪里。千萬別空著不寫空題是一分沒有的。關(guān)于編譯環(huán)境筆試系統(tǒng)通常支持C、Java、Python等主流語言。我的建議是選你最熟悉、標(biāo)準(zhǔn)庫最豐富的語言。算法題優(yōu)先Java或Python因?yàn)榧项悗炷艽蠓鶞p少編碼量C雖然效率高但容易在內(nèi)存和指針上出低級錯誤。Java的HashMap、PriorityQueue、Deque這些數(shù)據(jù)結(jié)構(gòu)要能不用查API就直接寫出來這是硬功夫考前多敲幾遍就自然熟了。5. 去重與反套路別被培訓(xùn)班的“模板答案”帶偏在講復(fù)習(xí)策略之前我要專門潑一盆冷水。現(xiàn)在網(wǎng)上流傳的很多“大廠筆試題模板答案”其實(shí)是培訓(xùn)班總結(jié)出來的一刀切套路它們能幫你應(yīng)付最基礎(chǔ)的版本但很容易讓你在稍微變形一點(diǎn)的題目面前翻車。舉個例子HashMap的并發(fā)問題很多模板答案是“Java 7會死循環(huán)Java 8沒有死循環(huán)”。這句話沒有錯但它遺漏了更重要的后半句Java 8雖然修掉了死循環(huán)但在并發(fā)put時仍可能導(dǎo)致數(shù)據(jù)丟失所以高并發(fā)場景仍然不應(yīng)該直接使用HashMap應(yīng)該用ConcurrentHashMap。單憑“死循環(huán)被修復(fù)”這個結(jié)論無法回答出題人真正的意圖。如果你在筆試現(xiàn)場寫了“Java 8 HashMap可以并發(fā)使用”那這道題基本就掛了。再比如TCP的TIME_WAIT模板答案是“2MSL”。但出題人常會在后面加一個小問“為什么不是MSL呢”如果你只是背了答案就會卡住。正確理解是2MSL 1MSL我的最后一個ACK到達(dá)對端的最長時間 1MSL對端重傳FIN到達(dá)我的最長時間這樣能確保舊連接的報(bào)文段徹底消失不會干擾新連接。把原理講到這個深度才叫真正掌握。我建議你復(fù)習(xí)時遵循“三層遞進(jìn)”法第一層掌握概念定義能回答“是什么”。這一層對應(yīng)基礎(chǔ)選擇題是最低要求。第二層掌握原理機(jī)制能解釋“為什么”。比如為什么TCP需要三次握手為什么BTree適合磁盤索引。這一層能幫你應(yīng)對填空、簡答和面試追問。第三層掌握工程權(quán)衡能在場景中做選擇。比如“這個場景選Kafka還是RocketMQ”“這個接口用緩存還是消息隊(duì)列”。這一層不見得筆試會考但它決定了你未來能不能真正勝任系統(tǒng)開發(fā)工程師。很多同學(xué)復(fù)習(xí)只停留在第一層考前刷了上百道選擇題結(jié)果筆試分?jǐn)?shù)不錯但一到面試就露餡。筆試和面試是聯(lián)動的內(nèi)推筆試的成績直接影響面試官對你的初始判斷所以你在卷面上展現(xiàn)的深度最好能支撐你后續(xù)面試的復(fù)盤講述。時間上怎么規(guī)劃如果你還有四周我建議這樣分配第一周快速過一遍計(jì)算機(jī)網(wǎng)絡(luò)和操作系統(tǒng)配合刷選擇題第二周集中刷數(shù)據(jù)結(jié)構(gòu)與算法每天保證三到四道完整編程題不僅要AC還要看題解比較自己的解法和最優(yōu)解法的差距第三周轉(zhuǎn)向數(shù)據(jù)庫和Java并發(fā)尤其是索引和線程池這兩大高頻考點(diǎn)第四周做模擬筆試嚴(yán)格限時用一套往年題或者模擬題完整走一遍流程提前感受壓力?！八㈩}”和“看題”的比例也要控制好。有同學(xué)一天能刷二十道但全是“看懂了就過”實(shí)際手寫時一個邊界條件都寫不對。我的經(jīng)驗(yàn)是每道題如果三十分鐘還寫不出來就去看題解但看完題解后一定要自己重新把AC代碼完整寫一遍而不是直接看代碼。能不能白板寫出來是檢驗(yàn)是否真正會做的唯一標(biāo)準(zhǔn)。6. 查漏補(bǔ)缺清單上考場前再快速過一遍這些點(diǎn)最后分享一份我當(dāng)年整理的查漏補(bǔ)缺清單它不是大而全的知識點(diǎn)百科而是針對“系統(tǒng)開發(fā)工程師”這個崗位筆試?yán)镒钊菀自诩?xì)節(jié)上翻車的點(diǎn)。你可以把它當(dāng)成考前一小時的快速回憶列表。ArrayList和LinkedList的區(qū)別ArrayList基于動態(tài)數(shù)組隨機(jī)訪問快尾部插入快LinkedList基于雙向鏈表頭部插入刪除快但隨機(jī)訪問慢。簡單說ArrayList偏愛“按索引逛商城”LinkedList偏愛“在隊(duì)伍兩頭插隊(duì)”。HashMap的默認(rèn)初始容量是16負(fù)載因子是0.75擴(kuò)容閾值是容量乘以負(fù)載因子。這個0.75是空間和時間開銷的平衡點(diǎn)不是隨便定的。JDK 1.8后鏈表長度超過8且數(shù)組長度大于64時鏈表會轉(zhuǎn)成紅黑樹。volatile關(guān)鍵字的兩層語義可見性和禁止指令重排序。它不能保證原子性所以volatile變量不適合做計(jì)數(shù)器。它的核心應(yīng)用場景是狀態(tài)標(biāo)志位比如線程啟動和停止的標(biāo)志。ThreadLocal的內(nèi)存泄漏問題ThreadLocalMap的key是弱引用value是強(qiáng)引用。如果ThreadLocal對象被回收但線程還存活value就永遠(yuǎn)無法被訪問到導(dǎo)致內(nèi)存泄漏。解決辦法是使用后調(diào)用remove方法清理。TCP的粘包問題由于TCP是字節(jié)流協(xié)議沒有消息邊界應(yīng)用層需要自己定義消息邊界。常見方案是固定長度消息、特殊分隔符、消息頭包含長度字段。這個問題在系統(tǒng)開發(fā)中非常常見尤其在做RPC框架或者Socket自定義協(xié)議時躲不開。進(jìn)程間通信方式管道、消息隊(duì)列、共享內(nèi)存、信號量、Socket。筆試常考的是共享內(nèi)存為什么是最快的IPC方式——因?yàn)樗恍枰獌?nèi)核態(tài)和用戶態(tài)之間的數(shù)據(jù)拷貝而管道和消息隊(duì)列都需要通過內(nèi)核中轉(zhuǎn)。同步和異步、阻塞和非阻塞的區(qū)別同步異步關(guān)注的是消息如何通知阻塞非阻塞關(guān)注的是調(diào)用方在等待結(jié)果時能否干別的事。把它們四個組合起來理解會發(fā)現(xiàn)Java中的NIO是同步非阻塞Netty雖然使用了異步ChannelFuture但底層IO模型是IO多路復(fù)用加非阻塞模式。這個辨析題考得非常細(xì)很多所謂“精通Netty”的同學(xué)都栽在這里。數(shù)據(jù)庫的樂觀鎖和悲觀鎖悲觀鎖就是先拿鎖再操作比如SELECT ... FOR UPDATE樂觀鎖就是操作時帶上版本號或時間戳檢查版本不匹配就重試。出行系統(tǒng)里司機(jī)接單操作就適合樂觀鎖因?yàn)椴l(fā)沖突的頻率相對低用版本號控制即可沒必要長時間鎖行。Redis的數(shù)據(jù)結(jié)構(gòu)和過期策略String、Hash、List、Set、ZSet以及惰性刪除和定期刪除的配合機(jī)制。如果考到Redis持久化至少要說清RDB是快照、AOF是追加日志以及兩者各自優(yōu)缺點(diǎn)。一致性哈希的虛擬節(jié)點(diǎn)為什么要引入虛擬節(jié)點(diǎn)因?yàn)楣?jié)點(diǎn)少時哈希環(huán)容易數(shù)據(jù)傾斜一個機(jī)器扛下大部分流量。虛擬節(jié)點(diǎn)把一個物理機(jī)器映射成多個虛擬位置讓數(shù)據(jù)分布更均勻同時某個節(jié)點(diǎn)故障時它的流量可以由多個其他節(jié)點(diǎn)分?jǐn)偛粫斐蓡我还?jié)點(diǎn)過載。這份清單不是我臨時湊出來的每一行都是往年筆試反復(fù)出現(xiàn)的考點(diǎn)。建議你在考試當(dāng)天早起過一遍不用深入展開看到一個點(diǎn)能想起來龍去脈就算過關(guān)。如果哪個點(diǎn)想不起來立刻翻開筆記快速補(bǔ)一眼不要戀戰(zhàn)。7. 筆試之后成績不是終點(diǎn)復(fù)盤才是開始很多人筆試完就徹底放飛自我了等收到面試通知才開始慌。我自己的經(jīng)驗(yàn)是筆試結(jié)束的當(dāng)天晚上趁著題目的記憶還溫?zé)崃⒖套鲆淮螐?fù)盤。哪怕沒有標(biāo)準(zhǔn)答案也要把自己選的、寫的答案完整記下來然后對照資料逐題分析。這個過程有兩個直接好處。第一個好處面試大概率會追問筆試內(nèi)容。面試官拿到的筆試記錄里除了你的分?jǐn)?shù)還有你的作答詳情。他們特別喜歡挑一道你答錯的題或者一道你解法很奇怪的題問“你為什么這樣設(shè)計(jì)”“當(dāng)時有沒有考慮其他方案”。如果你不復(fù)盤面對這種追問只能編編出來的答案在資深面試官眼里漏洞百出。如果你認(rèn)真復(fù)盤過就能邏輯清晰地重述當(dāng)時的選擇和當(dāng)下的反思這本身就是一次漂亮的面試開場。第二個好處復(fù)盤能幫你找到自己的知識盲區(qū)。比如你發(fā)現(xiàn)數(shù)據(jù)庫隔離級別那道題拿不準(zhǔn)說明你對事務(wù)并發(fā)控制的理解浮于表面那就去補(bǔ)充MVCC和鎖機(jī)制的細(xì)節(jié)。這個盲區(qū)今天不補(bǔ)明天可能在面試中再次暴露。內(nèi)推筆試某種程度上是給了你一次“預(yù)演”的機(jī)會真正的高手會利用它來校準(zhǔn)自己的復(fù)習(xí)方向。再分享一個很務(wù)實(shí)的小技巧每道錯題在復(fù)盤筆記里要寫清“錯因類型”。是概念理解錯誤、細(xì)節(jié)記憶模糊、還是做題時太急看錯了選項(xiàng)把錯因分類之后你會發(fā)現(xiàn)自己的問題往往集中在某幾個模塊。比如我當(dāng)年最大的錯因就是“網(wǎng)絡(luò)題細(xì)節(jié)記憶模糊”所以后續(xù)復(fù)習(xí)時把TCP狀態(tài)機(jī)單獨(dú)畫了三遍面試時遇到相關(guān)問題完全不慌。筆試只是校招長跑中的一站。系統(tǒng)開發(fā)工程師這個崗位真正比拼的不是你會背多少知識點(diǎn)而是你在一個具體的業(yè)務(wù)場景里能不能用系統(tǒng)思維拆解出可行方案。筆試只是這種能力的第一次量化體現(xiàn)。認(rèn)真對待每一次筆試考后認(rèn)真復(fù)盤你的系統(tǒng)設(shè)計(jì)能力、工程判斷力就會在一次次的圈定范圍、取舍決策中慢慢立起來。祝你在接下來的校招中拿到想要的Offer。最后再提一個很多人容易忽略的細(xì)節(jié)內(nèi)推筆試雖然叫“內(nèi)推”但仍然有篩選率內(nèi)推只是幫你從簡歷池里被撈出來筆試成績不過關(guān)一樣會被刷。所以不要以為走內(nèi)推通道就可以放松準(zhǔn)備。相反正因?yàn)閮?nèi)推意味著你有更多人脈背書筆試表現(xiàn)如果太差反而會讓推薦人難堪。以這個心態(tài)去對待每一道題你的答題態(tài)度和嚴(yán)謹(jǐn)程度都會不一樣。