Anthropic Fellow OA 復盤：GPU 排程 + ML Debug

最近走了一遍 Anthropic Fellow 的線上測評，前後一共兩個部分：OA1 是九十分鐘的程式實作，分成五道遞進的關卡；交卷後不到半小時，OA2 的 Debug 題就寄到了信箱。這篇復盤把兩部分的形式、真實節奏和核心考點都記下來，如果你也在準備 Anthropic 這類偏系統與 ML 工程的 OA，希望這份筆記能幫你少走彎路。需要 OA輔助 或 OA代面 的同學，也可以照著後面的思路對齊節奏。

OA 整體流程概覽

階段	時長	形式	考點
OA1	90 分鐘	五道獨立關卡，每關一個 .py 檔，呼叫給定系統程式碼（系統程式碼不可修改）	系統實作、狀態機建模、逐關加難
OA2	交卷後半小時內寄出	Debug 題：修復給定程式碼裡的 bug（ML 方向）	程式碼閱讀、定位缺陷、保持向量化

兩部分的味道完全不同：OA1 更像系統實作，你要在別人給好的介面上把排程邏輯搭起來；OA2 更像線上救火，考的是讀程式碼和除錯。下面分別拆開講。

---

OA1：LLM 推論請求排程器（五關遞進）

題目背景

OA1 的五道關卡圍繞同一個主題：實作一個 LLM 推論請求排程器，風格接近 vLLM / SGLang。每一關是一個獨立的 .py 檔，都要呼叫題目提供的「系統程式碼」裡的函式，而系統程式碼本身不能改動。五關實作的東西各不相同、難度逐級遞增，這裡以最能體現排程核心的一關為例。

一個請求的生命週期是這樣的：

1. 請求先進入 waiting（等待）佇列。
2. 經過一次 Prefill 後變為 admitted（已接納）。
3. 之後逐 token Decode。
4. 生成 token 數達到 max_tokens 時 finished（完成）。

每個時間步 GPU 的算力有上限 max_work，一步內消耗不能超過它。排程順序是硬性規定的：

• 先 按到達順序為所有 admitted 請求做 Decode，每個消耗 1 單元。
• 再 用剩餘算力，按到達順序為 waiting 請求做 Prefill，每個消耗 prompt_len。
• 關鍵約束：如果 waiting 佇列首的請求裝不下，就立刻停止這一輪的 Prefill——不能跳過它去排程後面更小的請求。

思路

維護三組狀態 waiting / admitted / finished。每一步從 remaining = max_work 開始：

1. Decode 階段：按到達順序走訪 admitted，每個消耗 1 單元；generated 達到 max_tokens 的移入 finished，否則留在 admitted。
2. Prefill 階段：從 waiting 佇列首取請求，只有 prompt_len <= remaining 才 Prefill 並移入 admitted；一旦佇列首裝不下就 break。
3. 每一步回傳本步排程的任務，並更新狀態與已生成 token 數。

注意一個細節：本步剛被 Prefill 的請求，這一步不會 Decode——因為 Prefill 排在 Decode 之後，它要等到下一步才開始出 token。

Python 實作

先給出題目提供的「系統程式碼」示意介面（唯讀，不可修改）：

from collections import deque
from typing import Dict, List


# ==== 系統程式碼（不可修改，僅示意介面） ====
class Request:
    def __init__(self, req_id: int, prompt_len: int, max_tokens: int):
        self.req_id = req_id
        self.prompt_len = prompt_len   # Prefill 需要的 GPU 單元數
        self.max_tokens = max_tokens   # 需要 Decode 出的 token 總數
        self.generated = 0             # 已生成的 token 數


def prefill(req: Request) -> int:
    """系統程式碼：完成 Prefill，回傳消耗的 GPU 單元數。"""
    return req.prompt_len


def decode_one(req: Request) -> int:
    """系統程式碼：Decode 一個 token，回傳消耗的 GPU 單元數（恆為 1）。"""
    req.generated += 1
    return 1

複雜度：prefill 與 decode_one 均為 O(1)。

再是我們要實作的排程器：

class Scheduler:
    """LLM 推論排程器：先 Decode 全部 admitted，再用剩餘算力 Prefill waiting。"""

    def __init__(self, max_work: int):
        self.max_work = max_work
        self.waiting: deque[Request] = deque()   # 尚未 Prefill
        self.admitted: deque[Request] = deque()  # 已 Prefill，正在 Decode
        self.finished: List[Request] = []

    def add(self, req: Request) -> None:
        self.waiting.append(req)

    def step(self) -> Dict[str, List[int]]:
        remaining = self.max_work
        decoded: List[int] = []
        prefilled: List[int] = []

        # 階段一：Decode —— 按到達順序服務所有 admitted，每個消耗 1 單元
        carry: deque[Request] = deque()
        while self.admitted:
            req = self.admitted.popleft()
            if remaining < 1:
                carry.append(req)              # 算力耗盡，下一步再 Decode
                continue
            remaining -= decode_one(req)       # 消耗 1 單元，generated += 1
            decoded.append(req.req_id)
            if req.generated >= req.max_tokens:
                self.finished.append(req)      # 達到上限，完成
            else:
                carry.append(req)
        self.admitted = carry

        # 階段二：Prefill —— 從 waiting 佇列首開始，佇列首裝不下就立刻停
        while self.waiting:
            head = self.waiting[0]
            if head.prompt_len > remaining:
                break                          # 佇列首放不下：不能跳過它去排程後面更小的請求
            self.waiting.popleft()
            remaining -= prefill(head)
            self.admitted.append(head)
            prefilled.append(head.req_id)

        return {"decode": decoded, "prefill": prefilled}

複雜度：單步 O(A + P)，A 為目前 admitted 數量、P 為本步新 Prefill 的數量；空間 O(N)，N 為在途請求總數。

Dry run 演示

設 max_work = 4，一開始加入三個請求（到達順序 R0、R1、R2）：

請求	prompt_len	max_tokens
R0	2	2
R1	3	1
R2	1	1

逐步走一遍 step()：

step	起始 remaining	Decode	Prefill	結束狀態（waiting / admitted / finished）
1	4	—	R0（-2）；R1 需 3 > 2，停	[R1,R2] / [R0] / []
2	4	R0（-1，generated=1）	R1（-3）；R2 需 1 > 0，停	[R2] / [R0,R1] / []
3	4	R0（generated=2，完成）、R1（generated=1，完成）	R2（-1）	[] / [R2] / [R0,R1]
4	4	R2（generated=1，完成）	waiting 空	[] / [] / [R0,R1,R2]

重點看第 1 步：remaining = 2 時佇列首 R1 需要 3 裝不下，即便後面的 R2 只需 1 也不能跳過 R1 去 Prefill R2——這正是題目最容易踩的坑。

拿分策略

五關逐級加難，穩妥的打法是先把靠前的基礎關吃乾淨：狀態機（waiting → admitted → finished）和「先 Decode 後 Prefill、佇列首裝不下即停」這條主幹一旦搭對，後面幾關多半是在它上面疊約束（例如搶佔、優先級、批次大小限制）。別一上來死磕最後一關，把基礎分鎖死再往上衝。

---

OA2：Debug Extremely Randomized Trees

題目背景

交完 OA1 不到半小時，信箱就收到了 OA2——一道 Debug 題，ML 方向。題目給了一份基本能跑但有 bug 的 Extremely Randomized Trees（Extra-Trees）實作，缺陷會導致當機或準確率異常。你需要閱讀 trees.py 和 tests/test_trees.py，從失敗的測試出發定位並修復問題。測試和文件不能改；不要求做速度最佳化，但不能把 NumPy 向量化操作換成明顯更慢的多層迴圈。

思路

不要一上來通讀全部程式碼，而是從報錯和失敗測試倒推：

1. 先跑完整測試套件，看哪些用例掛了、報什麼錯。
2. 針對每個失敗用例逐個收斂，定位到具體函式。
3. 重點排查這幾類地方：
   • 樹的停止條件（深度 / 樣本數 / 純度）是否正確。
   • 隨機特徵與隨機閾值的選取（Extra-Trees 的核心是閾值在特徵取值範圍內均勻隨機）。
   • 左右劃分的遮罩邊界（< 與 <=、以及左右是否互補完備）。
   • 空節點 / 葉子的處理。
   • 預測聚合（分類多數投票、迴歸取平均）。
   • 測試期望的隨機種子約定。
4. 保持原有介面和 NumPy 向量化；每修一處就重跑相關測試，最後再跑全套。

一個典型 bug 與修復

最常見的一類缺陷出在左右劃分：右子集本應是左子集的補集，卻被複製貼上寫成了同一個方向，導致右子樹永遠為空——要麼遞迴停不下來，要麼準確率崩掉。

# Before（bug）：左右用了同一個比較方向，右子集恆為空
left_mask = X[:, feat] <= threshold
right_mask = X[:, feat] <= threshold      # 複製貼上錯誤，應是補集

# After（fix）：右子集取補集，保證劃分互斥且完備，且保留向量化
left_mask = X[:, feat] <= threshold
right_mask = ~left_mask

另一類高頻坑是隨機特徵取樣的 off-by-one：np.random.randint(0, n_features - 1) 永遠取不到最後一個特徵，應寫成 np.random.randint(0, n_features)（上界開區間）。

# Before（bug）：最後一個特徵永遠不會被選中
feat = np.random.randint(0, n_features - 1)

# After（fix）：randint 上界是開區間，用 n_features 才能涵蓋全部特徵
feat = np.random.randint(0, n_features)

說明：這類修復都是常數級改動，不改變演算法整體複雜度——建樹仍是 O(n · d · depth) 量級，向量化劃分保持 O(n)，切忌為了「看起來對」而退化成逐樣本的多層迴圈。

---

備考建議

• OA1 先鎖基礎分：把請求狀態機和「Decode 優先、Prefill 佇列首不可跳過」這條主幹打牢，靠前的關卡穩拿，再向難關疊加約束。
• OA2 從報錯出發：先跑全套測試，用失敗用例定位，別通讀全程式碼；改一處、跑一次，逐步收斂。
• 守住既有約束：系統程式碼不可改、測試不可改、向量化不可退化——這些是隱性評分點，踩線會直接掉分。
• 兩部分節奏銜接：OA1 交卷後半小時內 OA2 就會來，中途別徹底放鬆，留好精力切換到「讀程式碼 + 除錯」的狀態。

---

FAQ

Q1：OA1 的五關一定要全做完嗎？

不一定。五關遞進加難，評分是累積的。穩妥策略是先把靠前的基礎關做乾淨、拿滿分，再往難關衝；把主幹（狀態機 + 排程順序）搭對，後面幾關往往是在它上面加約束。

Q2：排程裡為什麼佇列首裝不下就要停，而不是跳過去排程更小的請求？

這是題目明確規定的排程語意：Prefill 嚴格按到達順序，waiting 佇列首放不下就立刻停止本輪，保證先到先服務、避免大請求被無限延後。跳過佇列首去 Prefill 後面更小的請求會違反題意，直接判錯。

Q3：本步剛 Prefill 的請求，這一步會 Decode 嗎？

不會。每步是「先 Decode 全部 admitted，再 Prefill waiting」。請求是在 Decode 階段之後才被 Prefill 並加入 admitted 的，所以它要等到下一步才開始逐 token Decode。

Q4：OA2 的 Debug 題，應該先通讀全部程式碼嗎？

不建議。更高效的做法是先跑完整測試套件，從失敗用例和報錯訊息倒推，鎖定具體函式再看局部程式碼。重點查停止條件、隨機特徵 / 閾值選取、左右劃分遮罩、空節點處理和預測聚合。

Q5：OA2 說不能退化向量化，具體指什麼？

題目允許你不追求極致效能，但禁止把 NumPy 的向量化操作（如布林遮罩劃分、批次比較）改寫成明顯更慢的逐樣本多層迴圈。修復 bug 時保留原有的向量化寫法，改動控制在常數級即可。

---

正在準備 Anthropic Fellow 這類偏系統實作 + ML 工程的 OA？ 我們熟悉 vLLM / SGLang 風格的推論排程題和 Extra-Trees 這類 Debug 題的考法，能陪你把狀態機建模、排程語意和除錯節奏一次打磨到位，提供全程 OA輔助 與 OA代面 支援。

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

聯絡方式

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