剛結束 Google Virtual Onsite 第一輪技術面（R1），整體體驗非常典型的 Google 風格：題目不偏、不怪，但會透過 follow-up 深挖你對資料結構、複雜度和工程場景的理解，而不是隻看你會不會寫程式碼。面試官節奏不算快，一共兩道題，每道都有明確的 follow-up。
第一題：二叉樹遍歷與併發設計
題目本身是一個經典但很容易被低估的設計題：
設計一個迭代器，對二叉樹進行非遞迴的中序遍歷。每次呼叫 next() 返回下一個節點值，要求平均時間複雜度 O(1)。
我一開始先和麵試官確認了介面語義，比如是否需要 hasNext()、是否允許預處理整棵樹。明確不允許一次性展開後，就直接進入標準解法。核心思路是用棧來模擬遞迴呼叫過程。初始化時，從根節點開始，把當前節點以及所有左子節點一路壓棧，保證棧頂始終是當前中序遍歷中最靠前的節點。
每次呼叫 next()：
彈出棧頂節點，這個節點就是當前的返回值；
如果該節點存在右子樹，就從右子節點開始，把它以及它的所有左子節點依次壓入棧中。
這樣做的好處是完全“按需遍歷”，沒有提前生成完整的中序序列。單次 next() 雖然在最壞情況下可能會壓入多個節點，但從整體來看，每個節點只會進棧、出棧一次，因此平均時間複雜度是 O(1)，空間複雜度是 O(h)，h 為樹的高度。
面試官比較滿意這個部分，隨後進入了真正的加分點。
Follow-up：多執行緒環境下的執行緒安全設計
面試官提出了一個很 Google 的 follow-up：
如果在多執行緒環境下，多個迭代器可能同時遍歷同一棵樹，如何保證執行緒安全？
這裡的關鍵不是“加鎖就完事”，而是要區分共享狀態和私有狀態。
我的回答思路是：
如果每個 iterator 都維護自己獨立的棧結構，而樹本身在遍歷過程中是隻讀的，那麼多個迭代器併發遍歷同一棵樹本身就是執行緒安全的，不需要對樹加鎖。
真正需要考慮同步的，是單個 iterator 是否會被多個執行緒同時呼叫 next()。
如果存在這種情況，可以在 iterator 內部對 next() 方法加互斥鎖，或者使用執行緒安全的資料結構來保護棧的讀寫。
如果進一步追求效能，也可以透過“每執行緒一個 iterator”的設計來規避鎖競爭，這樣從設計層面消除併發寫問題。
面試官明顯是在考察你對併發邊界的判斷，而不是死板地回答 synchronized。
第二題：子陣列和等於 k 的計數問題
第二題是一個非常經典，但 Google 依然會考的基礎題：
給定一個整數陣列，計算有多少個子陣列的和等於目標值 k。
我直接從暴力解法切入，說明 O(n²) 不可行，然後引出字首和 + 雜湊表的最佳化方案。具體做法是：
遍歷陣列的同時維護當前字首和 sum。
用一個雜湊表記錄“某個字首和出現的次數”。當遍歷到當前位置時，如果 sum – k 在雜湊表中出現過，說明存在若干個以當前位置結尾、和為 k 的子陣列，數量正好等於 (sum – k) 出現的次數。初始化時要在雜湊表中放入 {0: 1}，代表“字首和為 0 出現過一次”，用來處理從下標 0 開始的子陣列。整體時間複雜度是 O(n)，空間複雜度 O(n)。
Follow-up：陣列包含負數時如何最佳化？
面試官在 follow-up 中強調了一點：陣列中可能包含負數，這會不會影響演算法？
這裡其實是一個“陷阱式確認”。我的回答是：
負數的存在確實會讓字首和不再單調，因此無法使用雙指標或滑窗那一套，但雜湊表記錄字首和的方法本身並不依賴單調性，時間複雜度仍然是 O(n)。如果從工程角度考慮，可以透過預估字首和的取值範圍（最大值、最小值）來最佳化雜湊表的容量分配，減少 rehash 成本，但演算法級別不需要改變。
面試關鍵節點的實戰助力
在 OA 或 VO 階段遇到瓶頸，其實不必慌。大廠的題型雖然看起來多樣，但往往可以分塊拆解：演算法核心、複雜度分析、邊界條件、思路表達。我們陪同一些同學完整走過許多大廠的 OA + VO，全程 實時輔助 ，面試過程中節奏更順，答題也更有條理，透過的機率自然更高。
