最近刚结束一场谷歌的远程技术面,过程还算丝滑,题目有点意思,分享出来给大伙儿攒攒经验值。疫情后 Google 面试全面转线上,刚开场气氛还算轻松,寒暄几句之后,面试官直接在共享文档里打出了题目:
Q: How many people can the last one in line see?
Clarification:
- A person A can see another person B in front of them if there is no one taller than both A and B standing between them.
- Every person has a different height.
Input: [1, 10, 6, 7, 9, 8, 2, 4, 3, 5]
Output: 6
我第一时间想到的并不是直接暴力双重循环去检查“每一个人是否被挡住”,而是根据规则从后往前扫描,这样能顺带模拟“最后一位”的视角。
我对面试官说了我的大致思路:“我打算从倒数第二个开始往前扫,一边记住当前看到的最高身高,一边统计有多少人比这个高度高——因为他们就能被最后一个人看到。”
对方点了点头,说“试试看怎么实现”。
我在共享编辑器中写了个最小可运行逻辑:用一个变量 maxHeight
来记录当前最高的“阻挡视线的人”,只要一个人比这个 maxHeight
还高,那他就可见,然后更新 maxHeight
。整个过程是线性时间,符合大厂对性能的期望。
运行了一下示例,结果是 6,和期望一致。
这时候,面试官继续追问:“那如果输入是空数组,或者只有一个人呢?”
我意识到考的是边界条件判断能力,于是立刻加了个判断:if heights == null or len <= 1: return 0
,避免 IndexOutOfBounds
错误。
接下来他问我:“时间和空间复杂度分别是多少?”
我答:时间复杂度是 O(n),只扫一遍数组;空间复杂度是 O(1),只用了常数个变量。面试官满意地点头。
最后他追问了一个 follow-up:如果不是最后一个人,而是中间某个人想看前面,怎么处理?
我简单回应说:那就不能只记录一个 maxHeight
,可能要倒着从那个位置开始扫描,然后在中间加一层判断,也许可以写成一个通用函数,传入一个位置,返回该人能看到的数量。这个 follow-up 没要求实现,但我讲了思路。
这道题表面简单,但实际要做到“代码稳健 + 性能合理 + 逻辑讲清楚 + 边界思考”,其实是很典型的 Google 风格。题不难,但考点全都在细节和讲述方式里。
祝各位拿到心仪的 Google offer,远程面试不比现场简单,但流程清晰、心态稳,代码落地快,机会就在眼前。
本文的作者 石老师,在这里给大家打个硬广,csoahelp.com每日分享北美大厂面经,小红书也有更新,我们还提供种类多样的收费服务协助您进入北美科技大厂,有意向的微信扫码联系我,或者也可以通过其他方式联系我
