Anthropic SDE 獨家 Coding 真題：Web Crawler（BFS + 多執行緒優化 + 系統設計）

這題本質是圖遍歷：頁面是節點、連結是邊。從一個種子 URL 出發，把同網域頁面抓完。

---

題目描述

實作一個 Web Crawler：

• 輸入：start_url
• 提供輔助函式：get_urls(url)
  • 已處理 HTTP 請求與基本連結解析
  • 回傳當前頁面的所有超連結
• 目標：
  1. 只爬取與 start_url 同網域 的 URL
  2. 每個 URL 只訪問一次
  3. 回傳最終爬到的 URL 清單

要求先完成同步版本，再優化為多執行緒版本。

---

一、同步版本（BFS）

為什麼用 BFS？

• 本題是標準圖遍歷
• 需要逐層擴展連結，BFS 最直觀
• 搭配 visited 可避免循環與重複抓取

核心要點

1. 用 urlparse 取出起始網域
2. 用佇列做 BFS
3. 用 visited 集合去重
4. 只把同網域 URL 放入佇列

Python 程式碼（同步）

from collections import deque
from urllib.parse import urlparse


def crawl_sync(start_url, get_urls):
    host = urlparse(start_url).netloc

    queue = deque([start_url])
    visited = {start_url}
    result = []

    while queue:
        url = queue.popleft()
        result.append(url)

        for nxt in get_urls(url):
            if urlparse(nxt).netloc != host:
                continue
            if nxt in visited:
                continue
            visited.add(nxt)
            queue.append(nxt)

    return result

複雜度

設同網域頁面數為 (V)，同網域連結總數為 (E)：

• 時間複雜度：(O(V + E))
• 空間複雜度：(O(V))

---

二、優化版本（ThreadPoolExecutor 並發抓取）

同步版瓶頸在 I/O 等待（網路慢），不是 CPU。最有效優化是並發。

設計思路

• 用 ThreadPoolExecutor 提交抓取任務
• 維護 future -> url 映射
• 任務一完成就立刻處理結果
• 發現新 URL 立即提交，不需等整層結束

這正是 follow-up 常問的：任務就緒後如何立即處理。

Python 程式碼（多執行緒）

from concurrent.futures import ThreadPoolExecutor, wait, FIRST_COMPLETED
from urllib.parse import urlparse


def crawl_threaded(start_url, get_urls, max_workers=8):
    host = urlparse(start_url).netloc

    visited = {start_url}
    result = []

    with ThreadPoolExecutor(max_workers=max_workers) as executor:
        in_flight = {executor.submit(get_urls, start_url): start_url}

        while in_flight:
            done, _ = wait(in_flight.keys(), return_when=FIRST_COMPLETED)

            for fut in done:
                url = in_flight.pop(fut)
                result.append(url)

                try:
                    neighbors = fut.result()
                except Exception:
                    continue

                for nxt in neighbors:
                    if urlparse(nxt).netloc != host:
                        continue
                    if nxt in visited:
                        continue
                    visited.add(nxt)
                    in_flight[executor.submit(get_urls, nxt)] = nxt

    return result

為什麼不做「逐層等待」？

逐層等待會讓執行緒池經常閒置。採用「誰先完成先處理」可更快擴展 URL，吞吐通常更高。

---

三、urlparse 在本題的作用

urlparse 主要解三件事：

1. 同網域過濾（netloc）
2. URL 正規化前處理
3. 避免把外部連結誤抓進來

面試可補充：

• 嚴格比較時可一起考慮 scheme + netloc，必要時統一預設埠號。

---

四、執行緒 vs 行程：差異與適用場景

維度	執行緒（Thread）	行程（Process）
記憶體	共享	獨立
建立/切換成本	較低	較高
Python GIL 影響	會受影響	可用多行程繞開
適用任務	I/O 密集	CPU 密集
本題適配	✅ 很適合	❌ 通常不優先

結論：Web Crawler 多數是 I/O 密集，優先執行緒或 async。

---

五、禮貌策略（避免壓垮目標站）

實務爬蟲要快也要有禮貌：

1. 遵守 robots.txt
2. 限速（全域與每網域）
3. 控制並發上限
4. 429/5xx 用指數退避重試
5. 清楚 User-Agent 與聯絡方式
6. 加入 jitter，避免固定節奏衝擊

---

六、百萬級 URL 的分散式系統設計

規模上去後通常拆成：

1. URL Frontier 佇列（Kafka/SQS/RabbitMQ）
2. Fetcher Worker 叢集（可水平擴展）
3. URL 去重服務（Redis/Bloom Filter + 持久化 KV）
4. 解析與索引管線（正文、標題、出鏈）
5. 調度與監控（重試、死信、指標）

可靠性重點：

• at-least-once 投遞 + 幂等處理
• 去重可接受最終一致

---

七、不同 URL 下的重複內容檢測

同內容常見於：追蹤參數、鏡像頁、路徑差異等。

兩層去重

1. URL 級去重

   • URL 正規化（去追蹤參數、統一 query/path）

2. 內容級去重

   • 精確指紋：SHA-256
   • 近似指紋：SimHash / MinHash

面試一句話版本：

先做 URL 正規化降低重複抓取，再做內容指紋攔截「不同 URL 同內容」。

---

八、面試回答模板

1. 先寫同步 BFS：queue + visited + same-host
2. 再做並發：ThreadPoolExecutor + 任務完成即處理
3. 補工程細節：限流、重試、退避、禮貌抓取
4. 擴展到分散式：frontier + workers + dedup + storage
5. 最後講判重：URL 正規化 + 內容指紋

這套回答通常可以覆蓋 coding 與 follow-up 的主要得分點。

---

常見坑位

• 忘記 visited，導致循環抓取
• 以字串包含判斷網域，造成誤判
• 無並發上限，瞬間打爆對方服務
• 瞬時錯誤不重試或不退避
• 只做 URL 去重，不做內容去重

---

總結

這題入門不難，但高分在工程完整度：

• 基礎：BFS 正確
• 進階：並發抓取 + 就緒即處理
• 高分：禮貌策略、分散式擴展、內容去重

只要照這條主線答，面試官通常會認為你不只會寫題，也懂真實系統。

---

🚀 需要 VO / OA 實戰輔導？

oavoservice 長期覆蓋 Anthropic、Google、Amazon、Meta、TikTok、Uber、Bloomberg 等高頻面試場景。

微信：Coding0201

可提供：

• ✅ 真題複盤與題型地圖
• ✅ 1v1 模擬面試（算法 + 系統設計）
• ✅ Follow-up 追問與表達訓練

---

聯絡方式

Email: [email protected]
Telegram: @OAVOProxy