一亩三分地论坛

 找回密码
 获取更多干货,去instant注册!

扫码关注一亩三分地公众号
查看: 4341|回复: 41
收起左侧

Google Onsite面经

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

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

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

您需要 登录 才可以下载或查看,没有帐号?获取更多干货,去instant注册!

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

电面:Number of Islands II
第一轮:
1.-google 1point3acres
给定下面的interface
  1. interface Iterator<T> {
  2.   boolean hasNext();
  3.   T next();
  4. }

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

复制代码
要求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.... 1point3acres.com/bbs

2.
实现一个lock interface
  1. interface Lock {
  2.   void acquire();
  3.   void release();
  4. }
复制代码
Follow up: 实现一个Read Write Lock 鏉ユ簮涓浜.涓夊垎鍦拌鍧.

第二轮:. 1point3acres.com/bbs
先问了一些list, set, hashmap的基本知识
给定一串log,包含Process ID, User ID, Start Time, End Time, Memory Usage,要求返回每个User最多用多少memory 鏉ユ簮涓浜.涓夊垎鍦拌鍧.

第三轮:. from: 1point3acres.com/bbs
1.
Find Nth smallest element in a binary search tree. 鐣欏鐢宠璁哄潧-涓浜╀笁鍒嗗湴
Follow up 1: 能否优化到好于O(n)
Follow up 2:如何做unit testing,如何比较两个算法的优劣. 鍥磋鎴戜滑@1point 3 acres

2.
一开始想问一道和Meeting Room II差不多的题,我说第二轮的时候问了很类似的题,他就说那我问你几个follow-up囧
首先还是那些log,问如果有很多log怎么办
我说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. visit 1point3acres.com for more.
314
. 鍥磋鎴戜滑@1point 3 acres124. 鐗涗汉浜戦泦,涓浜╀笁鍒嗗湴
玩家每一次可以把两个相邻的数字交换一下,比如如果把最中间的1和3交换一下,那么竖过来三个连续的1就可以被消除,要求随机generate这个棋盘
Follow-up:如何保证一个棋盘可以至少走一步

. visit 1point3acres.com for more.
第五轮: 鏉ユ簮涓浜.涓夊垎鍦拌鍧.
给一个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
. 1point 3acres 璁哄潧
. 1point3acres.com/bbs









.1point3acres缃

评分

6

查看全部评分

本帖被以下淘专辑推荐:

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

System design我也是完全从小白起步的,不过我觉得看完这些东西应该是够多了,至少我面了几家没有超出过这个范围
1. https://github.com/shashank88/system_design
这个可以作为一个大纲,里面提到的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
http://instagram-engineering.tum ... ng-ids-at-instagram
http://instagram-engineering.tum ... ndreds-of-instances
(2)里面的例子很好
http://www.aosabook.org/en/distsys.html
(3)Cracking the system design interview
http://www.puncsky.com/blog/2016 ... m-design-interview/
(4)海量数据处理july贴:http://blog.csdn.net/v_july_v/article/details/7382693.鏈枃鍘熷垱鑷1point3acres璁哄潧
(5)https://docs.google.com/document ... P0nrcy4eKiuA8Q/edit. from: 1point3acres.com/bbs
这里有个人总结了一些东西,可以稍微看一看
(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,这个很有用。。我亚麻面试的时候就问到了

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

使用道具 举报

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

第四轮: 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.鏈枃鍘熷垱鑷1point3acres璁哄潧
第三轮:  要做到好于 O(n), 要用 augment tree 记录左边node数之类的吧 ?

第四轮: Candy Crush, 如 ...

第三轮:对,就是要记录左子树的大小,我一开始搞错了以为要记所有比当前的数要小的个数囧
第四轮:你好像想多了,面试官只要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来存. 涓浜-涓夊垎-鍦帮紝鐙鍙戝竷
另外要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
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. Waral 鍗氬鏈夋洿澶氭枃绔,
先恭喜楼主~ 楼主拿到谷歌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用来记录左子树的大小就可以了. from: 1point3acres.com/bbs

第四轮那个只要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 ...

呃,汗颜,多谢提醒!我一定好好刷题!. 鍥磋鎴戜滑@1point 3 acres

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

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

使用道具 举报

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

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

噢你说的是最坏情况。。我是说一般情况而言的话BST这里复杂度应该是O(Height),当然面试的时候是要指出最坏情况的。。
时间复杂度来说的话你说的没错并查集要更好一点,不过面试的时候面试官只让我说了下并查集怎么做,然后还是让我写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. 1point 3acres 璁哄潧
System design我也是完全从小白起步的,不过我觉得看完这些东西应该是够多了,至少我面了几家没有超出过 ...

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

使用道具 举报

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

  1. 7
  2. 8
  3. 9
  4. 10
  5. 11. 1point 3acres 璁哄潧
  6. 12
  7. 13
  8. 14
  9. 15
  10. 16. 鍥磋鎴戜滑@1point 3 acres
  11. 17. 1point3acres.com/bbs
  12. 18
  13. 19
  14. 20. more info on 1point3acres.com
  15. 21
  16. 22
  17. 23
  18. 24
  19. 25. From 1point 3acres bbs
  20. 26
  21. 27
  22. 28
  23. 29
  24. 30
  25. 31
  26. 32. 鍥磋鎴戜滑@1point 3 acres
  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. more info on 1point3acres.com
  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)-google 1point3acres
  49.             writeLock.unlock();
  50.         readLock.unlock();   //concurrent read PRAM CREW

  51.     }. 1point3acres.com/bbs

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

  55.     public void writeunlock() {
  56.         writeLock.unlock();.鏈枃鍘熷垱鑷1point3acres璁哄潧
  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当时也跟我这么讲的. Waral 鍗氬鏈夋洿澶氭枃绔,
我不太care google给不给offer了233,主要是因为想做的那一块google并不强
回复 支持 反对

使用道具 举报

本版积分规则

请点这里访问我们的新网站:一亩三分地Instant.

Instant搜索更强大,不扣积分,内容组织的更好更整洁!目前仍在beta版本,努力完善中!反馈请点这里

关闭

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

手机版|小黑屋|一亩三分地论坛声明 ( 沪ICP备11015994号 )

custom counter

GMT+8, 2016-12-8 10:07

Powered by Discuz! X3

© 2001-2013 Comsenz Inc. Design By HUXTeam

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