前段時(shí)間整理舊硬盤翻出一份2015年阿里巴巴研發(fā)工程師A筆試卷的回憶版當(dāng)時(shí)跟著校招大軍刷完就丟在角落里了?，F(xiàn)在回頭再看這張卷子反而比當(dāng)年更有嚼頭。很多題目當(dāng)時(shí)只覺得是“面試關(guān)卡”工作幾年后再看會(huì)發(fā)現(xiàn)里面幾乎每一道題都能映射到真實(shí)項(xiàng)目里踩過的坑。無論你是準(zhǔn)備校招的應(yīng)屆生、想跳槽的社招候選人還是單純想檢驗(yàn)一下自己基本功的開發(fā)者這份卷子都值得認(rèn)真盤一盤。2015年的阿里校招筆試整體風(fēng)格就是“基礎(chǔ)扎實(shí)、覆蓋面廣、陷阱多”。它不會(huì)像LeetCode那樣讓你只刷算法題而是把數(shù)據(jù)結(jié)構(gòu)、操作系統(tǒng)、網(wǎng)絡(luò)、語言細(xì)節(jié)、邏輯推理全部揉在一起用一堆選擇題和填空題檢驗(yàn)?zāi)阏嬲挠?jì)算機(jī)功底。這篇文章我會(huì)把那張卷子涉及的考點(diǎn)拆開揉碎補(bǔ)充原題背后的原理、推導(dǎo)過程和實(shí)戰(zhàn)經(jīng)驗(yàn)盡量讓你看完之后不僅知道答案還能明白為什么這么答以及這些知識在今天的工作中到底怎么用。1. 試卷整體風(fēng)格與考察邏輯1.1 2015年這套卷子到底在考什么那年的A卷總體分幾大塊數(shù)據(jù)結(jié)構(gòu)與算法、操作系統(tǒng)、計(jì)算機(jī)網(wǎng)絡(luò)、C/C/Java語言基礎(chǔ)以及少量邏輯推理題。題量不小選擇題占大頭算法題和填空題穿插其中。整體難度并不算“變態(tài)”但對知識面的要求很寬如果本科階段只靠考前突擊大概率會(huì)掛在一些冷門細(xì)節(jié)上。舉個(gè)例子那套卷子里反復(fù)出現(xiàn)幾個(gè)主題二叉樹的各種遍歷、哈希沖突的處理方式、排序算法的時(shí)間復(fù)雜度與穩(wěn)定性、進(jìn)程和線程的區(qū)別、死鎖產(chǎn)生的必要條件、TCP握手過程、虛函數(shù)和靜態(tài)綁定的區(qū)別等等。這些題目單拎出來都不難但放在同一張卷子里節(jié)奏感就很重要。如果你在某一類題上卡太久后面大題的思考時(shí)間就會(huì)被壓縮。我記得當(dāng)時(shí)考完很多人最大的感受是“題都見過但選項(xiàng)怎么設(shè)計(jì)得這么刁鉆”。這是因?yàn)榘⒗锍鲱}很喜歡在“看似明白”的地方埋坑比如問“以下哪種排序算法是穩(wěn)定的”選項(xiàng)里會(huì)混入堆排序和快速排序兩個(gè)經(jīng)典不穩(wěn)定算法再放一個(gè)容易記混的希爾排序。這種題不是考察你背沒背過而是看你有沒有真正理解排序過程。1.2 為什么一張八年前的卷子還有參考價(jià)值可能有人會(huì)說都這么多年了互聯(lián)網(wǎng)技術(shù)棧早就變了還翻老黃歷干嘛。但恰恰相反這份卷子代表的是一類“經(jīng)典大廠基礎(chǔ)題”的范式而這類范式到今天依然是面試的主流。你可以去翻翻現(xiàn)在各大廠的筆試算法題確實(shí)更偏向LeetCode風(fēng)格但基礎(chǔ)知識的考察方式幾乎沒有變樹、圖、動(dòng)態(tài)規(guī)劃、并發(fā)、網(wǎng)絡(luò)依然是核心中的核心。更重要的是這套卷子的知識體系是“穩(wěn)定”的。語言可以換框架可以變但操作系統(tǒng)調(diào)度、TCP協(xié)議、二叉樹遍歷這些底層原理不會(huì)過時(shí)。你甚至可以把它當(dāng)成一份“計(jì)算機(jī)基礎(chǔ)能力自檢清單”不看答案做一遍就能知道自己哪些地方早就還給老師了。我當(dāng)時(shí)做完之后的感受是真正拉開差距的往往不是那些偏題怪題而是基礎(chǔ)題的正確率和速度。所以如果你現(xiàn)在正準(zhǔn)備面試我建議不要只悶頭刷LeetCode花兩天時(shí)間過一遍這類經(jīng)典筆試卷性價(jià)比極高。2. 核心考點(diǎn)逐個(gè)拆解高頻題與隱藏考點(diǎn)2.1 數(shù)據(jù)結(jié)構(gòu)樹與圖是絕對重點(diǎn)這套卷子里數(shù)據(jù)結(jié)構(gòu)部分占比很高樹又是數(shù)據(jù)結(jié)構(gòu)里的重中之重。像“已知二叉樹的前序遍歷和中序遍歷求后序遍歷”這類題幾乎年年都有變體。別小看它很多人筆試時(shí)能推出來但到面試現(xiàn)場手寫代碼時(shí)就容易慌亂。核心思路其實(shí)就一句話前序遍歷確定根節(jié)點(diǎn)中序遍歷劃分左右子樹遞歸進(jìn)行。還有一個(gè)高頻考點(diǎn)是二叉樹層次遍歷。我記得卷子里有題問“層次遍歷需要借助什么數(shù)據(jù)結(jié)構(gòu)”答案是隊(duì)列。這道題看似簡單但它背后其實(shí)是BFS的思路跟圖論里的廣度優(yōu)先遍歷一脈相承。如果你能把樹的層次遍歷和圖BFS放在一起理解后面遇到“求二叉樹最小深度”這類變種題就不慌了。圖的部分那套卷子考過拓?fù)渑判蚝虳ijkstra算法的基本思想。Dijkstra的題我記得是給了圖讓寫出從源點(diǎn)到各點(diǎn)的最短路徑過程。這里有個(gè)常見的坑Dijkstra不能處理負(fù)權(quán)邊選項(xiàng)里經(jīng)常會(huì)拿負(fù)權(quán)邊來干擾你。如果你理解它的貪心本質(zhì)就知道一旦某個(gè)節(jié)點(diǎn)被確定最短路徑下次就不會(huì)再更新而負(fù)權(quán)邊可能在后面讓某條路徑更短所以這個(gè)前提不成立。2.2 算法設(shè)計(jì)動(dòng)態(tài)規(guī)劃與貪心是拉開差距的地方那年年有“動(dòng)態(tài)規(guī)劃”的題多是選擇題形式給你一個(gè)場景讓你選遞推公式。比如經(jīng)典的爬樓梯問題一次可以爬1階或2階爬上n階有幾種方法答案就是斐波那契數(shù)列dp[n] dp[n-1] dp[n-2]。這種題對了就過了但真正深入面試時(shí)面試官一定會(huì)追問你是怎么想到狀態(tài)轉(zhuǎn)移方程的邊界條件是什么能不能優(yōu)化空間復(fù)雜度所以我在復(fù)盤時(shí)給自己定了一個(gè)規(guī)矩每道DP題都按三步走——定義狀態(tài)、寫轉(zhuǎn)移方程、初始化邊界。這套方法論到現(xiàn)在寫業(yè)務(wù)代碼時(shí)依然受用。貪心算法在卷子里也有出現(xiàn)典型的是“活動(dòng)安排問題”變體。這種題的破題點(diǎn)在于“按結(jié)束時(shí)間排序”每次選結(jié)束最早的且不沖突的活動(dòng)。當(dāng)年很多同學(xué)會(huì)習(xí)慣性按開始時(shí)間排序結(jié)果就是局部最優(yōu)不等于全局最優(yōu)。這類題想表達(dá)的核心思想是貪心不是盲目選看起來最爽的而是要有嚴(yán)格的證明邏輯。說句實(shí)話算法題部分的區(qū)分度就在于你有沒有系統(tǒng)訓(xùn)練過。如果只是零散刷題遇到“最長公共子序列”“編輯距離”“0-1背包”這些經(jīng)典模型現(xiàn)場很容易卡殼。我建議你把經(jīng)典DP模型整理成模板面試前集中過一遍尤其是狀態(tài)定義和空間優(yōu)化手段滾動(dòng)數(shù)組筆試經(jīng)常會(huì)考到空間優(yōu)化版本。2.3 操作系統(tǒng)與計(jì)算機(jī)網(wǎng)絡(luò)背了不一定得分理解了才行操作系統(tǒng)部分那套卷子反復(fù)出現(xiàn)的是進(jìn)程與線程的區(qū)別、死鎖的四個(gè)必要條件、虛擬內(nèi)存與頁面置換算法。其中“死鎖必要條件”屬于死記硬背就能拿分的題互斥、持有并等待、不可剝奪、循環(huán)等待但如果面試官追加一題“怎么避免死鎖”很多人就只會(huì)背“破壞四個(gè)條件之一”。其實(shí)更合適的回答方式是結(jié)合案例比如數(shù)據(jù)庫里通過按固定順序加鎖來破壞循環(huán)等待條件這就是工程里的實(shí)際做法。網(wǎng)絡(luò)部分印象最深的是TCP三次握手和四次揮手。那套卷子不僅考“為什么需要三次握手”還考了TIME_WAIT狀態(tài)持續(xù)時(shí)間。很多人會(huì)把“四次揮手”背得滾瓜爛熟但問你“為什么客戶端最后要等2MSL”時(shí)就答不上來了。本質(zhì)原因有兩個(gè)一是確保最后一個(gè)ACK能到達(dá)服務(wù)端如果丟失還能重傳二是讓舊連接中的報(bào)文在網(wǎng)絡(luò)中消逝避免干擾新連接。這兩個(gè)點(diǎn)缺一不可面試時(shí)能講清楚的話會(huì)很加分。還有一道“從輸入U(xiǎn)RL到頁面展示發(fā)生了什么”的綜合題當(dāng)時(shí)以選擇題形式出現(xiàn)現(xiàn)在則是面試必考題。這道題把DNS解析、TCP連接、HTTP請求、瀏覽器渲染全串起來了屬于典型的基礎(chǔ)知識整合。建議你自己動(dòng)手畫一遍這個(gè)流程每個(gè)環(huán)節(jié)至少能說出一個(gè)關(guān)鍵細(xì)節(jié)比如DNS用的是UDP還是TCP、HTTP1.0和1.1的區(qū)別、HTTPS握手多做了什么。這些細(xì)節(jié)都在2015年那套卷子的“射程”之內(nèi)只是當(dāng)時(shí)很多人沒意識到要這么深挖。2.4 語言基礎(chǔ)與工程習(xí)慣C/C和Java的細(xì)節(jié)題語言部分的題目C側(cè)重考察指針、引用、虛函數(shù)、const用法Java則側(cè)重考察HashMap原理、異常處理、線程安全集合。我記得有一道很經(jīng)典的題是“C中以下哪種類型不能作為模板參數(shù)”選項(xiàng)包括int、const char*、函數(shù)指針等等。答案是“局部變量”因?yàn)槟０鍏?shù)必須在編譯期確定而局部變量的地址要到運(yùn)行期才知道。這種題沒有實(shí)際寫過模板代碼的人很容易選錯(cuò)但它其實(shí)考察的是對C編譯模型的理解。Java方面HashMap的底層實(shí)現(xiàn)是那幾年的熱門考點(diǎn)。2015年的版本還是“數(shù)組鏈表”的結(jié)構(gòu)如果被問到“HashMap為什么是線程不安全的”很多人知道答案但面試官深挖“多線程put時(shí)會(huì)發(fā)生什么”就有人懵了。真實(shí)場景下可能出現(xiàn)兩個(gè)線程同時(shí)觸發(fā)resize導(dǎo)致鏈表成環(huán)進(jìn)而引發(fā)死循環(huán)。后續(xù)Java 8引入了紅黑樹優(yōu)化但理解“為什么不安全”的邏輯一直沒變。語言題目看起來很瑣碎但它們其實(shí)是工程能力的風(fēng)向標(biāo)。從一份考卷里的語言題面試官能快速判斷你是會(huì)“寫代碼”還是會(huì)“編程”。所謂“會(huì)寫代碼”就是語法熟練拿到需求能實(shí)現(xiàn)“會(huì)編程”則意味著你理解內(nèi)存布局、理解并發(fā)問題、理解編譯鏈接過程。當(dāng)年這張卷子的語言細(xì)節(jié)題本質(zhì)上就是在篩選后者。3. 從筆試卷到工程實(shí)踐這些知識現(xiàn)在怎么用3.1 算法思維落地LRU緩存與任務(wù)依賴也許你會(huì)覺得筆試?yán)锏乃惴}和日常工作關(guān)系不大但真不是這樣。就拿LRULeast Recently Used緩存淘汰算法來說它幾乎是2015年各類筆試的常客現(xiàn)在則是后端開發(fā)的必修課。實(shí)現(xiàn)思路不復(fù)雜哈希表雙向鏈表哈希表保證O(1)查找雙向鏈表保證O(1)插入和刪除。每次訪問一個(gè)key就把它移到鏈表頭部緩存滿了就把鏈表尾部的節(jié)點(diǎn)淘汰掉。這里我貼一段簡化的Java實(shí)現(xiàn)思路筆試和面試手寫都夠用class LRUCache { private MapInteger, Node map; private DoubleList cache; private int capacity; public int get(int key) { if (!map.containsKey(key)) return -1; Node node map.get(key); cache.remove(node); cache.addFirst(node); return node.val; } public void put(int key, int value) { if (map.containsKey(key)) { Node node map.get(key); node.val value; cache.remove(node); cache.addFirst(node); return; } if (cache.size() capacity) { Node last cache.removeLast(); map.remove(last.key); } Node newNode new Node(key, value); cache.addFirst(newNode); map.put(key, newNode); } }你可能會(huì)問工作里哪里會(huì)用到LRU很簡單任何“緩存容量有限但希望保留最近常訪問數(shù)據(jù)”的場景都適合LRU策略。我在做網(wǎng)關(guān)限流時(shí)就曾經(jīng)用類似LRU的結(jié)構(gòu)做“最近訪問用戶”的緩存避免每次請求都查數(shù)據(jù)庫。理解了它再遇到Redis的淘汰策略allkeys-lru、volatile-lru時(shí)你也會(huì)更容易理解背后的權(quán)衡。另一個(gè)例子是拓?fù)渑判?。筆試?yán)锟赡苤豢家粋€(gè)DAG有向無環(huán)圖的排序序列但工程里任務(wù)編排工具比如工作流引擎、SQL血緣分析、構(gòu)建工具依賴解析全部依賴它。我之前在做數(shù)據(jù)同步任務(wù)依賴時(shí)就需要確認(rèn)各表之間的同步先后順序如果存在循環(huán)依賴數(shù)據(jù)就會(huì)死鎖。用拓?fù)渑判虬阉腥蝿?wù)排個(gè)序一眼就能找出有沒有環(huán)。3.2 并發(fā)與性能優(yōu)化從死鎖到無鎖編程筆試?yán)镆蟊痴b的死鎖四個(gè)必要條件在工作里真的會(huì)遇到只是場景變成了“多個(gè)線程持有鎖互相等待對方釋放”。我自己就踩過一個(gè)坑一個(gè)支付回調(diào)流程里先鎖了訂單鎖再鎖賬戶鎖另一個(gè)退款流程卻先鎖賬戶鎖再鎖訂單鎖結(jié)果在高并發(fā)下偶發(fā)死鎖線上報(bào)警。排查到最后發(fā)現(xiàn)就是典型的循環(huán)等待。修復(fù)方式很直接所有地方都按固定的順序加鎖。如果那套筆試卷還停留在“會(huì)背條件”現(xiàn)在的你應(yīng)該更進(jìn)一步理解現(xiàn)代編程里減少死鎖的手段。比如盡量縮小鎖的粒度、用超時(shí)鎖、用讀寫鎖或者在合適場景下直接使用無鎖數(shù)據(jù)結(jié)構(gòu)。Java里的ConcurrentHashMap、AtomicLongC里的無鎖隊(duì)列都是朝這個(gè)方向的嘗試。有一道經(jīng)典的生產(chǎn)者消費(fèi)者模型當(dāng)年筆試考的是信號量P/V操作。工作后你會(huì)發(fā)現(xiàn)它就隱藏在許多MQ消息隊(duì)列的實(shí)現(xiàn)里。生產(chǎn)端往隊(duì)列里丟消息消費(fèi)端拉取消息隊(duì)列為空時(shí)消費(fèi)者就阻塞等待。理解了這一個(gè)模型再去看Kafka、RocketMQ的消費(fèi)組機(jī)制、阻塞隊(duì)列實(shí)現(xiàn)都會(huì)輕松很多。3.3 從筆試題到系統(tǒng)設(shè)計(jì)雛形2015年的研發(fā)工程師A卷幾乎沒有系統(tǒng)設(shè)計(jì)大題但里面考察的網(wǎng)絡(luò)基礎(chǔ)、緩存思想、并發(fā)模型恰恰是系統(tǒng)設(shè)計(jì)的原料。比如一致性哈希當(dāng)年很多同學(xué)只是在面經(jīng)里聽過而現(xiàn)在做分布式緩存路由時(shí)它幾乎是默認(rèn)方案。分布式緩存的數(shù)據(jù)分布和節(jié)點(diǎn)擴(kuò)容一直是個(gè)麻煩假如用簡單的hash(key)%N做路由N一變大部分key都要重新映射緩存會(huì)瞬間失效也就是緩存雪崩的來源之一。一致性哈希把哈希值空間組織成環(huán)每個(gè)節(jié)點(diǎn)負(fù)責(zé)環(huán)上的一段范圍增加或刪除節(jié)點(diǎn)時(shí)只影響相鄰節(jié)點(diǎn)上的少量數(shù)據(jù)。理解了筆試?yán)锏墓！㈡湵?、二分查找理解一致性哈希就不難關(guān)鍵是你愿不愿意把知識點(diǎn)從“做題”上升為“建模”。再比如TCP的握手和揮手雖然你在后端業(yè)務(wù)代碼里不會(huì)直接碰它但排查超時(shí)問題和性能瓶頸時(shí)就能用上?？蛻舳藞?bào)connect超時(shí)你要判斷是不是網(wǎng)絡(luò)層丟包是不是服務(wù)端backlog隊(duì)列滿了服務(wù)器大量TIME_WAIT連接堆積你要知道是不是客戶端主動(dòng)關(guān)閉連接太頻繁或者長連接復(fù)用策略沒做好。這些排查思路的根都在基礎(chǔ)知識只是學(xué)校不會(huì)告訴你它們的工程應(yīng)用場景。4. 備考與實(shí)戰(zhàn)中的常見問題與排查技巧4.1 時(shí)間分配與做題順序的實(shí)戰(zhàn)建議2015年那場筆試我印象很深刻題量不小選擇題就三十多道后面還有填空題和編程題。如果死磕一道不會(huì)的選擇題很容易造成時(shí)間失控。我當(dāng)時(shí)的策略是先快速過一遍所有題目把一眼會(huì)做的立刻做掉不會(huì)的先標(biāo)記跳過最后再回頭攻克。這樣能保證基本分先拿到心態(tài)也穩(wěn)。具體時(shí)間分配上選擇題平均每題不超過2分鐘超過就跳。算法題通常留30分鐘以上。順便說一句有時(shí)候選擇題本身就是提示比如后面算法題會(huì)用到前面某個(gè)題的數(shù)據(jù)結(jié)構(gòu)你回頭看可能會(huì)發(fā)現(xiàn)出題人故意埋的線索這能幫你更快理解題意。4.2 經(jīng)典踩坑點(diǎn)指針、邊界條件和復(fù)雜度第一個(gè)容易踩坑的地方是指針與引用。C里“傳值”和“傳引用”在語法上差別很小但行為完全不同。曾經(jīng)有一道題問vector作為函數(shù)參數(shù)怎樣傳遞才能在函數(shù)內(nèi)修改原對象。答案是傳引用或傳指針如果傳值函數(shù)里的修改只影響副本。這個(gè)坑在實(shí)戰(zhàn)里也很常見你自己寫代碼時(shí)如果發(fā)現(xiàn)“函數(shù)里改了值外面沒變化”第一反應(yīng)就該檢查是不是傳了副本。第二個(gè)經(jīng)典坑是二分查找的邊界條件。筆試?yán)锟赡苡小霸谟行驍?shù)組中查找目標(biāo)值的第一個(gè)位置”這類題很多人死循環(huán)或越界。我建議你直接記住一套固定模板左閉右開low0, highn循環(huán)條件是lowhighmidlow(high-low)/2。熟練之后不要在考場上“現(xiàn)推邊界”因?yàn)榫o張狀態(tài)下很容易寫錯(cuò)。第三個(gè)坑是復(fù)雜度分析不準(zhǔn)。很多人能寫出正確代碼但沒算清楚時(shí)間復(fù)雜度和空間復(fù)雜度。面試官問“你這個(gè)解法還能不能優(yōu)化”其實(shí)就是想讓你意識到是不是從O(n^2)降到O(n log n)甚至O(n)。筆試如果選擇題里給了一個(gè)解法復(fù)雜度選項(xiàng)你就得從代碼里的循環(huán)嵌套和遞歸層數(shù)去判斷不能憑感覺。4.3 復(fù)盤方法論怎么把一套卷子吃透刷完一套卷子對完答案并不算結(jié)束。我見過太多人考完只看個(gè)分?jǐn)?shù)不分析錯(cuò)因結(jié)果下次遇到類似題還是錯(cuò)。我給自己的復(fù)盤流程是三道工序第一道對每道錯(cuò)題寫“錯(cuò)因標(biāo)簽”。是知識盲區(qū)、計(jì)算失誤、還是審題不清分類之后你會(huì)發(fā)現(xiàn)計(jì)算失誤和審題不清占掉一半以上而不是你真的不會(huì)。第二道對知識盲區(qū)題目去翻教材或優(yōu)質(zhì)博客把一個(gè)知識點(diǎn)擴(kuò)展成一張知識網(wǎng)。比如錯(cuò)了一道“TCP三次握手為什么不是兩次”那就順便把“四次揮手為什么是四次”“SYN Flood攻擊原理”一起搞明白。第三道把有價(jià)值的題目沉淀成自己的一套“錯(cuò)題筆記”按專題分類考前過一遍。這個(gè)方法我從校招一直用到跳槽效果非常明顯。真題的價(jià)值不在于押中原題而在于通過它暴露你的知識盲區(qū)并且逼你把零散的知識串成體系。當(dāng)年和我一起刷題的朋友有的只刷了數(shù)量有的注重復(fù)盤最終面試結(jié)果的差距非常明顯。最后分享一個(gè)個(gè)人習(xí)慣每當(dāng)要準(zhǔn)備面試或系統(tǒng)梳理知識時(shí)我會(huì)把這張2015年的卷子重新做一遍當(dāng)作一次“基礎(chǔ)體檢”。每次做都會(huì)有新的體會(huì)。第一次做我感受最深的是“怎么這么多不會(huì)”第二次做我感悟到“原來出題人是在考工程思維”到后來再看我關(guān)注的是“這個(gè)知識點(diǎn)還能怎么變著花樣考”?；A(chǔ)這東西一直在那里關(guān)鍵是你在不同階段能不能看懂它更深的層次。技術(shù)變化再快計(jì)算機(jī)的核心原理依然穩(wěn)固這就是經(jīng)典筆試卷最值得反復(fù)咀嚼的地方。