【Google】【Software Engineer】【New Grad Phone Screen】Phone Screen 两道 Coding，面试官节奏很舒服

【Google】Software Engineer New Grad Phone Screen

基本信息

面试题目（按提问顺序）

1. Binary Tree Right Side View

• Given a binary tree, return an array of the values of all nodes visible from the right side (i.e., the last node at each level when viewed from the right).
• 解法思路：BFS 逐层遍历，每层取最后一个节点值即可。用队列做层序遍历，每层遍历时取出所有节点，取最后一个，再将下一层所有节点入队。
• Follow-up：如果树非常深（百万层），如何优化？讨论空间复杂度从 O(n) 优化到 O(h) 的方案。

1. K Smallest Pairs Sum

• Given two sorted arrays arr1 and arr2, and an integer k, find the k smallest sums where each sum is arr1[i] + arr2[j].
• 解法思路：使用 Min-Heap。先将所有 (arr1[i] + arr2[0], i, 0) 入堆，每次弹出最小值 (sum, i, j)，若 j+1 < len(arr2) 则将 (arr1[i] + arr2[j+1], i, j+1) 入堆，重复 k 次。
• Follow-up：时间复杂度分析？如果两个数组长度差距很大，如何优化？

面试感受 / 反馈

• 面试官是华人 senior engineer，全程英文沟通，但语速适中、态度友好
• 两道题难度适中，都属于 LeetCode Medium，45 分钟内完成两题节奏合理
• 每道题都有清晰的 hint 在注释中给出，不会有"猜题意"的情况
• 面试官很注重 communication，每写一步都会确认你是否理解了题意
• Google 的时间管理做得很好，基本到点结束，不会拖沓

准备建议

• 刷题重点：BFS/DFS 树题、Heap 相关题目，LeetCode 上 Google 标签的 Medium 题刷 50+ 道
• 面试时务必 边写边讲解思路，不要默默写完再解释
• 提前准备好 "Tell me about yourself" 的 1-2 分钟英文版本
• 对复杂度分析要脱口而出，面试官一定会问 follow-up