Meta NG Coding Round：CoderPad dry run 兩道真題

最近投了 Meta 的 New Grad SWE 職缺，履歷過後很快就約到了面試。這篇複盤記錄我在 Coding 輪的完整流程、真實體驗，以及碰到的兩道題。如果你也在準備 Meta 的新鮮人招募，希望這份筆記能幫你把節奏和心態調到位。

面試環境與形式概覽

整輪面試透過 Zoom 進行，寫程式用的是 CoderPad（如果碰到系統設計輪，畫圖會切到 Excalidraw）。有一點和很多公司不一樣：Meta 的 Coding 輪並不要求你的程式碼真的通過測試案例，它更看重你的思考過程和嚴謹程度。寫完之後，你必須做 dry run——把資料一行行走一遍，主動說出邊界情況。這一步考的是你對題目的掌握，以及能不能從邏輯上保證程式碼的正確性。

項目	詳情
平台	Zoom + CoderPad（系統設計用 Excalidraw）
形式	現場手寫程式碼 + 口頭講解
總時長	45 分鐘
題量	2 道，每道約 20 分鐘，留 5 分鐘緩衝
考察重點	思路清晰度、dry run 嚴謹性、邊界覆蓋

節奏很緊：如果第一題卡住，第二題基本就寫不完了。所以碰到熟悉的 tag 類型要快速判斷、果斷下手，把時間留給講解和 dry run。

Problem 1：合併區間（Merge Intervals）

題目背景

給定一組區間，把所有重疊的區間合併成盡量少的區間。這是非常典型的 tag 題，幾乎所有刷過題的人都見過。

思路

按區間的起點排序。
從左到右掃描：如果目前區間和結果裡最後一個區間重疊，就把它們合併成一個更大的區間（更新終點為兩者終點的較大值）；否則直接把目前區間加入結果。

關鍵在 dry run 時要主動驗證邊界：恰好相鄰的區間算不算重疊？空輸入怎麼處理？ 面試官在意的正是你會不會主動把這些說清楚。

Python 解法

from typing import List


def merge_intervals(intervals: List[List[int]]) -> List[List[int]]:
    """合併所有重疊的區間。

    先按起點排序，再線性掃描：能與前一個合併就合併，否則新開一段。
    """
    # 邊界情況：空輸入直接回傳空清單
    if not intervals:
        return []

    # Step 1: 按起點升冪排序
    intervals.sort(key=lambda x: x[0])

    # Step 2: 用第一個區間初始化結果
    merged = [intervals[0][:]]

    # Step 3: 逐個掃描後續區間
    for start, end in intervals[1:]:
        last = merged[-1]
        if start <= last[1]:
            # 有重疊（含恰好相鄰的情況）：把終點取較大值
            last[1] = max(last[1], end)
        else:
            # 不重疊：新開一段
            merged.append([start, end])

    return merged

Dry run 演示

用一個含多處重疊的例子最能說明問題：[[1,3],[2,6],[8,10],[15,18]]。

步驟	目前區間	結果狀態	說明
排序後	—	—	`[1,3],[2,6],[8,10],[15,18]` 起點已有序
初始化	`[1,3]`	`[[1,3]]`	放入第一個
掃描 `[2,6]`	`2 <= 3`	`[[1,6]]`	重疊，合併為 `[1,6]`
掃描 `[8,10]`	`8 > 6`	`[[1,6],[8,10]]`	不重疊，新開
掃描 `[15,18]`	`15 > 10`	`[[1,6],[8,10],[15,18]]`	不重疊，新開

最終結果 [[1,6],[8,10],[15,18]]：前兩個合併成 [1,6]，後兩個保持不變。

主動補充要驗證的邊界：

空輸入 [] → 回傳 []。
恰好相鄰 例如 [1,4],[4,5]，因為 4 <= 4 判定為重疊，合併成 [1,5]（是否合併要跟面試官確認口徑）。
完全包含 例如 [1,10],[2,3]，合併後仍是 [1,10]，靠 max 保證終點不被縮小。

時間複雜度：O(n log n)，主導項是排序。 空間複雜度：O(n)，用於存放結果（不計排序本身的開銷）。

Problem 2：課程表 —— 有向圖環偵測（Course Schedule）

題目背景

第二題明顯更難一點，是經典的 Course Schedule 變體：給定課程數和先修關係，判斷你能不能修完所有課程。本質是判斷有向圖裡是否存在環——有環就代表存在循環依賴，永遠修不完。

思路

用 BFS 拓撲排序（Kahn 演算法）：

統計每個節點的入度（有多少門先修課指向它）。
把所有入度為 0 的課程放入佇列，反覆取出一門課，把它「修掉」，並把它指向的鄰居入度減 1；鄰居入度降到 0 就入列。
如果最終處理過的課程數等於總課程數，代表無環，回傳 True；否則代表有環，回傳 False。

面試時要主動解釋為什麼選拓撲排序：因為問題本質是判斷依賴關係能否線性化，入度為 0 的節點就是「目前無任何未滿足先修條件」的課，逐層剝離即可判環。

Python 解法

from collections import deque
from typing import List


def can_finish(num_courses: int, prerequisites: List[List[int]]) -> bool:
    """判斷能否修完所有課程（等價於有向圖是否無環）。

    Kahn 拓撲排序：反覆移除入度為 0 的節點，看能否移除全部。
    prerequisites[i] = [a, b] 代表修 a 之前必須先修 b（b -> a）。
    """
    # 建構鄰接表與入度陣列
    graph = [[] for _ in range(num_courses)]
    indegree = [0] * num_courses

    for course, prereq in prerequisites:
        graph[prereq].append(course)  # prereq -> course
        indegree[course] += 1

    # Step 1: 所有入度為 0 的課程入列
    queue = deque(i for i in range(num_courses) if indegree[i] == 0)

    # Step 2: 逐個「修課」，統計已處理數量
    processed = 0
    while queue:
        node = queue.popleft()
        processed += 1
        for neighbor in graph[node]:
            indegree[neighbor] -= 1
            if indegree[neighbor] == 0:
                queue.append(neighbor)

    # Step 3: 處理完的課程數等於總數則無環
    return processed == num_courses

Dry run 演示

無環例子：num_courses = 2，prerequisites = [[1, 0]]（修 1 之前要先修 0）。

步驟	佇列	processed	說明
初始入度	—	0	課程 0 入度 0，課程 1 入度 1
入列	`[0]`	0	只有課程 0 入度為 0
取出 0	`[1]`	1	課程 1 入度減到 0，入列
取出 1	`[]`	2	無鄰居

拓撲序 [0, 1]，processed == 2 == num_courses → 回傳 True。

有環反例：num_courses = 2，prerequisites = [[0, 1], [1, 0]]（0 依賴 1，1 又依賴 0，互相依賴）。兩門課入度都是 1，一開始就沒有任何入度為 0 的節點能入列，佇列為空，processed = 0 < num_courses → 回傳 False。

補充要驗證的邊界：

無先修關係 prerequisites = []：所有課入度為 0，全部可處理，回傳 True。
單門課 num_courses = 1：直接可修完，回傳 True。

時間複雜度：O(V + E)，V 為課程數，E 為先修關係數。 空間複雜度：O(V + E)，用於鄰接表、入度陣列和佇列。

面試流程建議

Meta 的 Coding 輪並不是想「刁難」你，它檢查的是兩件事：對常見 tag 題型的熟悉度，以及能不能在時間壓力下乾淨地收尾。

tag 累積是根本：區間、排序、圖論、滑動視窗、二分搜尋這些高頻類型要練到看題即知套路，才能在 20 分鐘裡留出講解和 dry run 的時間。
dry run 是第二把鑰匙：寫完一定要用具體例子走一遍，尤其覆蓋邊界——空輸入、單元素、恰好相鄰但不重疊、有環 / 無環。主動說出這些，比程式碼「碰巧跑對」更能建立信任。
節奏管理：第一題快速下手，別戀戰；給第二題留夠時間。

FAQ

Q1：Meta 的 Coding 輪程式碼一定要通過測試嗎？

不一定。這一輪更看重你的思考過程和嚴謹性，寫完後透過 dry run 逐行走資料、主動指出邊界，從邏輯上論證正確性，比讓程式碼「碰巧 AC」更重要。

Q2：45 分鐘兩道題，節奏該怎麼安排？

每題大約 20 分鐘，留 5 分鐘緩衝。第一題若是熟悉的 tag 類型要果斷下手快速寫完，把富餘時間留給講解與 dry run；一旦第一題卡太久，第二題基本寫不完。

Q3：合併區間裡恰好相鄰的區間算重疊嗎？

取決於面試官定義，所以要主動確認。常見口徑是 [1,4] 與 [4,5] 因為端點相接算重疊、合併為 [1,5]；程式碼裡用 start <= last_end 即涵蓋這種情況。

Q4：判斷能否修完課程，為什麼用拓撲排序而不是普通 DFS？

問題本質是判斷有向圖有沒有環。Kahn 拓撲排序透過反覆移除入度為 0 的節點，如果最終無法移除全部節點，就代表存在循環依賴。它思路直觀、便於口頭解釋，也很好做 dry run。

Q5：dry run 時最該覆蓋哪些邊界？

空輸入、單元素、恰好相鄰但不重疊的區間，以及圖題裡的有環 / 無環兩類反例。把這幾類主動講出來，是這一輪拿分的關鍵。

正在準備 Meta 新鮮人 SWE 的 Coding 輪？ 我們熟悉 Meta 在 CoderPad 上的節奏和 dry run 偏好，能陪你把高頻 tag 題型和邊界表述打磨到位。

立即加入微信 Coding0201，取得一對一客製備考方案。

聯絡方式

微信：Coding0201
Email：[email protected]
Telegram：@OAVOProxy