【通知】7月22,工业界资深数据科学家教你破解各大公司面试!


一亩三分地论坛

 找回密码
 获取更多干活,快来注册

一亩三分地官方iOS手机应用下载
查看: 10725|回复: 43
收起左侧

Google Onsite面经

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

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

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

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

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

电面:Number of Islands II
第一轮:
1.
给定下面的interface
  1. interface Iterator<T> {
  2.   boolean hasNext();
  3.   T next();. 鐣欏鐢宠璁哄潧-涓浜╀笁鍒嗗湴
  4. }

  5. interface predicate<T> {
  6.   boolean apply(T item)
    .鏈枃鍘熷垱鑷1point3acres璁哄潧
  7. }. visit 1point3acres.com for more.


复制代码
要求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

第三轮:
1.. visit 1point3acres.com for more.
Find Nth smallest element in a binary search tree
Follow up 1: 能否优化到好于O(n)
Follow up 2:如何做unit testing,如何比较两个算法的优劣

2.
一开始想问一道和Meeting Room II差不多的题,我说第二轮的时候问了很类似的题,他就说那我问你几个follow-up囧
首先还是那些log,问如果有很多log怎么办. 1point 3acres 璁哄潧
我说Shard by user ID,他说不行,我要求返回所有user最多可能用多少memory,于是我说那可以根据start time和end time做bucket sort
. 鍥磋鎴戜滑@1point 3 acres
第四轮:
1. Word Pattern的简单版,只要字母和字母互相对应就行,比如$^((*和hello是互相match的
2. 类似于Candy Crush游戏,在一个棋盘里随机填1,2,3,4,例如:. Waral 鍗氬鏈夋洿澶氭枃绔,
121
314
124
玩家每一次可以把两个相邻的数字交换一下,比如如果把最中间的1和3交换一下,那么竖过来三个连续的1就可以被消除,要求随机generate这个棋盘
Follow-up:如何保证一个棋盘可以至少走一步. from: 1point3acres.com/bbs

.1point3acres缃
第五轮:
给一个Double Linked List,例如:
1<=>2<=>3<=>4<=>5
再给一个List,存的是某些Node的指针,例如存的是1,3,4,5,要求找这些Node里有多少group,一个Group里的Node是连通的
比如3,4,5是连通的,但是不和1直接连通,所以返回2个group
我一开始以为是Union Find,结果发现Union Find更复杂,直接用dfs就行,不过要注意用HashSet的话会有问题
然后同样要设计test case

. Waral 鍗氬鏈夋洿澶氭枃绔,


.1point3acres缃

. 1point3acres.com/bbs





评分

6

查看全部评分

本帖被以下淘专辑推荐:

 楼主| jimmyzzxhlh 发表于 2016-8-16 02:23:58 | 显示全部楼层
关注一亩三分地公众号:
Warald_一亩三分地
答案默默 发表于 2016-8-15 14:33
请问楼主的system design是怎么准备的呢?
还有还有,小白想请教一下那个读写锁那一题的第一问和follow  ...

System design我也是完全从小白起步的,不过我觉得看完这些东西应该是够多了,至少我面了几家没有超出过这个范围
1. https://github.com/shashank88/system_design.1point3acres缃
这个可以作为一个大纲,里面提到的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/
这个网站里面每个例子都是面试题
4. highscalability.com里面的一些文章,根据你要面什么公司来看,下面这篇不错
http://highscalability.com/blog/ ... tions-bottlene.html
5. 推荐几个比较有用的文章
(1)instgram如何Shard by ID. 1point 3acres 璁哄潧
http://instagram-engineering.tum ... ng-ids-at-instagram
http://instagram-engineering.tum ... ndreds-of-instances
(2)里面的例子很好
http://www.aosabook.org/en/distsys.html. more info on 1point3acres.com
(3)Cracking the system design interview
http://www.puncsky.com/blog/2016 ... m-design-interview/. Waral 鍗氬鏈夋洿澶氭枃绔,
(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
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,这个很有用。。我亚麻面试的时候就问到了
-google 1point3acres
读写锁的那题我其实写的不大好,所以就不献丑了,不过你可以参考这个网站,基本上涵盖了所有面试中能考到的multi-thread/concurrency的问题了(包括read-write lock,thread pool,blocking queue).1point3acres缃
http://tutorials.jenkov.com/java-concurrency/index.html
回复 支持 5 反对 0

使用道具 举报

lvvvvv 发表于 2016-8-10 11:31:47 | 显示全部楼层
关注一亩三分地微博:
Warald
第三轮:  要做到好于 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, 如 ...

第三轮:对,就是要记录左子树的大小,我一开始搞错了以为要记所有比当前的数要小的个数囧
第四轮:你好像想多了,面试官只要4个数字就行
主要问题是如何随机效率比较高,另外算法需不需要back tracking(好像是不需要的). visit 1point3acres.com for more.
第五轮:算法上没问题,但是如何判断是否在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 ...
. more info on 1point3acres.com
给的是list,所以要转换成set,你说的对得定义另一个set,实际我用hashmap来存
另外要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):
应该说碰到了一点点system design吧,不过不是很多
回复 支持 反对

使用道具 举报

答案默默 发表于 2016-8-15 14:33:08 | 显示全部楼层
jimmyzzxhlh 发表于 2016-8-12 10:25. from: 1point3acres.com/bbs
Leetcode刷个好几遍是必须的,然后看了很多system design方面的东西,结果并没有碰到什么。。

请问楼主的system design是怎么准备的呢?
还有还有,小白想请教一下那个读写锁那一题的第一问和follow up楼主还有具体的代码么???完全不会
回复 支持 反对

使用道具 举报

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

使用道具 举报

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/
这道题的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 ...

呃,汗颜,多谢提醒!我一定好好刷题!
. Waral 鍗氬鏈夋洿澶氭枃绔,
不过我没理解这里BST为啥不能被建成单链表?题目里有明确说到会自动平衡吗?或者给的其实是AVL树?如果是普通的二叉搜索树那最坏情况应该是单链表,高度本身就是节点总数,而且只能从唯一顶点开始顺序遍历,不能跳跃,为何可以优于O(n)呢?

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

使用道具 举报

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

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

噢你说的是最坏情况。。我是说一般情况而言的话BST这里复杂度应该是O(Height),当然面试的时候是要指出最坏情况的。。. Waral 鍗氬鏈夋洿澶氭枃绔,
时间复杂度来说的话你说的没错并查集要更好一点,不过面试的时候面试官只让我说了下并查集怎么做,然后还是让我写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. 鍥磋鎴戜滑@1point 3 acres
  6. 12
  7. 13
  8. 14
  9. 15 鏉ユ簮涓浜.涓夊垎鍦拌鍧.
  10. 16. From 1point 3acres bbs
  11. 17
  12. 18
  13. 19
  14. 20
  15. 21
  16. 22
  17. 23
  18. 24.1point3acres缃
  19. 25. visit 1point3acres.com for more.
  20. 26.鏈枃鍘熷垱鑷1point3acres璁哄潧
  21. 27
  22. 28
  23. 29
  24. 30
  25. 31
  26. 32
  27. 33
  28. 34. From 1point 3acres bbs
  29. 35. more info on 1point3acres.com
  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
  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. -google 1point3acres
  46.     public void readunlock() {
  47.         readLock.lock();
  48.         numsOfreadLock--;
  49.         if (numsOfreadLock == 0)
  50.             writeLock.unlock();
  51.         readLock.unlock();   //concurrent read PRAM CREW

  52.     }
  53. . visit 1point3acres.com for more.
  54.     public void writelock() {. more info on 1point3acres.com
  55.         writeLock.lock();
  56.     }
  57. . 1point 3acres 璁哄潧
  58.     public void writeunlock() {
  59.         writeLock.unlock();
  60.     }
  61. . visit 1point3acres.com for more.
  62. }
复制代码
回复 支持 反对

使用道具 举报

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,好捉急的说。。楼主 ...
. from: 1point3acres.com/bbs
你有拿着pending offer去催么?他们一定要有competing offer催一下才会快,HR当时也跟我这么讲的.鐣欏璁哄潧-涓浜-涓夊垎鍦
我不太care google给不给offer了233,主要是因为想做的那一块google并不强
回复 支持 反对

使用道具 举报

本版积分规则

关闭

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

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

custom counter

GMT+8, 2017-7-23 06:59

Powered by Discuz! X3

© 2001-2013 Comsenz Inc. Design By HUXTeam

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