Google SWE New Grad面试题和答案
New Grad Interview Questions & Answers
刚结束Google的Virtual Onsite，人已经麻了，赶紧趁热乎分享点面经给还在苦海里挣扎的兄弟姐妹们。不得不说，Google的面试体验还是很好的，面试官都很nice，但题目是真的不含糊，每一轮都感觉脑细胞在燃烧。
Google的New Grad SWE流程基本就是：网申 -> OA -> Virtual Onsite。OA一般是两道LC Medium难度的题，限时完成，大家把LC上Google高频题刷熟基本问题不大。Virtual Onsite就刺激了，通常是4轮背靠背，3轮Coding + 1轮Behavioral。偶尔会有一轮换成System Design，但New Grad比较少见，所以重点还是Coding。
下面分享几道我遇到或者听朋友说过的典型Coding题目，绝对不是原题，但风格很像，大家可以感受下。
第一道：Array与Sliding Window 题目大概是这样：给你一个整数Array和一个窗口大小k，让你返回一个新Array，里面是每个Sliding Window中的最大值。比如nums = [1,3,-1,-3,5,3,6,7], k = 3，那窗口移动的时候，最大值分别是[3,3,5,5,6,7]。
解题思路： 说实话，这道题第一眼看可能会想用brute force，每个窗口都遍历一遍找最大值，但Time Complexity直接飙到O(nk)，面试官肯定不会满意的。踩过坑的人都知道，这种题一般都有更优解。 正确的姿势是使用一个Deque（双端队列），队列里存放元素的index。遍历Array时，维持一个单调递减的队列，队首永远是当前窗口最大值的index。这样每个元素最多进出队列一次，Time Complexity就降到了O(n)，Space Complexity是O(k)。当时我卡了快10分钟才想到这个思路，一身冷汗。
第二道：Tree的遍历与验证 这道题也超经典：判断一个Binary Tree是不是一个有效的Binary Search Tree (BST)。
解题思路： 这题的坑在于，你不能只简单地比较每个node和它的左右child。一个合法的BST，要求左子树所有节点都小于root，右子树所有节点都大于root，而且这个规则必须对整个子树都成立。所以，光看局部是不行的。 最稳妥的方法是用DFS（或者BFS也行），在遍历的时候维持一个(min, max)的range。对于每个node，检查它的值是否在这个range里。如果不是，直接返回False。当递归到左子树时，更新max为当前node的值；递归到右子树时，更新min为当前node的值。这样一路下去，所有node都满足条件才是真BST。
第三道：综合性问题，考验代码设计
面试官描述了一个场景：设计一个系统，可以记录用户在网站上的浏览历史，并能快速返回用户最近访问的k个页面。
解题思路： 这题有点开放，有点像System Design的简化版，但主要还是考察数据结构。面试官想看的不是你写出多复杂的代码，而是你的设计思路和trade-off分析。 一个常见的实现是使用一个HashMap来存每个用户的浏览历史，key是userId，value可以是一个LinkedList。因为LinkedList在头部插入是O(1)操作，每次用户访问新页面，就把它加到这个用户的LinkedList头部。当需要查询最近k个页面时，就从头遍历这个LinkedList，取出k个元素即可。这个设计能保证记录操作非常快。如果面试官追问，比如要考虑每个用户的历史记录很长，内存占用怎么办，可以提一下用定长的Array或者Circular Array来代替LinkedList，只保留最新的N个记录。
关于System Design： New Grad轮次基本不会考完整的System Design，但可能会有上面那种“设计一个小功能”的题。重点是沟通，把你的假设、你选择的数据结构、以及它们的Time/Space Complexity都讲清楚。别闷头写代码。
关于Behavioral Question：
Google的BQ很重要，他们叫Googliness & Leadership。问题都比较常规，比如“讲一个你最有挑战的项目”、“如何处理和队友的冲突”、“你如何面对失败”等等。血泪教训是，千万别只说空话，一定要用STAR原则（Situation, Task, Action, Result）来准备几个故事。每个故事都要能体现出你的思考过程、解决问题的能力和团队合作精神。说实话，这部分准备一下性价比很高，别因为这个挂了。
总之，Google的面试就是一场马拉松，从OA到Onsite，战线拉得很长。刷题是必须的，但别只顾着刷，多思考总结，尤其是各种数据结构的优劣和应用场景。面试的时候多和面试官沟通，把你的想法大声说出来，即使思路错了也没关系，展现你的思考过程才是最重要的。希望我的这点经验能帮到大家，祝大家早日上岸！
#Google面试 #SWE #NewGrad #面经 #北美求职 #CS #SoftwareEngineer #面试经验 #FLAG #小红书
