這次幫同學复盤了一下 Apple 的兩輪純 Coding，整體節奏挺快的，題目雖然都是常規套路，但考察的都是“寫代碼 → 推思路 → 抗追問能力”這一整套鍊路。下面我把兩輪的題目、關鍵思路、以及面試官追問方向都整理出來，大家刷題/準備時可以對照下重點。
第 1 輪｜Subarray Sum Equals K
面試官給的題很直接：
給定數組 nums 和整數 k，找出所有和恰好等於 k 的連續子數組數量。
思路拆解
這題最容易犯的錯誤就是想用 sliding window。但只要數組裡有負數或 0，窗口法就直接不可用。所以真正穩定的解法只有一個：
前綴和 + 哈希表
- 遍歷數組，維護當前前綴和 sum
- 如果之前出現過 prefix = sum – k，則說明從 prefix 的位置到當前的這段子數組和為 k
- 哈希表記錄每個前綴和出現過幾次
- 初始化 {0:1}，代表“從頭到當前位置正好等於 k”也能計數
一句話：前綴和負責定位，哈希表負責統計數量。
代碼示例（Python）
def subarray_sum(nums, k):
from collections import defaultdict
cnt = defaultdict(int)
cnt[0] = 1
s = 0
ans = 0
for x in nums:
s += x
ans += cnt[s - k]
cnt[s] += 1
return ans
複雜度
时间 O(n)，空间 O(n)
面試官追問
1）負數或 0 會不會影響你這個算法？
不會影響前綴和方案，但會讓 sliding window 徹底失效。能把這個點講清楚，面試官會直接認可你對問題結構的理解。
2）空間能不能優化？
如果題目要求“統計數量”，基本無法從 O(n) 降下來。
如果只是“判斷是否存在某個子數組和為 k”，那可以用集合，但不適合計數。
3）為什麼哈希表中存的是“前綴和出現次數”？
因為不同前綴位置都可能構成一個新的子數組，所以要統計出現次數，而不是只記錄有沒有出現。
第 2 輪｜二叉樹中序遍歷迭代器
題目要求設計一個中序遍歷的迭代器，不能提前把整棵樹遍歷完，必須是惰性的。
思路拆解
這題本質是在考你能不能把“遞歸中序遍歷的過程”改成“顯式棧 + 惰性邏輯”。
核心做法：維護一條從當前節點往左走到底的路徑
初始化：把根節點一路往左的節點全部入棧
next()：
- 彈棧
- 如果有右子樹，把右子樹一路往左 push 進棧
- 返回當前節點的值
代碼示例（Python）
class InorderIterator:
def __init__(self, root):
self.st = []
self._push_left(root)
def _push_left(self, node):
while node:
self.st.append(node)
node = node.left
def hasNext(self):
return bool(self.st)
def next(self):
node = self.st.pop()
if node.right:
self._push_left(node.right)
return node.val
複雜度
next() 均攤 O(1)
空間 O(h)
面試官追問方向
1）多個迭代器同時訪問同一棵樹會不會有問題？
- 如果樹是只讀的（面試一般默認只讀），多個迭代器各自維護自己的棧，沒有問題
- 如果樹會被寫，需要加：
- 版本號（fail-fast）
- 讀寫鎖
- 或 snapshot 策略
能把優缺點說明白即可
2）如果樹退化成鍊錶，會不會很耗空間？
會，但這是中序遍歷的下界，不可避免。只要你能解釋“為什麼無法減少空間”，面試官就不會繼續深挖。
3）跟遞歸中序遍歷相比，有什麼改進？
遞歸不是惰性的，而且有系統棧限制；迭代器是可控空間，按需訪問。
為什麼選擇 ProgramHelp？你的 Offer，我們來保駕護航。
我們是精英團隊的“代言人”：
- Elite Background: 團隊由來自 Google、Meta、Amazon 的前資深工程師、以及 CMU、Stanford、清華、北大 校友組成。
- 絕對掌控力： 我們擁有北美 CS/Quant/Data 市場最新的題庫，對各大公司的面試風格和 Gating Factor 瞭如指掌。
拒絕廉價低端，我們提供的是 High-End 解決方案：
| 服務項目 | 市場平均水準（低端） | ProgramHelp.net （High-End / 零風險） |
| OA 輔助 (CodeSignal/HackerRank) | 腳本/廉價槍手；代碼風格差；查重風險高 | 真人實時原創代碼；過查重；保你 All Cases Passed |
| VO 輔助 | 延遲高；溝通障礙；被發現風險大 | 無延遲實時屏幕/語音輔助；配合默契；教你 “Think Aloud” 完美應付面試官 |
| ROI | 浪費 $500，Offer 仍然不穩 | 投資 $400+/小時，換取 $180k+ 的北美高薪 Offer |
END
