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