Google onsite面经

Job Hunting Interview
, , , , ,
1

一共五轮coding，最后一轮两个题

  1. Next greater element leetcode 556， followup是十六进制数字怎么处理，再followup是float number，比如1.58， 返回5.18。如果是8.51，那么应该返回 15.8。
  2. count different rhythm style
  3. implement hashmap snapshot function，实现下面几个方法
    a. V Get(K)
    b. void Put(K, V)
    c. int snapshot()
    b. V snapshotGet(K, int snapshotId)
    讨论两种解法的runtime和space的tradeoff，第二种解法要求用binary search 进一步优化runtime
  4. currency exchange
  5. a. remove extra edge: binary tree to delete the node have two parents，followup是BST
    b. 猜一个五位的单词 - 要求起猜的单词
2 Likes
3

graph的课上讲过

参考 399. Evaluate Division

5

啊，楼主今天收到了通知，已经过了 hiring committee！Xcode的课程还是挺有用的，考到的题基本都讲过，比如currency exchange和第一道题。听了之后基本思路就非常清晰，甚至在考的时候考官说这个情况是我下一个要考的点:joy: 这就非常有意思了。第3道题好像也是在某次旁听的时候，听到模拟面试的一道题，里面有两种实现方法，老师都提到了并且讲解了一遍，这次做的时候就非常的顺畅。如果没有上过课感觉我就只能当场想就很可怕了，都不知道能不能做出来。总之非常感谢Xcode里老师的努力！开心:grin:

6

楼主是new grad嘛？还是在职跳槽？

7

New grad，通过foobar获得的面试机会

8

New grad不是4轮coding吗

9

可能是skip电面了，所以要补回一轮

10

沾沾喜气

11

求问楼主timeline, 我也是通过foobar拿到面试的, 今天刚面完电面

12

我和他们说我有pending offer, 所以比较快。大概是面试完之后3天就联系我，同时进行team match，然后就是等所有面试成绩出来是7天后，大概成绩出来的同时就开始了team match

13

啊，team match完了，感觉都还不错。第一个组的manager感觉比较严肃，像是面试一样问了许多bq，并且一开始不告诉我他们组做什么，最后才介绍他们组。第二个组感觉更加随和一点，一直在和我介绍他们的工作。都是非常不错的组，能有这么一个机会也是非常的开心~最后选择了第二个组AdWords，总包裹大概17k左右

1 Like
14

是170K，少了个零吧

15

啊啊，是的，是170k，写错了，少了个0:joy:

16

adwords贡献谷歌80%的收入吧，cashcow

17

这个我也店面考到了，面的狗家电面，应该是白人小哥一上来就开始做题。恢复二叉树：即二叉树中多了一个edge，要求把这个edge找出来并且去掉。之前看的面经里这道题，面试官会给个follow up：现在树中多了不止一条edge，全部找出来并去掉。但是感觉无follow up的代码可以达到同样的效果？

18

楼主方便说下第三题是哪两种方法吗谢谢了

19

一种是 binary search 吧

20

对，优化解法就是用额外的map对每个key存历史上出现过的snapshot ids，这个ids 是递增的，因此可以binary search。
这里每个生成的snapshot存储的是与上个snapshot之间的put操作，也就是只存变化。另外删除操作需要用一个特定的object来表示，而不能用null。
第一种解法自然是存全量啦。

21

这题是一样的，描述差不多：

Google Snapshot。实现三个functions， get, set, take snapshots。其实就是一个长度为N的Array。Set可以设置Index i的值，每次take snapshot， version + 1，并且记录下当前version下 Array里面的值。然后get方法可以得到某一个Version下，每一个Index的Array的值

22

这题有很多细的follow up，比如怎么标记删除