2013年能從Google筆試?yán)锘钕聛?lái)的人現(xiàn)在基本都在各大廠帶團(tuán)隊(duì)了。我當(dāng)年沒(méi)趕上那趟車(chē)但事后把能找到的2013年Google筆試題翻來(lái)覆去做了好幾遍工作這些年回頭再看才發(fā)現(xiàn)那些題目才是真正的“內(nèi)功修煉手冊(cè)”。最近整理舊硬盤(pán)又翻出當(dāng)年的刷題筆記干脆把這份筆試卷掰開(kāi)揉碎講一遍給準(zhǔn)備外企面試或想夯實(shí)算法基礎(chǔ)的朋友做個(gè)參考。這套試卷對(duì)現(xiàn)在的意義不在于題目本身而在于它的考察邏輯——Google是出了名的不愛(ài)考“八股文”更看重候選人拆解問(wèn)題、設(shè)計(jì)算法、權(quán)衡取舍的能力。2013年的題目雖然距今有些年頭但其中涉及的數(shù)組處理、動(dòng)態(tài)規(guī)劃、圖論思想到今天依然是各大廠算法面試的核心。我建議你抱著“做練習(xí)題”的心態(tài)來(lái)讀而不是“背答案”這樣才能榨干這套題的價(jià)值。1. 內(nèi)容整體設(shè)計(jì)與思路拆解1.1 2013年Google筆試到底考什么聊這套題之前先說(shuō)個(gè)背景。Google的工程師招聘流程向來(lái)以“算法為王”著稱筆試環(huán)節(jié)主要篩掉兩類(lèi)人一類(lèi)是基本功不扎實(shí)的另一類(lèi)是思維僵化只懂套模板的。2013年的筆試卷整體延續(xù)了這個(gè)風(fēng)格題型集中在算法設(shè)計(jì)與代碼實(shí)現(xiàn)上偶有涉及系統(tǒng)設(shè)計(jì)的基礎(chǔ)題但核心永遠(yuǎn)圍繞著“給定約束下如何高效解決問(wèn)題”。我把當(dāng)年流傳出來(lái)的題目做了歸類(lèi)出現(xiàn)頻率最高的幾個(gè)方向是數(shù)組與字符串處理這類(lèi)題考察你對(duì)基礎(chǔ)數(shù)據(jù)結(jié)構(gòu)的敏感度常見(jiàn)的有查找、排序、去重、區(qū)間合并等變形。動(dòng)態(tài)規(guī)劃這是Google筆試的重頭戲幾乎每套卷必考。2013年的題目里DP類(lèi)問(wèn)題占比很高而且經(jīng)常不是裸的DP題而是包裝在“看似可以用貪心/遞歸硬解”的場(chǎng)景里。圖論與搜索BFS/DFS是基礎(chǔ)更進(jìn)階的會(huì)考察最短路、拓?fù)渑判?、連通分量等。概率與數(shù)學(xué)思維Google對(duì)數(shù)學(xué)底子很看重有些題目表面是coding實(shí)際上是在考你對(duì)概率模型或數(shù)學(xué)公式的理解。需要說(shuō)明的是2013年的筆試題沒(méi)有統(tǒng)一的官方版網(wǎng)上流傳的版本基本都是考生回憶的復(fù)現(xiàn)題細(xì)節(jié)上可能和原卷有出入但考察的知識(shí)點(diǎn)和風(fēng)格是可信的。我下面的解析也基于這些流傳版本并結(jié)合我自己刷題時(shí)的驗(yàn)證。1.2 為什么這套題到現(xiàn)在還值得刷有人可能會(huì)問(wèn)2013年的題都過(guò)了這么多年了刷它還有什么意義我自己的體會(huì)是Google的算法題風(fēng)格有一個(gè)特點(diǎn)——穩(wěn)定。哪怕過(guò)十年它考察的核心能力維度幾乎沒(méi)變你在有限時(shí)間內(nèi)能否快速定位問(wèn)題的本質(zhì)、能否設(shè)計(jì)出有明確復(fù)雜度的算法、能否寫(xiě)出健壯的代碼、能否清晰地和面試官交流思路。2013年的題和現(xiàn)在的題差別主要在題目包裝的新穎度上內(nèi)核換湯不換藥。舉個(gè)例子2013年有一道“找數(shù)組中第K大的數(shù)”的變種題放到現(xiàn)在依然是熱門(mén)考題。你背過(guò)模板沒(méi)用它會(huì)在條件上加限制比如“數(shù)據(jù)量極大無(wú)法一次性載入內(nèi)存”這時(shí)候就得改用堆或分治的思路。這種在約束條件上做文章的做法正是Google筆試最喜歡干的事。所以我的建議是別把這份卷子當(dāng)歷史文物把它當(dāng)成一套“高仿真模擬題”來(lái)刷。它比市面上很多培訓(xùn)機(jī)構(gòu)出的模擬題更貼近真實(shí)面試的節(jié)奏和深度。1.3 整體難度評(píng)估與應(yīng)對(duì)策略從難度梯度上看2013年Google筆試卷大致可以分成三檔難度檔位考察重點(diǎn)典型題型建議用時(shí)基礎(chǔ)檔編碼基本功、邊界條件處理數(shù)組操作、字符串處理、基礎(chǔ)排序每題10-15分鐘中等檔算法設(shè)計(jì)能力、經(jīng)典模型識(shí)別動(dòng)態(tài)規(guī)劃、DFS/BFS、雙指針每題20-30分鐘進(jìn)階檔數(shù)學(xué)建模、復(fù)雜優(yōu)化、系統(tǒng)思維概率題、大數(shù)據(jù)處理、狀態(tài)壓縮DP每題30分鐘以上當(dāng)時(shí)Google的筆試時(shí)長(zhǎng)大概在兩到三個(gè)小時(shí)題目數(shù)量在四到六道之間這意味著每道題留給你的時(shí)間非常緊張。如果你在前面的基礎(chǔ)題上卡住后面的大題基本就沒(méi)時(shí)間做了。所以備考策略上我強(qiáng)烈建議你先快速掃一遍所有題目?jī)?yōu)先做自己最有把握的把基礎(chǔ)分拿穩(wěn)再去啃硬骨頭。2. 核心細(xì)節(jié)解析與實(shí)操要點(diǎn)2.1 數(shù)組處理題從暴力到雙指針的進(jìn)階路線先拿一道2013年比較有代表性的數(shù)組題開(kāi)刀。題目大意是給定一個(gè)未排序的整數(shù)數(shù)組找出其中沒(méi)有出現(xiàn)的最小的正整數(shù)。這個(gè)題現(xiàn)在看起來(lái)不算太難但放在當(dāng)年對(duì)很多習(xí)慣暴力解的候選人來(lái)說(shuō)還是有一定殺傷力的。它能很好地反映出一個(gè)人的算法素養(yǎng)因?yàn)樗淖顑?yōu)解空間復(fù)雜度要求是O(1)這就排除了用哈希表“作弊”的可能。最自然的思路是排序后掃描時(shí)間復(fù)雜度O(n log n)空間O(1)。這個(gè)解法能拿一部分分但Google要的顯然不是這個(gè)。正確的最優(yōu)解是原地哈希遍歷數(shù)組把每個(gè)值放到它應(yīng)該在的位置上即把數(shù)字i放到下標(biāo)i-1處然后再掃一遍找出第一個(gè)缺失的正整數(shù)。這里面有幾個(gè)關(guān)鍵的邊界坑我當(dāng)年第一次寫(xiě)就踩了注意交換的時(shí)候如果兩個(gè)位置的值相等會(huì)陷入死循環(huán)。另外如果當(dāng)前值不在[1, n]范圍內(nèi)直接跳過(guò)不需要處理。我把它寫(xiě)成代碼大家可以直接看def first_missing_positive(nums): n len(nums) for i in range(n): while 1 nums[i] n and nums[nums[i] - 1] ! nums[i]: target_idx nums[i] - 1 nums[target_idx], nums[i] nums[i], nums[target_idx] for i in range(n): if nums[i] ! i 1: return i 1 return n 1這段代碼看起來(lái)簡(jiǎn)單但值得細(xì)品的地方很多。為什么用while而不是if因?yàn)榻粨Q過(guò)來(lái)的新值可能依然不在正確位置需要繼續(xù)處理。為什么判斷條件里要加nums[nums[i] - 1] ! nums[i]這是為了防止兩個(gè)相等的數(shù)互相交換導(dǎo)致死循環(huán)。這些細(xì)節(jié)恰恰是面試官重點(diǎn)觀察的點(diǎn)。2.2 動(dòng)態(tài)規(guī)劃題從記憶化搜索到狀態(tài)定義2013年Google筆試有一道讓我印象很深的DP題它的場(chǎng)景大概是一個(gè)“機(jī)器人走格子”的變體。原題說(shuō)的是機(jī)器人從網(wǎng)格左上角走到右下角每次只能向下或向右走但網(wǎng)格中有一些格子有障礙物問(wèn)有多少條不同的路徑。這道題的裸版是LeetCode 62/63但Google的版本在約束上做了手腳——網(wǎng)格的規(guī)模很大但障礙物的數(shù)量很少。如果你按照常規(guī)的二維DP去開(kāi)一個(gè)m×n的數(shù)組內(nèi)存可能會(huì)爆。這時(shí)候需要換個(gè)思路因?yàn)檎系K物少所以可行的路徑會(huì)被障礙物切分成若干個(gè)區(qū)間我們可以只對(duì)障礙物之間的可達(dá)關(guān)系做DP。這種“大網(wǎng)格小障礙”的約束條件在真實(shí)面試中非常常見(jiàn)。它考察的是你能不能根據(jù)數(shù)據(jù)規(guī)模調(diào)整算法設(shè)計(jì)。我當(dāng)時(shí)的解決方案是把所有障礙物按坐標(biāo)排序然后對(duì)障礙物序列做DP狀態(tài)是“到達(dá)某個(gè)障礙物位置作為路徑上的某個(gè)點(diǎn)的方案數(shù)”轉(zhuǎn)移時(shí)計(jì)算兩個(gè)障礙物之間的組合數(shù)用排列組合公式C(mn, m)。這個(gè)思路的代碼篇幅比較長(zhǎng)這里只貼出核心的狀態(tài)轉(zhuǎn)移邏輯def unique_paths_with_obstacles(m, n, obstacles): # obstacles是[(r, c), ...]格式的障礙物坐標(biāo)列表 if not obstacles: return comb(m n - 2, m - 1) points sorted(obstacles [(0, 0), (m - 1, n - 1)]) dp [0] * len(points) dp[0] 1 for i in range(1, len(points)): r_i, c_i points[i] for j in range(i): r_j, c_j points[j] if r_j r_i and c_j c_i: ways comb((r_i - r_j) (c_i - c_j), r_i - r_j) dp[i] dp[j] * ways return dp[-1]這個(gè)解法的核心洞察是從點(diǎn)A到點(diǎn)B的路徑數(shù)只取決于兩者之間的相對(duì)坐標(biāo)差是一個(gè)排列組合問(wèn)題。既然障礙物很少那我們直接在這些“關(guān)鍵點(diǎn)”之間轉(zhuǎn)移而不用窮舉整個(gè)網(wǎng)格。這里面用到了組合數(shù)計(jì)算函數(shù)comb在Python 3.8中可以直接從math庫(kù)導(dǎo)入。2.3 圖論搜索題BFS的狀態(tài)壓縮技巧再講一道圖論相關(guān)的題。2013年有一道題描述了一個(gè)迷宮問(wèn)題大概意思是一個(gè)由0和1組成的矩陣0表示可以走1表示是墻你可以從任意一個(gè)0出發(fā)目標(biāo)是找到一條路徑使得路徑上經(jīng)過(guò)的“墻”的數(shù)量不超過(guò)K次可以通過(guò)墻但要計(jì)數(shù)問(wèn)能否從起點(diǎn)到達(dá)終點(diǎn)。這種題看起來(lái)是BFS的變形難點(diǎn)在于狀態(tài)設(shè)計(jì)。如果你只記錄坐標(biāo)(x, y)那同一個(gè)坐標(biāo)可能會(huì)被多條不同“破墻次數(shù)”的路徑訪問(wèn)直接BFS會(huì)丟失狀態(tài)。正確的做法是記錄一個(gè)三元組(x, y, k)表示到達(dá)(x, y)時(shí)已經(jīng)穿墻k次。但如果你直接開(kāi)三維數(shù)組空間可能會(huì)比較大。更優(yōu)雅的做法是用“優(yōu)先隊(duì)列BFS”或者“雙端隊(duì)列BFS”0-1 BFS的變體每次走普通格子花費(fèi)0走墻花費(fèi)1目標(biāo)是找一條從起點(diǎn)到終點(diǎn)的最小“穿墻次數(shù)”路徑。這樣狀態(tài)就壓縮成了二維因?yàn)槊總€(gè)格子只需要記錄到達(dá)它所需的最小穿墻次數(shù)即可。我當(dāng)時(shí)刷這道題的時(shí)候發(fā)現(xiàn)這個(gè)“0-1 BFS”的技巧非常實(shí)用代碼也不復(fù)雜from collections import deque def can_break_walls(grid, K): m, n len(grid), len(grid[0]) INF float(inf) dist [[INF] * n for _ in range(m)] dq deque() # 從所有為0的起點(diǎn)開(kāi)始也可以指定單一入口 for i in range(m): for j in range(n): if grid[i][j] 0: dist[i][j] 0 dq.append((i, j)) break else: continue break dirs [(1,0), (-1,0), (0,1), (0,-1)] while dq: x, y dq.popleft() for dx, dy in dirs: nx, ny x dx, y dy if 0 nx m and 0 ny n: w 1 if grid[nx][ny] 1 else 0 if dist[x][y] w dist[nx][ny]: dist[nx][ny] dist[x][y] w if w 0: dq.appendleft((nx, ny)) else: dq.append((nx, ny)) # 檢查終點(diǎn)是否可達(dá)且穿墻次數(shù)不超過(guò)K return min(dist[i][j] for i in range(m) for j in range(n) if grid[i][j] 0) K這里用雙端隊(duì)列實(shí)現(xiàn)0-1 BFS的原理是走0權(quán)值的邊時(shí)把新節(jié)點(diǎn)插入隊(duì)首這樣能保持隊(duì)列中距離的單調(diào)性走1權(quán)值的邊時(shí)插隊(duì)尾。這樣每個(gè)節(jié)點(diǎn)最多入隊(duì)出隊(duì)常數(shù)次整體復(fù)雜度是O(m×n)。這個(gè)技巧在面對(duì)“代價(jià)只有0和1兩種”的最短路問(wèn)題中非常好用。2.4 概率題用數(shù)學(xué)思維解期望Google的筆試卷中概率題的出鏡率也不低。2013年有一道題我印象特別深刻大意是給定一個(gè)隨機(jī)數(shù)生成器每次等概率生成0或1如何用它構(gòu)造一個(gè)生成0到N-1之間均勻分布的隨機(jī)數(shù)這是個(gè)經(jīng)典的“拒絕采樣”問(wèn)題。最簡(jiǎn)單的做法是用log2(N)個(gè)隨機(jī)比特拼出一個(gè)二進(jìn)制數(shù)如果這個(gè)數(shù)落在[0, N)范圍內(nèi)就輸出否則重新生成。但這個(gè)做法有一個(gè)效率問(wèn)題當(dāng)N不是2的冪次時(shí)拒絕的概率比較高。更優(yōu)的策略是“緩存式拒絕采樣”。我發(fā)現(xiàn)網(wǎng)上很多資料都沒(méi)講這里詳細(xì)說(shuō)說(shuō)思路你每次生成k個(gè)比特得到一個(gè)值v。如果v N直接返回否則不要丟掉v而是把v - N記錄下來(lái)下次生成隨機(jī)數(shù)時(shí)用(v - N)的值再拼上一些新的比特位繼續(xù)判定。這樣可以顯著減少隨機(jī)比特的浪費(fèi)把期望消耗的比特?cái)?shù)壓到理論最優(yōu)附近。這個(gè)思路背后的數(shù)學(xué)原理是拒絕采樣產(chǎn)生的“多余隨機(jī)數(shù)”其實(shí)也服從均勻分布可以通過(guò)移位和拼接重新利用。我當(dāng)時(shí)花了很長(zhǎng)時(shí)間才把這塊想明白后來(lái)發(fā)現(xiàn)它和算術(shù)編碼的思想有些相通之處。這種題在筆試中出現(xiàn)的意義不在于你真的要寫(xiě)一個(gè)多么高效的隨機(jī)數(shù)生成器而在于考察你的數(shù)學(xué)建模能力以及能否用程序把數(shù)學(xué)模型轉(zhuǎn)化為可運(yùn)行的代碼。我見(jiàn)過(guò)不少候選人卡在這種題上其實(shí)不是不會(huì)寫(xiě)代碼而是腦子里沒(méi)有建立起“概率模型→算法設(shè)計(jì)”的橋梁。3. 實(shí)操過(guò)程與核心環(huán)節(jié)實(shí)現(xiàn)3.1 從拿到題目到提交代碼的完整流程筆試實(shí)戰(zhàn)和平時(shí)刷題完全是兩碼事。平時(shí)刷題你可以慢慢想筆試不行時(shí)間一到就要交卷。我在模擬2013年這套題時(shí)給自己定了一套標(biāo)準(zhǔn)流程分享出來(lái)供你參考第1步2分鐘內(nèi)快速通讀所有題標(biāo)記每道題的難度和預(yù)計(jì)耗時(shí)。先做簡(jiǎn)單的題把確定性拿分再做難題。第2步每題最開(kāi)始的5分鐘不要急著寫(xiě)代碼。先在紙上畫(huà)樣例、推邊界想清楚算法框架確認(rèn)復(fù)雜度和預(yù)期。第3步每題中間20分鐘專注寫(xiě)代碼。用注釋標(biāo)注關(guān)鍵邏輯變量命名盡量清晰。Google對(duì)代碼風(fēng)格是有一定偏好的清晰度甚至比執(zhí)行效率更重要。第4步最后5分鐘留出時(shí)間檢查邊界條件和潛在的死循環(huán)。很多bug都是在最后一分鐘抓出來(lái)的。這個(gè)流程看起來(lái)很基礎(chǔ)但執(zhí)行到位的人真不多。多數(shù)人的通病是拿到題就開(kāi)始寫(xiě)代碼寫(xiě)著寫(xiě)著發(fā)現(xiàn)思路不對(duì)推倒重來(lái)白白浪費(fèi)大量時(shí)間。我一開(kāi)始也犯過(guò)這個(gè)毛病后來(lái)逼著自己每次都先畫(huà)圖再動(dòng)手正確率明顯上去了。3.2 一道完整題目的實(shí)戰(zhàn)推演找最長(zhǎng)回文子串為了讓你更直觀地感受整個(gè)思考過(guò)程我用2013年Google筆試中出現(xiàn)過(guò)的另一道經(jīng)典題——“最長(zhǎng)回文子串”來(lái)做一次完整的推演。先看題目給定一個(gè)字符串s找到s中最長(zhǎng)的回文子串。你可以假設(shè)s的最大長(zhǎng)度為1000。拿到題先別急著寫(xiě)代碼在腦子里過(guò)一遍候選方案暴力法枚舉所有子串檢查是否為回文時(shí)間O(n^3)太慢直接淘汰。動(dòng)態(tài)規(guī)劃法用dp[i][j]表示s[i:j1]是否是回文狀態(tài)轉(zhuǎn)移是dp[i][j] (s[i]s[j]) and (j-i3 or dp[i1][j-1])。時(shí)間O(n^2)空間O(n^2)。這個(gè)能過(guò)但空間可以優(yōu)化。中心擴(kuò)展法每個(gè)中心向外擴(kuò)展記錄最長(zhǎng)回文的起點(diǎn)和終點(diǎn)。時(shí)間O(n^2)空間O(1)。這是面試中最推薦的方案。Manacher算法時(shí)間O(n)空間O(n)。如果你能流暢地寫(xiě)出來(lái)面試官會(huì)眼前一亮但前提是你要真懂不然面試官深挖幾句就露餡了。我在模擬筆試時(shí)選擇了中心擴(kuò)展法因?yàn)樗鼘?shí)現(xiàn)相對(duì)簡(jiǎn)單且不容易出錯(cuò)。核心代碼大概是這樣的def longest_palindrome(s): if not s: return start, end 0, 0 for i in range(len(s)): len1 expand_around_center(s, i, i) # 奇數(shù)長(zhǎng)度回文 len2 expand_around_center(s, i, i 1) # 偶數(shù)長(zhǎng)度回文 max_len max(len1, len2) if max_len end - start: start i - (max_len - 1) // 2 end i max_len // 2 return s[start:end 1] def expand_around_center(s, left, right): while left 0 and right len(s) and s[left] s[right]: left - 1 right 1 return right - left - 1這段代碼有幾個(gè)細(xì)節(jié)值得注意中心擴(kuò)展法要同時(shí)處理奇數(shù)和偶數(shù)長(zhǎng)度回文所以循環(huán)里調(diào)用了兩次擴(kuò)展函數(shù)分別以i為中心和以(i, i1)為中心。計(jì)算start和end時(shí)用(max_len - 1) // 2和max_len // 2的整除運(yùn)算可以同時(shí)兼容奇偶兩種情況。這道題的拿分點(diǎn)在于邊界條件的處理。我見(jiàn)過(guò)不少人在空字符串、單字符串、全相同字符的case上翻車(chē)。每次筆試前把這類(lèi)極端case在腦子里過(guò)一遍能避免很多無(wú)謂的失分。3.3 大數(shù)據(jù)場(chǎng)景下的方案設(shè)計(jì)除了純算法題2013年Google筆試有時(shí)也會(huì)出現(xiàn)一道“大數(shù)據(jù)”風(fēng)格的設(shè)計(jì)題。比如給定一個(gè)非常大的日志文件光靠?jī)?nèi)存裝不下如何統(tǒng)計(jì)其中出現(xiàn)頻率最高的前100個(gè)IP地址這種題在筆試中不會(huì)要求你寫(xiě)完整代碼但需要你給出方案并分析時(shí)間空間復(fù)雜度。標(biāo)準(zhǔn)的做法是用“分治 哈希 堆”三件套第一步把大文件切分成若干個(gè)小塊每塊可以完整加載進(jìn)內(nèi)存。第二步對(duì)每個(gè)小塊用哈希表統(tǒng)計(jì)每個(gè)IP的出現(xiàn)次數(shù)。第三步對(duì)每個(gè)小塊用大小為100的最小堆或最大堆提取該塊的前100高頻IP。第四步歸并所有塊的結(jié)果再全局排序取前100。這個(gè)方案的思路并不復(fù)雜但面試官想聽(tīng)的不只是方案本身還包括你在細(xì)節(jié)上的思考。比如怎么切分文件才能保證同一個(gè)IP不會(huì)散落在多個(gè)塊中切分的依據(jù)應(yīng)該是IP的哈希值而不是簡(jiǎn)單地按文件大小切否則同一個(gè)IP的統(tǒng)計(jì)會(huì)被拆分。再比如如果哈希值分布不均導(dǎo)致某個(gè)塊特別大怎么辦可以引入多級(jí)哈希切分或者在切分后對(duì)超大塊再遞歸處理。這種題在考場(chǎng)上的分值占比不一定高但它考察的是“系統(tǒng)思維”和“工程落地能力”恰恰是Google這種公司很看重的。如果你平時(shí)只刷LeetCode不關(guān)注數(shù)據(jù)規(guī)模對(duì)方案的影響很容易在這種題上露怯。4. 常見(jiàn)問(wèn)題與排查技巧實(shí)錄4.1 考場(chǎng)上的典型翻車(chē)現(xiàn)場(chǎng)我在模擬2013年這套題的過(guò)程中踩過(guò)不少坑整理了一些典型的翻車(chē)現(xiàn)場(chǎng)大家看看自己有沒(méi)有中招只想到一種解法就開(kāi)寫(xiě)結(jié)果寫(xiě)著寫(xiě)著發(fā)現(xiàn)復(fù)雜度不達(dá)標(biāo)只好推翻重寫(xiě)。這浪費(fèi)掉的20分鐘可能直接決定你后面大題的生死。忽略了題目中的隱含條件。比如“數(shù)組未排序”“數(shù)字可能為負(fù)”“字符串可能包含空格”這些關(guān)鍵信息都會(huì)影響算法設(shè)計(jì)漏掉一個(gè)就是災(zāi)難。遞歸寫(xiě)法沒(méi)有想清楚終止條件和返回值語(yǔ)義寫(xiě)出來(lái)的代碼在邊界case上各種報(bào)錯(cuò)白白丟分。只測(cè)了題目給的示例沒(méi)有自己構(gòu)造邊界case。比如數(shù)組長(zhǎng)度為1、字符串為空、整數(shù)溢出等。這些坑單拎出來(lái)都不算大問(wèn)題但組合在一起足以讓你的筆試成績(jī)從“通過(guò)”滑到“不通過(guò)”。4.2 筆試中的邊界條件速查表根據(jù)刷題經(jīng)驗(yàn)我列了一個(gè)筆試前必看的邊界條件速查表每次模擬考之前都過(guò)一遍場(chǎng)景需要檢查的邊界條件數(shù)組類(lèi)空數(shù)組、長(zhǎng)度為1、全相同元素、最大值/最小值、有重復(fù)元素字符串類(lèi)空串、單字符、全空格、大小寫(xiě)混合、Unicode字符數(shù)值類(lèi)0、負(fù)數(shù)、整數(shù)溢出、浮點(diǎn)數(shù)精度如有遞歸類(lèi)深度過(guò)大導(dǎo)致棧溢出、終止條件是否覆蓋所有輸入圖論類(lèi)只有一個(gè)節(jié)點(diǎn)、沒(méi)有邊、存在環(huán)有向/無(wú)向、極大的稀疏圖這個(gè)表格看著簡(jiǎn)單但每次做題前掃一眼能幫你建立“條件反射”。我在刷題時(shí)反復(fù)強(qiáng)調(diào)寫(xiě)代碼前先花30秒想邊界條件寫(xiě)完后用幾個(gè)極端case手動(dòng)跑一遍能抓出大部分bug。4.3 時(shí)間不夠用怎么辦取舍策略實(shí)踐筆試中時(shí)間管理是門(mén)硬功夫。有時(shí)候題目數(shù)量多難度大并不是所有題都能做完。我的經(jīng)驗(yàn)是每題先拿部分分再想著拿全分。舉個(gè)例子如果一道題最優(yōu)解是O(n)且空間O(1)但你一時(shí)想不出來(lái)可以先寫(xiě)一個(gè)暴力解比如用哈希表的O(n)空間解法把基礎(chǔ)分拿到然后在注釋里說(shuō)明你計(jì)劃的優(yōu)化方向。這樣至少證明你具備基本的編程能力不是毫無(wú)頭緒。我做過(guò)幾次標(biāo)記發(fā)現(xiàn)多數(shù)情況下提供一個(gè)正確但非最優(yōu)的解法遠(yuǎn)比提供一個(gè)半吊子且bug百出的“最優(yōu)解”得分更高。當(dāng)然這不是鼓勵(lì)你永遠(yuǎn)滿足于次優(yōu)解。而是說(shuō)在筆試的限時(shí)壓力下要懂得“先完成再完美”。先把能跑通的代碼寫(xiě)出來(lái)保底如果剩余時(shí)間充足再回來(lái)優(yōu)化復(fù)雜度和空間占用。4.4 復(fù)盤(pán)方法從一套題中榨出最大價(jià)值刷完一套題復(fù)盤(pán)比做題本身更重要。我自己常用的復(fù)盤(pán)方法是“三輪復(fù)習(xí)法”第一輪考后當(dāng)天對(duì)照參考答案找出自己思路偏差的地方把正確解法完整地寫(xiě)一遍。第二輪三天后不看答案獨(dú)立重寫(xiě)一遍。如果能順利寫(xiě)出說(shuō)明真的掌握了如果卡殼說(shuō)明只是記住了答案沒(méi)有理解思路。第三輪一周后把題目條件做變換比如“數(shù)組改成鏈表”“數(shù)值范圍加大”看自己能否舉一反三寫(xiě)出變種題的解法。這一步最能檢驗(yàn)是否真正吃透了知識(shí)點(diǎn)。這個(gè)方法比較笨但效果扎實(shí)。Google的題往往不是孤立的一道題而是一類(lèi)思想的載體。能從一個(gè)題目中抽提出通用的解題模型你就可以應(yīng)對(duì)一類(lèi)題目而不是僅僅會(huì)一道題。5. 從筆試卷走向系統(tǒng)設(shè)計(jì)工程視角的延伸5.1 為什么筆試中會(huì)出現(xiàn)“設(shè)計(jì)感”很強(qiáng)的題很多刷題博主會(huì)把算法題和系統(tǒng)設(shè)計(jì)題分開(kāi)講但2013年Google筆試中我注意到一個(gè)有趣的趨勢(shì)有些算法題本身帶有一定的“設(shè)計(jì)感”。它們不是純粹問(wèn)“怎么實(shí)現(xiàn)某個(gè)功能”而是問(wèn)“在某個(gè)約束條件下怎么實(shí)現(xiàn)”。比如前面提到的“大數(shù)據(jù)日志統(tǒng)計(jì)Top100 IP”的題它在實(shí)際工程中就是一項(xiàng)常見(jiàn)需求。做廣告點(diǎn)擊日志分析、用戶行為追蹤的團(tuán)隊(duì)幾乎每天都要處理類(lèi)似的分布式統(tǒng)計(jì)任務(wù)。Google考這類(lèi)題本質(zhì)上是在考察你是否具備“把算法落地到工程場(chǎng)景”的直覺(jué)。我當(dāng)時(shí)在筆記里寫(xiě)過(guò)一句話算法題是在一個(gè)受控環(huán)境里考驗(yàn)?zāi)愕南孪尴到y(tǒng)設(shè)計(jì)題是在一個(gè)貼近現(xiàn)實(shí)的環(huán)境里考驗(yàn)?zāi)愕纳舷蕖?013年的這套筆試卷雖然以算法題為主但已經(jīng)能看出Google對(duì)候選人“系統(tǒng)性思考”的偏好。5.2 從筆試到真實(shí)工程兩個(gè)常見(jiàn)的落地陷阱這里說(shuō)兩個(gè)我在實(shí)際工作中踩過(guò)的坑和筆試題目有很強(qiáng)的關(guān)聯(lián)。第一個(gè)坑是“確認(rèn)邊界條件前就動(dòng)手設(shè)計(jì)”。筆試時(shí)題目會(huì)給你明確的輸入輸出范圍但真實(shí)工程中上游數(shù)據(jù)的格式和范圍經(jīng)常是模糊的。我曾經(jīng)負(fù)責(zé)過(guò)一個(gè)數(shù)據(jù)處理模塊當(dāng)時(shí)直接照搬筆試時(shí)的“大數(shù)組”思路寫(xiě)了一個(gè)內(nèi)存統(tǒng)計(jì)方案結(jié)果上線后發(fā)現(xiàn)上游推送的數(shù)據(jù)量是預(yù)估的幾十倍直接導(dǎo)致OOM。后來(lái)才學(xué)會(huì)在動(dòng)手寫(xiě)代碼前先確認(rèn)數(shù)據(jù)的量級(jí)、分布和延遲要求。第二個(gè)坑是“只關(guān)注時(shí)間而忽略空間”。筆試中時(shí)間復(fù)雜度的要求往往是明說(shuō)的但真實(shí)工程中空間成本往往更致命。比如在日志分析中如果每個(gè)key都在內(nèi)存里放一個(gè)計(jì)數(shù)器幾億條日志可以把內(nèi)存吃穿。這時(shí)候就要用到筆試?yán)飳W(xué)到的“哈希取模分片 離線聚合”的思路把大規(guī)模問(wèn)題拆成可并行的小塊?；剡^(guò)頭看當(dāng)年在Google筆試卷上養(yǎng)成的“先看清約束再選方案”的習(xí)慣在工作中幫了大忙。5.3 如果你現(xiàn)在準(zhǔn)備面試應(yīng)該怎么用這套題最后聊點(diǎn)實(shí)用的。假如你現(xiàn)在正在準(zhǔn)備Google或其他外企的面試這套2013年的題不應(yīng)該被當(dāng)成“直接背答案的題庫(kù)”而應(yīng)該當(dāng)成“練基本功的磨刀石”。我建議的使用順序是第一遍不限時(shí)每道題都仔細(xì)想寫(xiě)出完整代碼并通過(guò)自測(cè)。目標(biāo)是吃透題目背后的算法模型。第二遍限時(shí)模擬按筆試的節(jié)奏完整做一遍。目標(biāo)是訓(xùn)練時(shí)間管理和臨場(chǎng)應(yīng)變能力。第三遍改題訓(xùn)練把每道題的約束條件做變化思考對(duì)應(yīng)解法要做什么調(diào)整。目標(biāo)是建立“復(fù)雜度敏感”的思維習(xí)慣。用這個(gè)方法把這套題刷過(guò)三遍你的算法底子會(huì)有肉眼可見(jiàn)的提升。那時(shí)候你回頭看會(huì)發(fā)現(xiàn)這套題最寶貴的不是那些答案而是逼著你一次次思考“為什么這么做”的過(guò)程。我自己當(dāng)年刷完這套題后最大的感受是算法面試拼的不只是“會(huì)寫(xiě)代碼”更是“在限定條件下做最優(yōu)決策”的能力。這種能力靠背題背不出來(lái)只能靠一次次的思考、試錯(cuò)、復(fù)盤(pán)慢慢磨出來(lái)。希望這篇拆解能幫你少走一些彎路。