传说中的谷歌招聘委员会成员之一,从幕后走出来,教你学系统设计!


一亩三分地论坛

 找回密码
 获取更多干活,快来注册
天天打游戏、照样领工资、还办H1B
这份工作你要不要?
把贵司招聘信息放这里
查看: 11505|回复: 43
收起左侧

Google Onsite面经

[复制链接] |试试Instant~ |关注本帖
jimmyzzxhlh 发表于 2016-8-10 10:58:56 | 显示全部楼层 |阅读模式

2016(7-9月) 码农类 硕士 全职@Google - 内推 - 技术电面 Onsite |Other其他

注册一亩三分地论坛,查看更多干货!

您需要 登录 才可以下载或查看,没有帐号?获取更多干活,快来注册

x
刚刚面完G家,由于已经接了另外一家offer,于是轻松上阵,发个面经回馈地里

电面:Number of Islands II
第一轮:
1.
给定下面的interface
游客,本帖隐藏的内容需要积分高于 188 才可浏览,您当前积分为 0。 查看如何攒积分
要求implement一个filter function如下:
  1. Iterator<T> filter(Iterator<T> in, predicate<T> pred);
复制代码
predicate里的apply就是起到check的作用,比如说T是Integer,然后当一个integer是偶数的时候apply function返回True,否则返回False,那么filter function就是实现一个偶数的iterator
例如如果不断call next()的话,Iterator<T> in返回的是0,1,2,3,4,5,6,...,那么filter function返回的那个iterator应该能输出0,2,4,6...

2.
实现一个lock interface
  1. interface Lock {
  2.   void acquire();
  3.   void release();
  4. }
复制代码
Follow up: 实现一个Read Write Lock

第二轮:
先问了一些list, set, hashmap的基本知识
给定一串log,包含Process ID, User ID, Start Time, End Time, Memory Usage,要求返回每个User最多用多少memory

第三轮:. 鍥磋鎴戜滑@1point 3 acres
1.
Find Nth smallest element in a binary search tree
Follow up 1: 能否优化到好于O(n)
Follow up 2:如何做unit testing,如何比较两个算法的优劣

2.. 鍥磋鎴戜滑@1point 3 acres
一开始想问一道和Meeting Room II差不多的题,我说第二轮的时候问了很类似的题,他就说那我问你几个follow-up囧
首先还是那些log,问如果有很多log怎么办. 1point3acres.com/bbs
我说Shard by user ID,他说不行,我要求返回所有user最多可能用多少memory,于是我说那可以根据start time和end time做bucket sort

第四轮:
1. Word Pattern的简单版,只要字母和字母互相对应就行,比如$^((*和hello是互相match的
2. 类似于Candy Crush游戏,在一个棋盘里随机填1,2,3,4,例如:
121
314
124
玩家每一次可以把两个相邻的数字交换一下,比如如果把最中间的1和3交换一下,那么竖过来三个连续的1就可以被消除,要求随机generate这个棋盘
Follow-up:如何保证一个棋盘可以至少走一步

. from: 1point3acres.com/bbs
第五轮:
给一个Double Linked List,例如:
游客,本帖隐藏的内容需要积分高于 188 才可浏览,您当前积分为 0。 查看如何攒积分

.1point3acres缃




. from: 1point3acres.com/bbs
.1point3acres缃


. From 1point 3acres bbs


评分

7

查看全部评分

本帖被以下淘专辑推荐:

 楼主| jimmyzzxhlh 发表于 2016-8-16 02:23:58 | 显示全部楼层
答案默默 发表于 2016-8-15 14:33 鏉ユ簮涓浜.涓夊垎鍦拌鍧.
请问楼主的system design是怎么准备的呢?
还有还有,小白想请教一下那个读写锁那一题的第一问和follow  ...

System design我也是完全从小白起步的,不过我觉得看完这些东西应该是够多了,至少我面了几家没有超出过这个范围
1. https://github.com/shashank88/system_design. from: 1point3acres.com/bbs
这个可以作为一个大纲,里面提到的david malans的lecture必须要看
2. http://www.hiredintech.com/system-design/
url shortening service必须要看,同时可以看这个http://n00tc0d3r.blogspot.com/
3. http://blog.gainlo.co/index.php/ ... nterview-questions/-google 1point3acres
这个网站里面每个例子都是面试题
4. highscalability.com里面的一些文章,根据你要面什么公司来看,下面这篇不错
http://highscalability.com/blog/ ... tions-bottlene.html
5. 推荐几个比较有用的文章
(1)instgram如何Shard by ID
http://instagram-engineering.tum ... ng-ids-at-instagram
http://instagram-engineering.tum ... ndreds-of-instances
(2)里面的例子很好.1point3acres缃
http://www.aosabook.org/en/distsys.html.鐣欏璁哄潧-涓浜-涓夊垎鍦
(3)Cracking the system design interview.鏈枃鍘熷垱鑷1point3acres璁哄潧
http://www.puncsky.com/blog/2016 ... m-design-interview/
(4)海量数据处理july贴:http://blog.csdn.net/v_july_v/article/details/7382693
(5)https://docs.google.com/document ... P0nrcy4eKiuA8Q/edit
这里有个人总结了一些东西,可以稍微看一看
(6)https://discuss.leetcode.com/top ... n-phone-browsing/15. 1point 3acres 璁哄潧
Leetcode站长(?)关于如何design chat application的一些思路,可以和这个结合起来看
http://blog.gainlo.co/index.php/ ... book-chat-function/
(7)Scalable system design pattern
http://horicky.blogspot.com/2010 ... esign-patterns.html
(8)https://www.adayinthelifeof.nl/2011/02/06/memcache-internals/
memcache如何design,这个很有用。。我亚麻面试的时候就问到了. from: 1point3acres.com/bbs

读写锁的那题我其实写的不大好,所以就不献丑了,不过你可以参考这个网站,基本上涵盖了所有面试中能考到的multi-thread/concurrency的问题了(包括read-write lock,thread pool,blocking queue)
http://tutorials.jenkov.com/java-concurrency/index.html
回复 支持 5 反对 0

使用道具 举报

lvvvvv 发表于 2016-8-10 11:31:47 | 显示全部楼层
第三轮:  要做到好于 O(n), 要用 augment tree 记录左边node数之类的吧 ?

第四轮: Candy Crush, 如果数字种类很多, keep 一个有解的patten, 随机到一个位置 , 剩下纯随机, 数字太少的话,每一行固定每个数字平均数量, 打乱, 还有什么别的想法 ?

第五轮: 第二个 list 能判断在不在这个list 里吗?(I mean if it is a real linked list ?), 可以的话, 任取一个node pointer, 向左向右, 每步判断在不在 list 里, 断开就是一个 group。  还是我想简单了 ?
回复 支持 反对

使用道具 举报

 楼主| jimmyzzxhlh 发表于 2016-8-10 11:41:53 | 显示全部楼层
lvvvvv 发表于 2016-8-10 11:31
第三轮:  要做到好于 O(n), 要用 augment tree 记录左边node数之类的吧 ?

第四轮: Candy Crush, 如 ...
. more info on 1point3acres.com
第三轮:对,就是要记录左子树的大小,我一开始搞错了以为要记所有比当前的数要小的个数囧 鏉ユ簮涓浜.涓夊垎鍦拌鍧.
第四轮:你好像想多了,面试官只要4个数字就行
主要问题是如何随机效率比较高,另外算法需不需要back tracking(好像是不需要的)
第五轮:算法上没问题,但是如何判断是否在list里才是真正的问题,另外如何从list里移走已经访问过的node
回复 支持 反对

使用道具 举报

Lilian1109 发表于 2016-8-10 23:29:02 | 显示全部楼层
第五轮, {1,3,4,5} 给的是list还是set?如果用 set的话, 可以另定义一个 set存已经visit 过的nodes。 dfs应该是比较直接的。 这样是不改变原来的double-linked list。
感觉应该也可以选择改变原有double linked list, 可以节省空间。
回复 支持 反对

使用道具 举报

 楼主| jimmyzzxhlh 发表于 2016-8-11 01:24:23 | 显示全部楼层
Lilian1109 发表于 2016-8-10 23:29
第五轮, {1,3,4,5} 给的是list还是set?如果用 set的话, 可以另定义一个 set存已经visit 过的nodes ...

给的是list,所以要转换成set,你说的对得定义另一个set,实际我用hashmap来存. 1point3acres.com/bbs
另外要clarify是不是所有的node里的value是不同的,如果有相同的话,那么就不是很容易定义equals了
回复 支持 反对

使用道具 举报

mooc 发表于 2016-8-12 06:05:53 | 显示全部楼层
好奇问一句lz都怎么准备G家面试的?能否分享一下?
回复 支持 反对

使用道具 举报

 楼主| jimmyzzxhlh 发表于 2016-8-12 10:25:05 | 显示全部楼层
mooc 发表于 2016-8-12 06:05
好奇问一句lz都怎么准备G家面试的?能否分享一下?

Leetcode刷个好几遍是必须的,然后看了很多system design方面的东西,结果并没有碰到什么。。

补充内容 (2016-8-16 02:26):. more info on 1point3acres.com
应该说碰到了一点点system design吧,不过不是很多
回复 支持 反对

使用道具 举报

答案默默 发表于 2016-8-15 14:33:08 | 显示全部楼层
jimmyzzxhlh 发表于 2016-8-12 10:25. 鍥磋鎴戜滑@1point 3 acres
Leetcode刷个好几遍是必须的,然后看了很多system design方面的东西,结果并没有碰到什么。。
. 鐗涗汉浜戦泦,涓浜╀笁鍒嗗湴
请问楼主的system design是怎么准备的呢?
还有还有,小白想请教一下那个读写锁那一题的第一问和follow up楼主还有具体的代码么???完全不会
回复 支持 反对

使用道具 举报

howeflguap 发表于 2016-8-16 09:35:02 | 显示全部楼层
多谢楼主分享,请问一下:. From 1point 3acres bbs
第三轮中二叉搜索树最坏情况就是单链表,为何能够优化到好于O(n)呢?难道是需要优化算法的lower bound?
第四轮(2)中在followup之前,生成棋盘只要[1, 4]中随机挑选就行?还是有额外要求?
第五轮中链表给定都是排序好的吗?如果可以任意顺序给出,那为何并查集会不如纯搜索呢?
回复 支持 反对

使用道具 举报

low910411 发表于 2016-8-16 10:01:54 | 显示全部楼层
先恭喜楼主~ 楼主拿到谷歌offer了嘛
回复 支持 反对

使用道具 举报

 楼主| jimmyzzxhlh 发表于 2016-8-16 10:58:11 | 显示全部楼层
low910411 发表于 2016-8-16 10:01. 1point 3acres 璁哄潧
先恭喜楼主~ 楼主拿到谷歌offer了嘛

还没,G家一向非常非常慢,基本整个流程要一个月左右。。
回复 支持 反对

使用道具 举报

 楼主| jimmyzzxhlh 发表于 2016-8-16 11:10:17 | 显示全部楼层
howeflguap 发表于 2016-8-16 09:35
多谢楼主分享,请问一下:
第三轮中二叉搜索树最坏情况就是单链表,为何能够优化到好于O(n)呢?难道是需要 ...

bst那题,同学你要好好刷LeetCode啊(敲黑板)(不对)
https://leetcode.com/problems/kth-smallest-element-in-a-bst/.鏈枃鍘熷垱鑷1point3acres璁哄潧
这道题的follow up就是优化的方法,只要修改BST里的节点的data structure,增加一个Count用来记录左子树的大小就可以了. 涓浜-涓夊垎-鍦帮紝鐙鍙戝竷

第四轮那个只要1-4中随机选就行
第五轮链表不是排好序的,给的input list也不是排好序的,如果链表里的节点数是N,input list的节点数是M,并查集不好是因为空间复杂度会变成O(N),纯搜索的话空间复杂度是O(M)
回复 支持 反对

使用道具 举报

howeflguap 发表于 2016-8-16 12:41:24 | 显示全部楼层
jimmyzzxhlh 发表于 2016-8-16 11:10
bst那题,同学你要好好刷LeetCode啊(敲黑板)(不对)
https://leetcode.com/problems/kth-smallest-el ...
. 鐣欏鐢宠璁哄潧-涓浜╀笁鍒嗗湴
呃,汗颜,多谢提醒!我一定好好刷题!

不过我没理解这里BST为啥不能被建成单链表?题目里有明确说到会自动平衡吗?或者给的其实是AVL树?如果是普通的二叉搜索树那最坏情况应该是单链表,高度本身就是节点总数,而且只能从唯一顶点开始顺序遍历,不能跳跃,为何可以优于O(n)呢?

第五轮的题空间复杂度的确是DFS更优,我之前没想到,非常感谢提醒!!!时间复杂度上并查集的最坏情况应该比纯深搜的最坏情况要好?假设M<<N,当给定的第二个队列包含链表的两个端点(假定无环)或者间隔最远的两个节点(有环无环均可)时,深搜都应该无法比并查集的时间复杂度更优了吧?
回复 支持 反对

使用道具 举报

 楼主| jimmyzzxhlh 发表于 2016-8-16 12:47:29 | 显示全部楼层
howeflguap 发表于 2016-8-16 12:41
呃,汗颜,多谢提醒!我一定好好刷题!

不过我没理解这里BST为啥不能被建成单链表?题目里有明确说到 ...

噢你说的是最坏情况。。我是说一般情况而言的话BST这里复杂度应该是O(Height),当然面试的时候是要指出最坏情况的。。. visit 1point3acres.com for more.
时间复杂度来说的话你说的没错并查集要更好一点,不过面试的时候面试官只让我说了下并查集怎么做,然后还是让我写dfs去了
回复 支持 反对

使用道具 举报

howeflguap 发表于 2016-8-16 12:51:41 | 显示全部楼层
jimmyzzxhlh 发表于 2016-8-16 12:47
噢你说的是最坏情况。。我是说一般情况而言的话BST这里复杂度应该是O(Height),当然面试的时候是要指出最 ...

多谢多谢,这番交流收获颇丰,祝愿楼主早日拿到offer!
回复 支持 反对

使用道具 举报

答案默默 发表于 2016-8-16 15:55:03 | 显示全部楼层
jimmyzzxhlh 发表于 2016-8-16 02:23
System design我也是完全从小白起步的,不过我觉得看完这些东西应该是够多了,至少我面了几家没有超出过 ...

楼主你太好了!!!!!!!!!!!!!!!
你一定会拿到心仪的offer的呐!
系统设计题一般都是让说一下思路什么的对吧?
回复 支持 反对

使用道具 举报

readman 发表于 2016-8-16 20:08:29 | 显示全部楼层

  1. 7
  2. 8
  3. 9
  4. 10
  5. 11
  6. 12
  7. 13
  8. 14
  9. 15
  10. 16
  11. 17
  12. 18
  13. 19
  14. 20
  15. 21
  16. 22
  17. 23
  18. 24
  19. 25
  20. 26
  21. 27
  22. 28
  23. 29
  24. 30
  25. 31
  26. 32
  27. 33
  28. 34
  29. 35
  30. public class ReadWriteLock {
  31.     interface Mutex {// given an mutex
  32.         public void lock();
  33.         public void unlock();
  34.     }
  35.     Mutex readLock; // read lock, in order to support PRAM CREW.  it only lock when. 1point3acres.com/bbs
  36.     Mutex writeLock; // write lock. only lock when read perform.. 鐣欏鐢宠璁哄潧-涓浜╀笁鍒嗗湴
  37.     int numsOfreadLock = 0;

  38.     public void readlock() {
  39.         readLock.lock();
  40.         numsOfreadLock++;
  41.         if (numsOfreadLock == 1)
  42.             writeLock.lock();
  43.         readLock.unlock();  //concurrent read PRAM CREW
  44.     }

  45.     public void readunlock() {
  46.         readLock.lock();
  47.         numsOfreadLock--;
  48.         if (numsOfreadLock == 0). Waral 鍗氬鏈夋洿澶氭枃绔,
  49.             writeLock.unlock();
  50.         readLock.unlock();   //concurrent read PRAM CREW. 1point 3acres 璁哄潧

  51.     }

  52.     public void writelock() {
  53.         writeLock.lock();
  54.     }

  55.     public void writeunlock() {
  56.         writeLock.unlock();
  57.     }. 涓浜-涓夊垎-鍦帮紝鐙鍙戝竷

  58. }
复制代码
回复 支持 反对

使用道具 举报

low910411 发表于 2016-8-16 22:19:37 | 显示全部楼层
jimmyzzxhlh 发表于 2016-8-16 10:58
还没,G家一向非常非常慢,基本整个流程要一个月左右。。

我上上周也是去onsite,然后hr到现在还没给结果,因为有一个其他家的pending offer,好捉急的说。。楼主你已经签了,那假如谷歌给offer怎么办呀。我在想要不要先签了其他家,实在不行再毁约,可是又觉得毁约是不是不太好 = = 求意见~~~谢谢哈
回复 支持 反对

使用道具 举报

 楼主| jimmyzzxhlh 发表于 2016-8-16 23:28:11 | 显示全部楼层
low910411 发表于 2016-8-16 22:19
我上上周也是去onsite,然后hr到现在还没给结果,因为有一个其他家的pending offer,好捉急的说。。楼主 ...

你有拿着pending offer去催么?他们一定要有competing offer催一下才会快,HR当时也跟我这么讲的
我不太care google给不给offer了233,主要是因为想做的那一块google并不强
回复 支持 反对

使用道具 举报

本版积分规则

关闭

一亩三分地推荐上一条 /5 下一条

手机版|小黑屋|一亩三分地论坛声明

custom counter

GMT+8, 2017-9-22 21:52

Powered by Discuz! X3

© 2001-2013 Comsenz Inc. Design By HUXTeam

快速回复 返回顶部 返回列表