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