面試題解析 第 50 頁，共 52 頁
瀏覽 OfferCC 面試題解析第 50 頁，查看解題思路、實作細節、追問與公開來源。
演算法面試：如何從未知長度的資料流中均勻抽樣？
用 Reservoir Sampling 在單次掃描與 O(k) 記憶體限制下維護 k 個等機率樣本，推導不變量、證明正確性並處理邊界。
如何設計分散式唯一 ID 產生器？
從容量限制推導 Snowflake 位元配置，處理時鐘回撥、worker 身分、序號溢位和多區域故障，並比較 UUIDv7 與號段方案。
類別極度不平衡時，如何選擇模型指標與分類門檻？
從混淆矩陣、審核容量和誤判成本推導分類指標與決策門檻，並說明 AUROC、PR 曲線、機率校準及基準率變化各自解決什麼問題。
演算法面試：如何選擇不重疊工作以取得最大收益？
用加權區間排程串起排序、二分搜尋與動態規劃，說清楚邊界定義、正確性證明、複雜度與方案回復。
如何設計分散式任務排程器，避免漏執行與重複執行？
從執行實例識別、分片時間索引與至少一次投遞出發，設計支援單次及 Cron 任務的多租戶排程器，並處理整點尖峰、錯過觸發、時區、取消競態與故障復原。
機器學習中的資料洩漏是什麼？如何發現與避免？
以詐欺辨識模型為例，建立預測時間契約，排查目標、時間、實體與預處理洩漏，並設計可信的資料切分、交叉驗證和最終留出測試。
程式設計面試：如何實作動態陣列並證明 append 的攤銷 O(1)？
從容量不變量、幾何擴容與攤銷證明出發，實作可索引的動態陣列，並解釋空間與最壞情況成本。
如何設計支援簡訊、Email 與推播的多管道通知系統？
以每日 10 億個管道投遞任務為假設，設計同時承載 OTP 與行銷活動的通知系統，釐清優先級隔離、投遞狀態、亂序回呼、重試與可驗證的故障復原。
串流處理如何應對延遲與亂序事件，確保視窗彙總正確？
以每小時營收為例，從事件時間、watermark、允許延遲與去重狀態推導串流處理方案，並處理結果修正、狀態清理、故障復原與離線對帳。
程式設計面試：如何返回出現頻率最高的 K 個單字？
用雜湊計數、客製最小堆和嚴格的頻率/字典序比較器，在 O(n log k) 時間內返回 Top K 單字。
系統設計面試：如何實作跨區域全域限流？
用配額租約實作全域 API 上限，量化網路分區時的超放邊界，並處理熱點區域再平衡和明確故障策略。
程式面試：如何實作不允許重疊的日程預約？
用半開區間、前驅後繼查找與有序映射實作 My Calendar I，說明邊界、複雜度與並行服務的變化。
演算法面試：如何除錯雙堆動態中位數實作？
針對只在交錯極值、重複值與偶數長度出錯的 MedianFinder，用不變量、最小反例和對照測試定位並修復。
Coding 面試：如何實作一個 O(1) 查詢最小值的堆疊？
通過輔助堆疊維護每個深度的最小值，在 push、pop 和 getMin 都保持 O(1)，並處理重複最小值與空堆疊邊界。
程式設計面試：實作一個 Bloom Filter
實作支援 add 與 mightContain 的 Bloom Filter，說明誤判、參數估算、刪除限制與測試。
程式設計面試：實作一個執行緒安全的讀寫鎖
練習用互斥量、條件變數與等待計數實作讀寫鎖，並解釋公平性、升級與失敗情境。
程式設計面試：實作帶 TTL 的快取
用雜湊表、過期時間和惰性清理實作可測試的 TTL 快取，並討論並行、容量與時間邊界。
程式設計面試：如何實作支援合併與查詢的區間集合？
實作一個維護不重疊區間的集合，支援插入、刪除、點查詢和區間查詢，並說明邊界、合併和複雜度。
程式設計面試：如何實作支援更新和刪除的穩定優先佇列？
用堆、索引表和惰性刪除實作可更新優先級的優先佇列，並處理相同優先級、刪除、失效項目和複雜度證明。
程式設計面試：如何設計可恢復的分批迭代器？
從 hasNext/next 契約出發，設計按頁讀取遠端資料、支援暫停恢復、避免重複並正確傳遞錯誤的迭代器。
演算法面試：如何實作快照陣列？
用依索引組織的變更歷史、同版本寫入合併和二分前驅查詢實作快照陣列，並證明時間、空間與快照語意。
演算法面試：最少需要多少間會議室？
把會議區間轉化為同時佔用資源數，用雙陣列掃描線求最少會議室，並透過重疊深度證明最優性，涵蓋半開區間、同刻事件、堆積解法與房間分配追問。
程式面試：用拓撲排序解外星字典
從已排序詞表中只擷取有依據的字元先後限制，再用拓撲排序還原未知字母表。掌握無效前綴、環偵測、正確性證明、多解判斷和對抗性測試。
演算法面試：如何用迭代 DFS 計算島嶼數量？
從連通分量建模推導原地迭代 DFS，說明為何要在入堆疊時標記，並涵蓋複雜度、正確性、邊界測試與替代方案。