刚结束 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，全程 实时辅助 ，面试过程中节奏更顺，答题也更有条理，通过的概率自然更高。
