前幾天整理云盤(pán)里的舊資料翻出當(dāng)年備戰(zhàn)微軟校招時(shí)整理的一套題目正是網(wǎng)上流傳很廣的2014年研發(fā)工程師筆試卷B。那段時(shí)間我把它來(lái)回做了三遍每一遍都能發(fā)現(xiàn)新的問(wèn)題最后靠著這套題的復(fù)盤(pán)拿到了面試機(jī)會(huì)?，F(xiàn)在回頭看這套題雖然已經(jīng)過(guò)去快十年但它的考察思路和今天的算法面試依然高度一致非常適合正在準(zhǔn)備大廠研發(fā)崗、或者想檢驗(yàn)自己C/C和算法基本功的人當(dāng)作自測(cè)材料。先說(shuō)結(jié)論這套筆試卷B整體難度中等偏上不算變態(tài)但陷阱非常多。它不考任何框架、不考花哨的新技術(shù)核心就三塊——C/C語(yǔ)言細(xì)節(jié)、算法與數(shù)據(jù)結(jié)構(gòu)基本功、快速編碼能力。如果你能拿75分以上面試輪是很有希望進(jìn)的。下面我把這套題的題型結(jié)構(gòu)、高頻考點(diǎn)和編程大題的完整解法拆開(kāi)講順便把我踩過(guò)的坑也一并寫(xiě)出來(lái)。1. 2014年微軟研發(fā)筆試卷B整體拆解與出題邏輯1.1 筆試卷的題型分布與考察維度我手頭這份回憶版B卷結(jié)構(gòu)大概是這樣的選擇題約10道、填空題和簡(jiǎn)答題2到3道、編程大題2道外加一道選做的附加題。總時(shí)長(zhǎng)90分鐘到120分鐘卷面滿(mǎn)分100分左右。選擇題每題分值不高但勝在覆蓋面廣幾乎每道題都埋了1到2個(gè)坑簡(jiǎn)答題主要考代碼理解和邏輯推導(dǎo)比如給你一段程序讓你寫(xiě)出輸出結(jié)果編程大題則是整張卷子的重頭戲一道題動(dòng)輒20到30分基本決定你能不能過(guò)線(xiàn)。從考察維度上看這張卷子其實(shí)很克制的。它不考操作系統(tǒng)源碼、不考編譯原理、不考網(wǎng)絡(luò)協(xié)議細(xì)節(jié)重心非常明確C/C語(yǔ)言細(xì)節(jié)指針、數(shù)組、結(jié)構(gòu)體、虛函數(shù)、內(nèi)存布局大概占30%左右。算法與數(shù)據(jù)結(jié)構(gòu)鏈表、字符串、排序、查找、遞歸大概占50%左右。基礎(chǔ)系統(tǒng)概念進(jìn)程線(xiàn)程、堆棧區(qū)別、動(dòng)態(tài)鏈接之類(lèi)的概念題占剩下的20%。這個(gè)比例你品一下就知道微軟當(dāng)年的校招邏輯就是“算法定天下”。為什么這么設(shè)計(jì)后面細(xì)說(shuō)。1.2 為什么微軟喜歡靠算法題篩人有人可能覺(jué)得微軟這種體量的公司筆試應(yīng)該考系統(tǒng)設(shè)計(jì)、考業(yè)務(wù)場(chǎng)景其實(shí)恰恰相反。校招研發(fā)崗的筆試和社招完全不是一個(gè)路子。校招候選人沒(méi)有實(shí)際項(xiàng)目經(jīng)驗(yàn)面試官能快速判斷的就是兩件事第一你的計(jì)算機(jī)基礎(chǔ)扎不扎實(shí)第二你的腦子轉(zhuǎn)得快不快、代碼能不能寫(xiě)利索。算法題恰好同時(shí)滿(mǎn)足這兩個(gè)需求。一道反轉(zhuǎn)鏈表能看出你對(duì)指針和內(nèi)存的理解一道第K大元素能看出你的排序和分治功底。更重要的是算法題可以在兩個(gè)小時(shí)內(nèi)批量考察大量候選人成本低、信號(hào)強(qiáng)、很難靠背題蒙混過(guò)關(guān)。微軟面試中著名的“白板編程”文化從筆試階段就已經(jīng)開(kāi)始鋪墊了。所以你看這套2014年筆試卷B它的出題邏輯其實(shí)很簡(jiǎn)單用選擇題過(guò)濾那些基礎(chǔ)不牢的人再用編程大題留下真正能寫(xiě)代碼的人。明白這個(gè)邏輯你就知道備考重點(diǎn)應(yīng)該放在哪兒了——說(shuō)白了就是兩板斧語(yǔ)言基礎(chǔ)吃透、算法題刷透。1.3 分?jǐn)?shù)權(quán)重與時(shí)間分配策略這里直接給一份我用下來(lái)覺(jué)得最舒服的時(shí)間分配方案。假設(shè)總時(shí)長(zhǎng)120分鐘題型建議用時(shí)策略選擇題20分鐘快速掃題不確定的先標(biāo)記不戀戰(zhàn)簡(jiǎn)答題15分鐘寫(xiě)出關(guān)鍵點(diǎn)即可不要長(zhǎng)篇大論編程大題60分鐘每題留足20-30分鐘先想思路再寫(xiě)碼附加題15分鐘大題搞定了才碰拿不到不虧?rùn)z查10分鐘重點(diǎn)檢查邊界條件和數(shù)組越界我的個(gè)人習(xí)慣是拿到卷子先花兩分鐘通讀一遍不是逐字看而是掃一眼每道題大概在考什么心里有個(gè)數(shù)。尤其是編程大題我會(huì)先看題目描述和輸入輸出示例在腦子里初步構(gòu)思一下解法然后再回頭做選擇填空。這樣等做到大題的時(shí)候思路其實(shí)已經(jīng)醞釀了一會(huì)兒落筆會(huì)順很多。2. 選擇題高頻考點(diǎn)深度解析2.1 C/C內(nèi)存與指針的基本功選擇題里幾乎每年必考的就是sizeof和指針之間的關(guān)系。我記得B卷里就有一道類(lèi)似的題表面上看是一道普通的代碼輸出題實(shí)際上坑全在數(shù)組名退化上。void foo(int arr[]) { // arr 是函數(shù)參數(shù)本質(zhì)是一個(gè)指針 printf(%zu\n, sizeof(arr)); // 64位系統(tǒng)上輸出8 } int main() { int arr[10]; printf(%zu\n, sizeof(arr)); // 輸出40 printf(%zu\n, sizeof(arr) / sizeof(arr[0])); // 輸出10 foo(arr); // 輸出8 return 0; }這里有兩層坑。第一層很多人知道sizeof(arr)在main函數(shù)里是40因?yàn)閿?shù)組名代表的是整個(gè)數(shù)組10個(gè)int乘以4字節(jié)。第二層坑在于數(shù)組作為函數(shù)參數(shù)傳遞時(shí)會(huì)退化為指向首元素的指針?biāo)心阋詾槭恰皞鲾?shù)組”的寫(xiě)法實(shí)際傳的都是指針。所以在foo里面sizeof(arr)返回的是指針的大小64位環(huán)境下就是8。類(lèi)似的還有字符串相關(guān)的陷阱char *p hello; char arr[] hello; printf(%zu %zu\n, sizeof(p), sizeof(arr)); // 8 6 printf(%zu %zu\n, strlen(p), strlen(arr)); // 5 5sizeof(arr)是6因?yàn)閿?shù)組版本會(huì)在末尾自動(dòng)加一個(gè)\0sizeof(p)是8指針大小跟字符串長(zhǎng)度無(wú)關(guān)而strlen永遠(yuǎn)數(shù)到\0為止所以?xún)烧叨际?。這道題如果對(duì)字符串字面量的存儲(chǔ)機(jī)制不熟悉很容易把sizeof(p)誤寫(xiě)成6。這類(lèi)題考察的核心就一句話(huà)數(shù)組名、指針、字符串字面量這三者之間的區(qū)別。建議備考時(shí)把sizeof和strlen的對(duì)比、數(shù)組參數(shù)退化、字符數(shù)組和字符指針的區(qū)別這三個(gè)知識(shí)點(diǎn)反復(fù)吃透選擇題的C/C部分基本就能拿下大半。2.2 虛函數(shù)、虛表與運(yùn)行時(shí)多態(tài)B卷里還有一道關(guān)于虛函數(shù)的題我記得類(lèi)似這樣一個(gè)基類(lèi)指針指向派生類(lèi)對(duì)象調(diào)用一個(gè)虛函數(shù)和一個(gè)普通函數(shù)分別調(diào)用的是哪個(gè)版本。class Base { public: virtual void show() { printf(Base\n); } void normal() { printf(Base normal\n); } }; class Derived : public Base { public: void show() override { printf(Derived\n); } void normal() { printf(Derived normal\n); } }; int main() { Base *p new Derived(); p-show(); // 輸出 Derived p-normal(); // 輸出 Base normal delete p; }這道題對(duì)熟悉多態(tài)的人來(lái)說(shuō)很簡(jiǎn)單但當(dāng)時(shí)有不少同學(xué)栽在第二行。原因就是沒(méi)有記清楚只有虛函數(shù)才具備動(dòng)態(tài)綁定能力。p-show()運(yùn)行時(shí)通過(guò)虛表找到Derived的版本輸出Derived而normal()沒(méi)有加virtual編譯階段就根據(jù)指針類(lèi)型決定調(diào)用Base的版本。還有一個(gè)擴(kuò)展考點(diǎn)是析構(gòu)函數(shù)為什么要聲明為虛函數(shù)Base *p new Derived(); delete p; // 如果析構(gòu)函數(shù)不是虛函數(shù)只會(huì)調(diào)用Base的析構(gòu)可能造成內(nèi)存泄漏這也是微軟筆試面試中反復(fù)出現(xiàn)的細(xì)節(jié)題。本質(zhì)原因是delete一個(gè)基類(lèi)指針時(shí)編譯器在編譯期只能看到指針的靜態(tài)類(lèi)型不知道它到底指向的是哪個(gè)派生類(lèi)對(duì)象。如果析構(gòu)函數(shù)不是虛函數(shù)就不會(huì)觸發(fā)動(dòng)態(tài)綁定Derived部分可能得不到正確釋放。應(yīng)對(duì)這類(lèi)題我建議你梳理一張“virtual機(jī)制”的腦圖虛函數(shù)如何實(shí)現(xiàn)動(dòng)態(tài)綁定、虛表和虛指針的存在位置、構(gòu)造函數(shù)不能是虛函數(shù)的原因、析構(gòu)函數(shù)建議聲明為虛函數(shù)的原因。這幾點(diǎn)一旦理清相關(guān)選擇題無(wú)論怎么變形都不會(huì)被難住。2.3 數(shù)據(jù)結(jié)構(gòu)復(fù)雜度數(shù)組、鏈表、哈希表怎么選有一類(lèi)選擇題特別有意思題目會(huì)給出幾個(gè)常見(jiàn)操作問(wèn)哪種數(shù)據(jù)結(jié)構(gòu)效率最高。這類(lèi)題本質(zhì)上是在考察對(duì)復(fù)雜度的理解而不是死記硬背結(jié)論。比如B卷里有道題要求在頻繁插入、刪除的場(chǎng)景下選擇合適的數(shù)據(jù)結(jié)構(gòu)答案肯定是鏈表但你要能解釋為什么。操作數(shù)組鏈表哈希表隨機(jī)訪(fǎng)問(wèn)O(1)O(n)O(1) 平均頭部插入O(n)O(1)不一定中間插入O(n)O(1)不適用按值查找O(n)O(n)O(1) 平均這里要特別注意“平均”兩個(gè)字。哈希表在有大量沖突時(shí)會(huì)退化最壞情況下查找是O(n)所以在對(duì)時(shí)延要求苛刻的場(chǎng)合不能無(wú)腦選哈希表。我記得那套卷子里有一道引申題問(wèn)“如果哈希函數(shù)選得不好所有元素都映射到同一個(gè)桶里那查找復(fù)雜度是多少”正確答案是O(n)很多人會(huì)錯(cuò)選O(1)。數(shù)組最大的優(yōu)勢(shì)是緩存局部性好實(shí)際運(yùn)行速度往往比鏈表快這也是一個(gè)很多人忽略的點(diǎn)。筆試題目里如果只說(shuō)“存儲(chǔ)一連串整數(shù)主要做順序遍歷”選數(shù)組通常比鏈表更合理因?yàn)閮?nèi)存是連續(xù)的CPU緩存命中率遠(yuǎn)高于鏈表。這個(gè)結(jié)論在紙上分析復(fù)雜度時(shí)看不到但微軟這種做產(chǎn)品的公司出題人心里是裝著實(shí)際工程的。2.4 位運(yùn)算技巧兩行代碼解決一個(gè)經(jīng)典問(wèn)題B卷里關(guān)于位運(yùn)算的題不算難但很考驗(yàn)“有沒(méi)有見(jiàn)過(guò)這類(lèi)技巧”。比如判斷一個(gè)正整數(shù)是不是2的冪int isPowerOfTwo(int n) { return n 0 (n (n - 1)) 0; }原理很簡(jiǎn)單一個(gè)數(shù)如果是2的冪它的二進(jìn)制表示里只有一個(gè)1比如4是1008是1000。減去1以后原來(lái)1的位置變成0后面的位全部變成1。如果這個(gè)數(shù)原本只有一個(gè)1n (n - 1)的結(jié)果一定是0。如果原本有多個(gè)1結(jié)果是去掉最低位的1之后剩下的值不會(huì)是0。另一個(gè)經(jīng)典題是統(tǒng)計(jì)一個(gè)整數(shù)二進(jìn)制表示里有多少個(gè)1int countOnes(int n) { int count 0; while (n) { n (n - 1); count; } return count; }這段代碼每次循環(huán)把最低位的1變成0循環(huán)次數(shù)等于1的個(gè)數(shù)而不是二進(jìn)制位數(shù)。從負(fù)數(shù)到正數(shù)、從0到最大值都能正確統(tǒng)計(jì)。選擇題里問(wèn)“對(duì)于整數(shù)256這個(gè)函數(shù)返回多少”答案是1如果對(duì)位運(yùn)算不敏感很容易算成8或者其他數(shù)字。這類(lèi)位運(yùn)算技巧不建議死記代碼而是理解“減去1翻轉(zhuǎn)低位”這個(gè)規(guī)律考試時(shí)即使忘了具體實(shí)現(xiàn)也能現(xiàn)場(chǎng)推出來(lái)。平時(shí)準(zhǔn)備的時(shí)候把移位、異或、與或非的常見(jiàn)套路整理到一起每天看一遍選擇題基本不會(huì)失分。3. 編程大題從思路到實(shí)現(xiàn)的完整代碼3.1 鏈表反轉(zhuǎn)迭代、遞歸和尾遞歸鏈表反轉(zhuǎn)是微軟筆試面試?yán)锍霈F(xiàn)頻率最高的題之一2014年這套B卷里我記得也有它的變體。它考察的點(diǎn)非常集中指針操作、邊界處理、循環(huán)或遞歸思維。題目一般長(zhǎng)這樣給定一個(gè)單鏈表反轉(zhuǎn)后返回新的頭節(jié)點(diǎn)。迭代寫(xiě)法是最容易理解的核心思路是遍歷過(guò)程中不斷翻轉(zhuǎn)當(dāng)前節(jié)點(diǎn)的next方向struct ListNode { int val; struct ListNode *next; }; struct ListNode* reverseList(struct ListNode* head) { struct ListNode *prev NULL; struct ListNode *curr head; while (curr ! NULL) { struct ListNode *next curr-next; // 先保存下一個(gè)節(jié)點(diǎn) curr-next prev; // 翻轉(zhuǎn)當(dāng)前節(jié)點(diǎn)的指針 prev curr; // prev 前移 curr next; // curr 前移 } return prev; // prev 最后指向原鏈表的尾節(jié)點(diǎn)也就是新鏈表的頭 }這里最容易犯的錯(cuò)誤是忘記在修改curr-next之前保存next。一旦先把指針?lè)D(zhuǎn)了后面的節(jié)點(diǎn)就丟了。我當(dāng)年第一次寫(xiě)這個(gè)題就踩了這坑debug了半天所以在代碼注釋里也特別標(biāo)出來(lái)了。遞歸寫(xiě)法更精簡(jiǎn)但理解門(mén)檻更高struct ListNode* reverseListRecursive(struct ListNode* head) { if (head NULL || head-next NULL) { return head; } struct ListNode *newHead reverseListRecursive(head-next); head-next-next head; // 讓下一個(gè)節(jié)點(diǎn)指回當(dāng)前節(jié)點(diǎn) head-next NULL; // 斷開(kāi)原來(lái)的正向鏈接 return newHead; }遞歸思想是假設(shè)后面的部分已經(jīng)反轉(zhuǎn)好了當(dāng)前只需要處理自己這個(gè)節(jié)點(diǎn)和下一個(gè)節(jié)點(diǎn)之間的關(guān)系。空間復(fù)雜度O(n)因?yàn)檫f歸棧要用n層。筆試時(shí)兩種寫(xiě)法都可以但要記得主動(dòng)說(shuō)明時(shí)間復(fù)雜度和空間復(fù)雜度。迭代是O(1)空間遞歸是O(n)空間面試官聽(tīng)了會(huì)認(rèn)為你對(duì)復(fù)雜度有清晰認(rèn)知。變換形式還有一種“反轉(zhuǎn)鏈表前K個(gè)節(jié)點(diǎn)”或者“每K個(gè)一組反轉(zhuǎn)”難度會(huì)上去一檔但核心思想一樣只是多了一層分組和邊界處理。建議備考時(shí)把基礎(chǔ)反轉(zhuǎn)寫(xiě)得滾瓜爛熟再?lài)L試變體會(huì)順手很多。3.2 字符串去重與原地操作字符串相關(guān)的編程大題在B卷里也有露面。我記得有一道題要求把字符串中重復(fù)的字符去掉只保留第一次出現(xiàn)的順序。比如輸入abcaabcd輸出abcd。最直接的想法是開(kāi)一個(gè)新的字符串遍歷原串時(shí)判斷當(dāng)前字符是否已經(jīng)出現(xiàn)過(guò)。這在C/C里可以用一個(gè)長(zhǎng)度為128或256的int數(shù)組當(dāng)哈希表void removeDuplicates(char *str) { if (str NULL) return; int hash[256] {0}; int writeIdx 0; for (int i 0; str[i] ! \0; i) { unsigned char ch (unsigned char)str[i]; if (!hash[ch]) { hash[ch] 1; str[writeIdx] str[i]; } } str[writeIdx] \0; }這里有兩個(gè)細(xì)節(jié)特別值得注意。第一字符強(qiáng)轉(zhuǎn)成unsigned char再作為數(shù)組下標(biāo)是因?yàn)镃語(yǔ)言標(biāo)準(zhǔn)里char不一定是有符號(hào)的直接用str[i]當(dāng)下標(biāo)如果字符是負(fù)數(shù)會(huì)訪(fǎng)問(wèn)到hash[-1]這種越界區(qū)域程序直接崩潰。第二原地操作的意思是直接在原字符串上寫(xiě)入把不重復(fù)的字符依次往前放最后在正確位置補(bǔ)一個(gè)\0。這道題的時(shí)間復(fù)雜度O(n)空間O(1)因?yàn)楣１泶笮」潭ㄊ?56。筆試時(shí)如果要求“不允許用額外存儲(chǔ)空間”那可以用雙重循環(huán)O(n^2)的做法每次比較當(dāng)前字符和前面已經(jīng)保留的字符但代碼會(huì)更繞。我的建議是先把哈希表版本寫(xiě)對(duì)再根據(jù)題目限制作的放矢地調(diào)整。字符串題在微軟筆試題里占有不小的比重建議把常見(jiàn)的子串查找、回文判斷、字符計(jì)數(shù)、原地反轉(zhuǎn)、去重這幾類(lèi)題目都練一遍就能覆蓋大部分場(chǎng)景。3.3 求第K大元素快速選擇算法求無(wú)序數(shù)組中第K大的元素是B卷編程大題里比較有分量的一道。很多人第一反應(yīng)是先排序再索引復(fù)雜度O(n log n)但如果數(shù)組規(guī)模很大這個(gè)解法通常不是出題人想要的。更優(yōu)的方案是基于快速排序的partition思想也叫快速選擇Quick Select平均時(shí)間復(fù)雜度能到O(n)。求第K大可以轉(zhuǎn)換成求“第(n-K1)小”。這部分我當(dāng)時(shí)用了Lomuto分區(qū)方案的寫(xiě)法int partition(int arr[], int low, int high) { int pivot arr[high]; int i low; for (int j low; j high; j) { if (arr[j] pivot) { int temp arr[i]; arr[i] arr[j]; arr[j] temp; i; } } arr[high] arr[i]; arr[i] pivot; return i; } int quickSelect(int arr[], int low, int high, int k) { if (low high) return arr[low]; int pivotIndex partition(arr, low, high); int leftLen pivotIndex - low 1; if (leftLen k) { return arr[pivotIndex]; } else if (k leftLen) { return quickSelect(arr, low, pivotIndex - 1, k); } else { return quickSelect(arr, pivotIndex 1, high, k - leftLen); } }調(diào)用方式求第K大實(shí)際上是求第n - K 1小代入quickSelect(arr, 0, n - 1, n - K 1)?？焖龠x擇的平均時(shí)間復(fù)雜度是O(n)因?yàn)槊看蝡artition之后只需要處理一邊的數(shù)據(jù)規(guī)模是按比例縮小的。但它有一個(gè)軟肋如果pivot每次都選得很差比如在近乎有序的數(shù)組里固定取最后一個(gè)元素作為pivot最壞情況時(shí)間復(fù)雜度會(huì)退化為O(n^2)。筆試時(shí)如果輸入規(guī)模很大建議對(duì)數(shù)組做一次隨機(jī)打亂或者在partition時(shí)隨機(jī)選pivot能有效降低退化概率。這道題還有一種解法是用大小為K的最小堆時(shí)間復(fù)雜度O(n log K)。如果K值很小比如“找第2大的數(shù)”堆方案在某些場(chǎng)景下更穩(wěn)定。我當(dāng)時(shí)在卷子上寫(xiě)的是快速選擇因?yàn)樗臻g復(fù)雜度O(1)不算遞歸棧而且代碼量少適合筆試這種時(shí)間緊張的場(chǎng)合。3.4 附加題全排列的非遞歸生成B卷的附加題里有一道生成全排列的題輸入一個(gè)字符串輸出它的所有排列。最經(jīng)典的解法是遞歸回溯思路是固定第一個(gè)字符然后遞歸排列后面的部分void swap(char *a, char *b) { char temp *a; *a *b; *b temp; } void permute(char *str, int start, int end) { if (start end) { printf(%s\n, str); return; } for (int i start; i end; i) { swap(str[start], str[i]); permute(str, start 1, end); swap(str[start], str[i]); // 恢復(fù)現(xiàn)場(chǎng) } }需要注意“恢復(fù)現(xiàn)場(chǎng)”這一步。如果不把交換過(guò)的字符換回去遞歸返回時(shí)字符串順序已經(jīng)被打亂后面的排列就會(huì)出現(xiàn)嚴(yán)重的重復(fù)或者遺漏。這個(gè)細(xì)節(jié)幾乎是全排列題的高頻bug點(diǎn)。如果題目要求去重比如輸入aab就要在循環(huán)里加一個(gè)條件如果某個(gè)字符在當(dāng)前位置已經(jīng)出現(xiàn)過(guò)就跳過(guò)?？梢杂靡粋€(gè)長(zhǎng)度為256的數(shù)組標(biāo)記當(dāng)前位置是否已經(jīng)使用過(guò)某個(gè)字符void permuteUnique(char *str, int start, int end) { if (start end) { printf(%s\n, str); return; } int used[256] {0}; for (int i start; i end; i) { unsigned char ch (unsigned char)str[i]; if (used[ch]) continue; used[ch] 1; swap(str[start], str[i]); permuteUnique(str, start 1, end); swap(str[start], str[i]); } }非遞歸的做法是基于字典序的next_permutation思路是從右往左找到第一對(duì)相鄰的升序?qū)υ購(gòu)挠彝笳业降谝粋€(gè)大于左側(cè)元素的值交換后反轉(zhuǎn)右側(cè)序列。這個(gè)算法的手寫(xiě)實(shí)現(xiàn)比遞歸版復(fù)雜不少但好在C的STL頭文件里已經(jīng)提供了std::next_permutation。筆試時(shí)如果時(shí)間緊張直接用STL是合理選擇但前提是你得清楚它的底層層邏輯不然面試官追問(wèn)起來(lái)會(huì)比較麻煩。4. 筆試實(shí)操經(jīng)驗(yàn)與環(huán)境避坑4.1 筆試前的開(kāi)發(fā)環(huán)境準(zhǔn)備筆試之前有一個(gè)非常實(shí)際的坑就是開(kāi)發(fā)環(huán)境的準(zhǔn)備。當(dāng)年的問(wèn)卷一般會(huì)給兩個(gè)選擇一是直接在網(wǎng)頁(yè)上寫(xiě)代碼二是本地寫(xiě)完后提交。很多人習(xí)慣用Visual Studio那就要提前確認(rèn)編譯器和運(yùn)行庫(kù)是否齊全。我當(dāng)年第一次模擬練習(xí)時(shí)本地VS報(bào)了一堆鏈接錯(cuò)誤折騰半天才發(fā)現(xiàn)是運(yùn)行庫(kù)版本不匹配白白浪費(fèi)了半小時(shí)心態(tài)都有點(diǎn)崩。后來(lái)我養(yǎng)成了一個(gè)習(xí)慣除了自己常用的IDE還會(huì)用一個(gè)輕量級(jí)的編譯方式兜底。比如裝好MinGW或者GCC之后在命令行里執(zhí)行g(shù)cc -stdc99 -Wall -Wextra -o solution solution.c-Wall和-Wextra會(huì)打開(kāi)大部分警告這對(duì)檢查數(shù)組越界、未初始化變量、類(lèi)型轉(zhuǎn)換等問(wèn)題非常有幫助。筆試現(xiàn)場(chǎng)如果編譯器提示warning很多時(shí)候不是語(yǔ)言本身有問(wèn)題而是代碼里藏著隱患所以開(kāi)著警告編譯是一個(gè)好習(xí)慣。如果你參加的是允許使用本地環(huán)境的筆試建議把所有模板代碼提前準(zhǔn)備好鏈表節(jié)點(diǎn)定義、樹(shù)的節(jié)點(diǎn)定義、快排、歸并、二分查找、堆排序。這些基礎(chǔ)模板塊能夠幫你省下大量現(xiàn)場(chǎng)打字時(shí)間。注意模板不是讓你照抄答案而是減少重復(fù)敲結(jié)構(gòu)體的時(shí)間把精力留給核心算法邏輯。4.2 時(shí)間分配與做題順序做題順序這件事我見(jiàn)過(guò)太多人栽跟頭。有些人拿到卷子就從第一題開(kāi)始做選擇題做得很嗨結(jié)果到了最后一道編程大題只剩15分鐘手忙腳亂代碼都沒(méi)寫(xiě)完。這是最典型的失誤。我的策略是大題優(yōu)先。拿到卷子先花兩分鐘通讀一遍確定編程大題的題號(hào)然后直接從大題開(kāi)始寫(xiě)。原因很簡(jiǎn)單大題分值高、區(qū)分度大而且做完大題之后心態(tài)會(huì)踏實(shí)很多回頭再做選擇題就算有幾道拿不準(zhǔn)也不會(huì)太慌。具體時(shí)間分配可以這樣參考環(huán)節(jié)時(shí)間說(shuō)明通讀全卷2-3分鐘標(biāo)記不確定的題目編程大題120-25分鐘先想清楚再寫(xiě)不急著敲鍵盤(pán)編程大題220-25分鐘注意邊界條件附加題0-15分鐘如果大題順利可以嘗試選擇題填空20-25分鐘逐個(gè)擊破不確定的做個(gè)標(biāo)記檢查5-10分鐘重點(diǎn)檢查數(shù)組越界、空指針、返回值這套流程我后來(lái)推薦給好幾個(gè)學(xué)弟學(xué)妹反映都還不錯(cuò)。核心邏輯就一條用你的最佳狀態(tài)去打最能拉開(kāi)分差的仗而不是把黃金時(shí)間浪費(fèi)在低價(jià)值的題目上。4.3 面試官眼里的“好答案”長(zhǎng)什么樣筆試雖然只看最終提交但微軟的筆試結(jié)果會(huì)和后續(xù)面試聯(lián)動(dòng)。你在筆試編程題里暴露出的編碼習(xí)慣、邊界處理意識(shí)和解題思路往往會(huì)成為面試官提問(wèn)的素材。所以從筆試開(kāi)始就要有意識(shí)地培養(yǎng)“面試官友好型”的答題習(xí)慣。第一先寫(xiě)思路再寫(xiě)代碼。這不需要提交給閱卷系統(tǒng)但如果你在草稿紙上先畫(huà)一畫(huà)思路、列出時(shí)間復(fù)雜度和空間復(fù)雜度你的代碼質(zhì)量會(huì)明顯更高。我在做鏈表反轉(zhuǎn)時(shí)會(huì)先在草稿紙上畫(huà)三個(gè)節(jié)點(diǎn)模擬一下指針的移動(dòng)過(guò)程這能避免“自以為寫(xiě)對(duì)了但實(shí)際邏輯混亂”的情況。第二主動(dòng)處理邊界條件?？罩羔?、空數(shù)組、只有一個(gè)元素、全是相同元素這些情況每一道題都要問(wèn)自己一遍。很多人提交的代碼在正常用例下AC一旦輸入為空或者長(zhǎng)度為1就直接崩潰這在閱卷時(shí)是致命的。多寫(xiě)幾行防御性代碼比如if (head NULL || head-next NULL) { return head; }不僅能防止崩潰還能讓閱卷人一眼看出你對(duì)邊界條件的敏感度。第三代碼風(fēng)格要干凈。不要追求一行代碼寫(xiě)三件事不要用a、b、c這種毫無(wú)意義的變量名。微軟的工程師文化比較看重可讀性和可維護(hù)性變量命名、縮進(jìn)、注釋習(xí)慣都會(huì)被潛移默化地評(píng)估。筆試不是競(jìng)賽不是寫(xiě)越短的代碼越好而是寫(xiě)的越清楚越好。5. 常見(jiàn)問(wèn)題與高效備考路線(xiàn)5.1 我踩過(guò)的一些坑備考過(guò)程中我踩過(guò)的坑不算少挑幾個(gè)典型的講給后來(lái)的朋友聽(tīng)希望你們少走彎路。第一個(gè)坑是只刷題不總結(jié)。我一開(kāi)始用在線(xiàn)題庫(kù)刷題一晚上刷十幾道當(dāng)時(shí)感覺(jué)效率極高。但隔一周再做同樣的題居然又要重頭開(kāi)始推思路。后來(lái)我改了一種方式每道題做完之后在筆記本上寫(xiě)三句話(huà)——這道題考察什么知識(shí)點(diǎn)、我的第一反應(yīng)是什么、最優(yōu)解是什么。這樣刷題的數(shù)量降下來(lái)但鞏固率大幅提升。第二個(gè)坑是忽視手寫(xiě)代碼。筆試雖然不一定要求手寫(xiě)但面試經(jīng)常要白板編程。我最初習(xí)慣在IDE里寫(xiě)代碼因?yàn)檎Z(yǔ)法高亮、自動(dòng)補(bǔ)全、即時(shí)編譯都幫我掩蓋了很多問(wèn)題。等到白板上寫(xiě)代碼時(shí)才發(fā)現(xiàn)連for循環(huán)的括號(hào)都不容易寫(xiě)對(duì)更別提處理那些需要臨時(shí)變量交換的邏輯了。建議備考后期每天至少手寫(xiě)兩三道題的完整代碼不要借助任何IDE輔助。第三個(gè)坑是忽略了編譯環(huán)境的細(xì)節(jié)。有一次我提交的代碼在本地跑得好好的結(jié)果到在線(xiàn)評(píng)測(cè)系統(tǒng)上直接編譯失敗原因是用了非C標(biāo)準(zhǔn)庫(kù)函數(shù)而評(píng)測(cè)環(huán)境的編譯參數(shù)比本地嚴(yán)格很多。從那以后我每次寫(xiě)完代碼都會(huì)在命令行用嚴(yán)格的編譯參數(shù)跑一遍比如加-Wall -Werror。-Werror會(huì)把警告當(dāng)成錯(cuò)誤強(qiáng)迫我消除所有隱患。5.2 從一個(gè)月倒計(jì)時(shí)開(kāi)始的刷題計(jì)劃如果你還有一個(gè)月就要參加類(lèi)似性質(zhì)的筆試我建議把備考規(guī)劃成四個(gè)階段每周一個(gè)主題節(jié)奏相對(duì)舒服第一周語(yǔ)言基礎(chǔ)補(bǔ)漏。重點(diǎn)復(fù)習(xí)指針、數(shù)組、內(nèi)存布局、C的類(lèi)/析構(gòu)/虛函數(shù)。每天找?guī)椎勒Z(yǔ)言細(xì)節(jié)選擇題練手不急著刷算法題先把地基打穩(wěn)。第二周數(shù)據(jù)結(jié)構(gòu)專(zhuān)項(xiàng)。鏈表、字符串、棧、隊(duì)列、二叉樹(shù)、哈希表每種結(jié)構(gòu)至少刷10道題。務(wù)必把反轉(zhuǎn)鏈表、判斷回文、二叉樹(shù)遍歷這幾類(lèi)基礎(chǔ)題練到閉眼能寫(xiě)。第三周算法專(zhuān)項(xiàng)。排序、二分、雙指針、遞歸回溯、動(dòng)態(tài)規(guī)劃。重點(diǎn)放在高頻題型上比如快速排序、歸并排序、第K大元素、最長(zhǎng)公共子串等。第四周模擬考試。找一套往年的筆試題或在線(xiàn)題庫(kù)的模擬卷設(shè)定120分鐘鬧鐘在完全模擬筆試的環(huán)境下做完整套題。做完之后認(rèn)真復(fù)盤(pán)每一道題尤其是錯(cuò)題多問(wèn)自己“為什么是這個(gè)答案”。輔助資料方面我強(qiáng)烈推薦《編程之美》這本書(shū)本身就是微軟研究院出的面試題集各種題目的思路非常貼近微軟的考察風(fēng)格。另外《C和指針》是補(bǔ)C語(yǔ)言短板的利器雖然覆蓋面廣但隨便挑幾章看就能受益匪淺。如果算法底子比較薄可以配合《算法圖解》入門(mén)再逐步過(guò)渡到《算法導(dǎo)論》的相關(guān)章節(jié)。我個(gè)人在實(shí)際操作中的一個(gè)體會(huì)是刷題不要貪多貪多嚼不爛。同一個(gè)知識(shí)點(diǎn)比如鏈表反轉(zhuǎn)把這一個(gè)點(diǎn)吃透比草草刷十道不同類(lèi)型的題更有價(jià)值。筆試考的不是你知道多少種算法而是在有限時(shí)間里把最經(jīng)典的解法寫(xiě)得又快又準(zhǔn)。最后再分享一個(gè)小技巧筆試前一周每天早起花10分鐘默寫(xiě)一份“必備代碼清單”。我當(dāng)時(shí)的清單是鏈表反轉(zhuǎn)、快速排序、歸并排序、二分查找、二叉樹(shù)前中后序遍歷、層序遍歷、快速選擇、全排列遞歸版。每天寫(xiě)一遍堅(jiān)持一周等到真正上考場(chǎng)手里有糧心里不慌。這套2014年的筆試卷B雖然年代有點(diǎn)久遠(yuǎn)但它的考點(diǎn)和經(jīng)典題目對(duì)今天的大廠校招依然很有參考價(jià)值希望這篇復(fù)盤(pán)能幫到你。