近期论坛无法登录的解决方案


一亩三分地论坛

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

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

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
  1. interface Iterator<T> {. 1point3acres.com/bbs
  2.   boolean hasNext();
  3.   T next();
  4. }

  5. interface predicate<T> {
  6.   boolean apply(T item)
  7. }.鐣欏璁哄潧-涓浜-涓夊垎鍦


复制代码
要求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.. From 1point 3acres bbs
实现一个lock interface
  1. interface Lock {
  2.   void acquire();
  3.   void release();. 1point 3acres 璁哄潧
  4. }
复制代码
Follow up: 实现一个Read Write Lock
.鏈枃鍘熷垱鑷1point3acres璁哄潧
第二轮:. 1point3acres.com/bbs
先问了一些list, set, hashmap的基本知识. 鍥磋鎴戜滑@1point 3 acres
给定一串log,包含Process ID, User ID, Start Time, End Time, Memory Usage,要求返回每个User最多用多少memory

第三轮:
1.
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囧. more info on 1point3acres.com
首先还是那些log,问如果有很多log怎么办
我说Shard by user ID,他说不行,我要求返回所有user最多可能用多少memory,于是我说那可以根据start time和end time做bucket sort
. 鐣欏鐢宠璁哄潧-涓浜╀笁鍒嗗湴
第四轮:
1. Word Pattern的简单版,只要字母和字母互相对应就行,比如$^((*和hello是互相match的. more info on 1point3acres.com
2. 类似于Candy Crush游戏,在一个棋盘里随机填1,2,3,4,例如:
121-google 1point3acres
314. 1point3acres.com/bbs
124
玩家每一次可以把两个相邻的数字交换一下,比如如果把最中间的1和3交换一下,那么竖过来三个连续的1就可以被消除,要求随机generate这个棋盘
Follow-up:如何保证一个棋盘可以至少走一步


第五轮:
给一个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










. 涓浜-涓夊垎-鍦帮紝鐙鍙戝竷

评分

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
这个可以作为一个大纲,里面提到的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里面的一些文章,根据你要面什么公司来看,下面这篇不错. 1point 3acres 璁哄潧
http://highscalability.com/blog/ ... tions-bottlene.html
5. 推荐几个比较有用的文章
(1)instgram如何Shard by ID
http://instagram-engineering.tum ... ng-ids-at-instagram. visit 1point3acres.com for more.
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
(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,这个很有用。。我亚麻面试的时候就问到了

. more info on 1point3acres.com读写锁的那题我其实写的不大好,所以就不献丑了,不过你可以参考这个网站,基本上涵盖了所有面试中能考到的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 | 显示全部楼层
关注一亩三分地微博:
Warald
第三轮:  要做到好于 O(n), 要用 augment tree 记录左边node数之类的吧 ?-google 1point3acres

第四轮: Candy Crush, 如果数字种类很多, keep 一个有解的patten, 随机到一个位置 , 剩下纯随机, 数字太少的话,每一行固定每个数字平均数量, 打乱, 还有什么别的想法 ?
.1point3acres缃
第五轮: 第二个 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(好像是不需要的)
第五轮:算法上没问题,但是如何判断是否在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 | 显示全部楼层
多谢楼主分享,请问一下:. 1point 3acres 璁哄潧
第三轮中二叉搜索树最坏情况就是单链表,为何能够优化到好于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. from: 1point3acres.com/bbs
多谢楼主分享,请问一下:. 鐗涗汉浜戦泦,涓浜╀笁鍒嗗湴
第三轮中二叉搜索树最坏情况就是单链表,为何能够优化到好于O(n)呢?难道是需要 ...
-google 1point3acres
bst那题,同学你要好好刷LeetCode啊(敲黑板)(不对)
https://leetcode.com/problems/kth-smallest-element-in-a-bst/
这道题的follow up就是优化的方法,只要修改BST里的节点的data structure,增加一个Count用来记录左子树的大小就可以了

-google 1point3acres第四轮那个只要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. 1point3acres.com/bbs
bst那题,同学你要好好刷LeetCode啊(敲黑板)(不对)
https://leetcode.com/problems/kth-smallest-el ...

呃,汗颜,多谢提醒!我一定好好刷题!

不过我没理解这里BST为啥不能被建成单链表?题目里有明确说到会自动平衡吗?或者给的其实是AVL树?如果是普通的二叉搜索树那最坏情况应该是单链表,高度本身就是节点总数,而且只能从唯一顶点开始顺序遍历,不能跳跃,为何可以优于O(n)呢?
. Waral 鍗氬鏈夋洿澶氭枃绔,
第五轮的题空间复杂度的确是DFS更优,我之前没想到,非常感谢提醒!!!时间复杂度上并查集的最坏情况应该比纯深搜的最坏情况要好?假设M<<N,当给定的第二个队列包含链表的两个端点(假定无环)或者间隔最远的两个节点(有环无环均可)时,深搜都应该无法比并查集的时间复杂度更优了吧?
回复 支持 反对

使用道具 举报

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

不过我没理解这里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.鏈枃鍘熷垱鑷1point3acres璁哄潧
System design我也是完全从小白起步的,不过我觉得看完这些东西应该是够多了,至少我面了几家没有超出过 ...

楼主你太好了!!!!!!!!!!!!!!!.鐣欏璁哄潧-涓浜-涓夊垎鍦
你一定会拿到心仪的offer的呐!. Waral 鍗氬鏈夋洿澶氭枃绔,
系统设计题一般都是让说一下思路什么的对吧?
回复 支持 反对

使用道具 举报

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. from: 1point3acres.com/bbs
  14. 20
  15. 21
  16. 22
  17. 23
  18. 24
  19. 25
  20. 26
  21. 27
  22. 28
  23. 29
  24. 30. 1point 3acres 璁哄潧
  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
  36.     Mutex writeLock; // write lock. only lock when read perform.
  37.     int numsOfreadLock = 0;-google 1point3acres
  38. . from: 1point3acres.com/bbs
  39.     public void readlock() {
  40.         readLock.lock();
  41.         numsOfreadLock++;.鐣欏璁哄潧-涓浜-涓夊垎鍦
  42.         if (numsOfreadLock == 1)
  43.             writeLock.lock();
  44.         readLock.unlock();  //concurrent read PRAM CREW. 1point3acres.com/bbs
  45.     }
  46. . From 1point 3acres bbs
  47.     public void readunlock() {
  48.         readLock.lock();
  49.         numsOfreadLock--;
  50.         if (numsOfreadLock == 0)
  51.             writeLock.unlock();
  52.         readLock.unlock();   //concurrent read PRAM CREW

  53.     }

  54.     public void writelock() {
  55.         writeLock.lock();
  56.     }
  57. .鐣欏璁哄潧-涓浜-涓夊垎鍦
  58.     public void writeunlock() {
  59.         writeLock.unlock();
  60.     }
  61. . more info on 1point3acres.com
  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,好捉急的说。。楼主 ...

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

使用道具 举报

本版积分规则

关闭

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

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

custom counter

GMT+8, 2017-6-28 15:13

Powered by Discuz! X3

© 2001-2013 Comsenz Inc. Design By HUXTeam

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