題幹與適用情境
你接手一個 MedianFinder：較小的一半放最大堆，較大的一半放最小堆。它能處理 1, 2, 3，卻會在 10, 1, 9, 2、大量重複值和極端整數下失敗。本題要求除錯既有實作，不再重複從零推導雙堆。
面試官考察點
- 能否先寫清楚不變量，再修改程式碼。
- 能否縮小失敗序列，找到第一次非法狀態。
- 能否涵蓋空查詢、重複值和偶數長度溢位。
- 證明、複雜度和實作是否一致。
回答前需要釐清的問題
- 第一次插入前呼叫
findMedian()應回傳什麼？ - 哪個堆允許多一個元素？
- 輸入整數寬度與回傳型別是什麼？
- 是否允許重複值，並行是否在範圍內？
本題假設重複值有效，下半堆可多一個元素，查詢回傳浮點數，空查詢拋出明確錯誤；並行不在範圍內。
30 秒回答框架
「我會在每次插入後檢查兩個不變量：下半堆和上半堆大小相等，或下半堆多一個；兩個堆都非空時，下半堆頂不能大於上半堆頂。先把失敗輸入縮成最小反例，再統一用『插入下半堆、把最大值移到上半堆、必要時把上半堆最小值移回』修復。偶數長度先擴寬數值型別再算平均。最後用排序陣列作真值，對短序列窮舉並涵蓋交錯極值。」
分步驟深入解答
第一步：讓錯誤狀態可見
每次插入後記錄輸入前綴、兩個堆的大小和堆頂，一旦不變量失效就停止。不斷刪除輸入值並重跑，直到得到仍可重現的最短序列。四個數的反例比一千個隨機數更容易說明。
第二步：使用確定的插入流程
所有新值先進入下半堆，再把下半堆最大值移到上半堆；若上半堆變大，就把它的最小值移回。這個順序先修復左右順序，再修復大小。只有最小堆的語言可在下半堆儲存負數，但符號轉換要集中在邊界。
第三步：處理查詢與數值安全
兩個堆都空時拒絕查詢。總數為奇數時回傳下半堆頂；偶數時先把兩個端點轉成更寬或浮點型別再相加，避免固定寬度整數在中位數可表示時仍發生加法溢位。
第四步：證明並驗證修復
把下半堆最大值移到上半堆後，留下的下半部不會越過邊界；再移回一個上半堆最小值，只會恢復大小規則，不會破壞順序。每次插入執行常數次堆操作，因此是 O(log n)；查詢 O(1)，空間 O(n)。
每個前綴都與排序陣列結果比對。測試空查詢、一個值、兩個極值、遞增、遞減、交錯高低、全重複、負數，以及奇偶長度反覆切換。
高品質示範回答
「我不會只修補當前失敗分支。我先斷言兩個堆大小相等或下半堆多一個，並在兩邊非空時斷言 max(lower) <= min(upper)。插入時統一先進 lower，再把最大值移到 upper；只有 upper 較大時才把最小值移回。這樣正確性不依賴輸入順序。
空結構查詢會報錯。奇數長度取 lower 堆頂，偶數長度先擴寬兩個堆頂再算平均，避免極端整數溢位。我會讓每個輸入前綴都和排序陣列真值比較，並對包含負數、零、重複值和極值的小集合窮舉。複雜度仍是插入 O(log n)、查詢 O(1)、空間 O(n)。」
常見錯誤
- 只平衡大小 → 兩堆的值仍可能交叉 → 單獨檢查堆頂順序不變量。
- 只根據新值選擇分支 → 舊堆狀態可能繼續非法 → 統一執行堆間移動。
- 用輸入整數型別直接相加 → 極值平均會溢位 → 相加前擴寬。
- 只測有序且不重複的值 → 分支缺陷無法暴露 → 每個前綴對照並加入交錯極值。
- 聲稱插入
O(1)→ 堆的 push/pop 是對數級 → 依真實操作計算複雜度。
追問及應對
如何找到最小失敗輸入？
逐個或分段刪除輸入並重跑不變量，保留仍然失敗的最短前綴，再只分析造成第一次失效的那次插入。
為什麼重複值不需要特殊分支？
不變量使用 <=，相等值可以落在任一側。中位數由堆大小決定，與重複值的身分無關。
不信任另一份雙堆實作時如何測試？
對小輸入直接複製並排序，再按數學定義計算中位數。先窮舉小字母表序列，再補固定寬度極值與大規模隨機資料。
這套實作支援滑動視窗嗎？
不支援。刪除任意過期值需要可索引刪除，或在兩個堆增加延遲刪除計數；那是另一道獨立題。