一亩三分地《新生手册+美国生活指南》下载

一亩三分地论坛

 找回密码
 Sign Up 注册获取更多干货

最近看过此主题的会员

E轮2.5亿美元融资
K12教育独角兽一起作业
北京-诚聘人工智能/教育/大数据岗
码农求职神器Triplebyte:
不用海投
内推多家公司面试
前Google华人高管创立
面试offer一键直通
Leap.ai助你进入热门独角兽
硅谷知名AI创业公司
图灵视频
招聘多个工程师职位
查看: 16249|回复: 364
收起左侧

google 2018四月onsite面筋

    [复制链接] |试试Instant~ |关注本帖
我的人缘0
凯伦小龙虾 发表于 2018-4-17 21:48:50 | 显示全部楼层 |阅读模式
本楼: 【顶】   100% (8)
 
 
0% (0)   【踩】
全局: 顶  100% (75)
 
 
0% (0)  踩

2018(4-6月) 码农类General 硕士 全职@Google - 猎头 - Onsite  | Pass | 在职跳槽

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

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

x
分享一波4月10号Onsite 面筋,现在在team match 阶段

1.黑哥哥
input: 一些字符串words, 一个目标字符串, 要求返回words里 包含了所有目标字符串里的所有char 的词中最短的那个。
eg:  words = [study, haha, stone, school, star, store]  target = "rts", 需要返回 的词是star, 因为star 包含了所有rts, 同时也是最短。
来源一亩.三分地论坛.
follow-up: 多种方法优化这道题的方法, 楼主先排序 (要求写出查找的平均时间复杂度),
楼主还答了可以把words 存成 s: study, stone, school, star, stor; t : star, stone, store..... 这样的map, 好处是我们查找的时候只需要看target里出现过的char所对应的词,然后找并集,在目标字符串很小的情况下有可能会省很多时间。


2.白姐姐 . visit 1point3acres for more.
用preorder和postorder建树,这道题出来时我说好像没有inorder是做不出来的,然后聚了个例子,面试管说那就假设总是有left subtree的,然后楼主用recursion写了。完了分析时间复杂度,问怎么优化(hashmap 存一边postorder里的val 对应的Index)
.本文原创自1point3acres论坛
3. 白大哥-google 1point3acres
类似乐扣伞就无 但不一样的是这个api不能存query, 不负责接收query,不负责发送,只是会每1秒让n个isAllowed() 返回true. 这题我当场有点懵,我就说了那就写一个count和clear, 然后每秒清零count。但这样做会造成每秒前10个可以,会形成每秒一个峰值。面试官问可不可以有一个更平均的分布,我说那就每1/n秒返回一个true, 然后清零... (我知道这样做很笨,但当场没有想到更好的方法。面试官一直强调说不能存任何和query有关的东西(除了计数),只负责yes or no然后保证这个rate的正确性),写完码答了怎么unit test

4.  话很多的白姐姐
. 牛人云集,一亩三分地这个姐姐是我面得最开心的一轮,她整个人很活波,一直笑,让我放松了很多。
给一个char stream,  有next(), 和hasNext(), 两个API。 给一些字符串作为目标字符串。要求每当char stream里出现目标字符串任何一个词,就打印这个词。
比如目标 'abc, att, bba, bc, abce', 然后我们对char stream call next, 出来的一些char 是 t, a, b, c, e, t.... 我们需要打印 abc, bc, abce
这题用字典树,比较麻烦的是需要在字典树里存多个指针,然后每次出来一个char,就写一个Loop来更新所有现有的指针就可以给了。

5. 话很少的白哥哥
乐扣巴以无
这题我面试前一天看过一眼,因为当时是乐扣最新的一道hard,(其实一点不难),但前一天只是想了一下,没有练习码。不过面试官说出考题的时候还是很激动的,感觉比较胸有成竹了吧。
做完后写了三个unit test, 白哥看了时间,还有10多分钟,他让我写了两个javascript里的call back function 给他看一下,问了一下我平时遇到bug怎么debug之类的就聊完了。.本文原创自1point3acres论坛

周二面完,周天收到hr说结果不错,现在正在team match.

谢谢大家,求大米哟。祝大家好运。
我有自己总结的按知识点总结一个文档,java写的,如果有需要,可以留下邮箱。


补充内容 (2018-4-17 23:42):. 围观我们@1point 3 acres
第三轮是乐扣伞无就,,不好意思我之前写错了

评分

参与人数 62大米 +225 收起 理由
lx5945 + 5 给你点个赞!
cc.wang + 5 给你点个赞!
sunny喵 + 1 很有用的信息!
SerenaJ + 5 给你点个赞!
EETHAN + 3 给你点个赞!
fantasist + 3 很有用的信息!
liu5395 + 3 给你点个赞!
eggface + 3 很有用的信息!
warlord + 3 很有用的信息!
duangduangduang + 3 给你点个赞!
seblsb + 3 很有用的信息!
Molten + 10 给你点个赞!
elephant31 + 3 给你点个赞!
ppcc + 1 帖子十分有用!感谢楼主!
kebugcheck + 3 给你点个赞!

查看全部评分


上一篇:阿里北美面试
下一篇:苹果QA onsite

本帖被以下淘专辑推荐:

我的人缘0
alanlxl 发表于 2018-4-20 14:02:38 | 显示全部楼层
本楼: 【顶】   100% (1)
 
 
0% (0)   【踩】
全局: 顶  96% (28)
 
 
3% (1)  踩
凯伦小龙虾 发表于 2018-4-17 22:44
就是说每次出来一个char,我都会从root开始找看有没有符合,如果符合的话,我就把当前这个trienode指针ap ...

这个题如果把词典的word逆序后建Trie树,再用一个vector存最近遇到的max_length_of_word_in_dict个char,每次来一个char就逆序构造string到Trie中查找,就可以避免存多个TrieNode*的情况. visit 1point3acres for more.
因为你存TrieNode*至多也要存max_length_of_word_in_dict个,所以空间复杂度没区别。
回复

使用道具 举报

我的人缘0
markpen 发表于 2018-4-18 11:55:34 | 显示全部楼层
本楼: 【顶】   100% (1)
 
 
0% (0)   【踩】
全局: 顶  92% (13)
 
 
7% (1)  踩
凯伦小龙虾 发表于 2018-4-18 03:17
是的。面试官当时只是说保证rate不被打破,而且不能存之前的信息,所以我当时就有点懵,不清楚怎么做可以 ...

看了最近的面经,我觉得面试官是想要设计一个类似Rate Limiter 的东西,true 表示接收, false 表示拒绝。这样想的话,楼主的做法似乎没有什么问题。
回复

使用道具 举报

我的人缘0
 楼主| 凯伦小龙虾 发表于 2018-4-18 03:17:24 | 显示全部楼层
本楼: 【顶】   100% (1)
 
 
0% (0)   【踩】
全局: 顶  100% (75)
 
 
0% (0)  踩
markpen 发表于 2018-4-18 03:12. 1point 3acres 论坛
我觉得这题应该需要query 在每秒内的分布情况。楼主似乎假设了query在一秒内是均匀分布的。否则的话,有 ...

. more info on 1point3acres是的。面试官当时只是说保证rate不被打破,而且不能存之前的信息,所以我当时就有点懵,不清楚怎么做可以解决你提的这个问题哈,有什么好的想法么,求指导
回复

使用道具 举报

我的人缘0
markpen 发表于 2018-4-18 03:12:29 | 显示全部楼层
本楼: 【顶】   100% (1)
 
 
0% (0)   【踩】
全局: 顶  92% (13)
 
 
7% (1)  踩
凯伦小龙虾 发表于 2018-4-18 02:06
是的,我提出说我可以index 所有query然后random n个,但面试官说好像不能存,而且最好不要有延迟。如果 ...

我觉得这题应该需要query 在每秒内的分布情况。楼主似乎假设了query在一秒内是均匀分布的。否则的话,有个极端情况就是1000个query都在前0.5秒内,剩下的0.5秒没有query。如果我没有理解错的话,按楼主1/n秒产生一个true的算法,只能产生0.5n个true。

21.000+ students read the Road to learn React. The course weaves all the opinionated roadmaps into one roadmap to master React. It gives you all the fundamentals in React. You will build a Hacker News App along the way.

回复

使用道具 举报

我的人缘0
 楼主| 凯伦小龙虾 发表于 2018-4-17 22:44:16 | 显示全部楼层
本楼: 【顶】   100% (1)
 
 
0% (0)   【踩】
全局: 顶  100% (75)
 
 
0% (0)  踩
zyy6799 发表于 2018-4-17 22:35
请问楼主第四题的字典树怎么做的,指针的意思是指每次拿到一个符合条件的char,把这些指针全部存下来?然后 ...
. 1point3acres
就是说每次出来一个char,我都会从root开始找看有没有符合,如果符合的话,我就把当前这个trienode指针append 到一个list里; 同时我会loop 整个list, 看我之前的那些指针所在的trienode能不能继续往下走,如果可以我update它们,如果不可以我就把它从list里remove
比如abc, bc,   然后我的char stream 出来是 a, b, c.
出来a的时候 我把a 存在list 里 [a],   来源一亩.三分地论坛.
出来b的时候,我发现之前的a 也可以被update, 同时b 也是root 里的char, 就存[a ->b,  b]
出来c, 我同样update list 里的每一个 [a->b->c, b->c], 这样就可以打印了
回复

使用道具 举报

我的人缘0
alyssum14 发表于 2018-4-17 21:58:29 | 显示全部楼层
本楼: 【顶】   0% (0)
 
 
0% (0)   【踩】
全局: 顶  98% (54)
 
 
1% (1)  踩
恭喜楼主,能不能分享下文档呢?邮箱changshi3333@gmail.com,万分感谢~
回复

使用道具 举报

我的人缘0
Ramily 发表于 2018-4-17 21:59:22 | 显示全部楼层
本楼: 【顶】   0% (0)
 
 
0% (0)   【踩】
全局: 顶  100% (44)
 
 
0% (0)  踩
感谢楼主!写的好详细! 可以发我一分文档嘛xfxchun@gmail.com 十分感谢!

With React+D3v4 you'll learn the basics of building fast data visualization components in about an hour.

回复

使用道具 举报

我的人缘0
wtcupup 发表于 2018-4-17 22:27:11 | 显示全部楼层
本楼: 【顶】   0% (0)
 
 
0% (0)   【踩】
全局: 顶  62% (342)
 
 
37% (209)  踩
万分感谢 ! 727229512@qq.com
回复

使用道具 举报

我的人缘0
Tir 发表于 2018-4-17 22:34:38 | 显示全部楼层
本楼: 【顶】   0% (0)
 
 
0% (0)   【踩】
全局: 顶  100% (1)
 
 
0% (0)  踩
楼主写的好详细!求一份总结,630415789@qq.com 感谢!
回复

使用道具 举报

我的人缘0
zyy6799 发表于 2018-4-17 22:35:08 | 显示全部楼层
本楼: 【顶】   0% (0)
 
 
0% (0)   【踩】
全局: 顶  96% (25)
 
 
3% (1)  踩
请问楼主第四题的字典树怎么做的,指针的意思是指每次拿到一个符合条件的char,把这些指针全部存下来?然后下次碰到以这个指针开头的char然后开始找?

Learn React.js, Redux & Immutable.js while building a weather app

回复

使用道具 举报

我的人缘0
blairmn123 发表于 2018-4-17 22:40:34 | 显示全部楼层
本楼: 【顶】   0% (0)
 
 
0% (0)   【踩】
全局: 顶  90% (10)
 
 
9% (1)  踩
谢谢楼主分享,邮箱: zsy1018@live.cn
回复

使用道具 举报

我的人缘0
rpg99699016 发表于 2018-4-17 22:40:39 | 显示全部楼层
本楼: 【顶】   0% (0)
 
 
0% (0)   【踩】
全局: 顶  100% (11)
 
 
0% (0)  踩
恭喜lz,邮箱cooperwang1994@gmail.com,求一份总结,多谢!
回复

使用道具 举报

我的人缘1
idatascience 发表于 2018-4-17 23:18:34 | 显示全部楼层
本楼: 【顶】   0% (0)
 
 
0% (0)   【踩】
全局: 顶  84% (250)
 
 
15% (46)  踩
女神,你已经工作了,都不用面System Design么?是在MTV site面的嘛?
回复

使用道具 举报

我的人缘0
cinderellafly41 发表于 2018-4-17 23:20:23 | 显示全部楼层
本楼: 【顶】   0% (0)
 
 
0% (0)   【踩】
全局: 顶  0% (0)
 
 
0% (0)  踩
恭喜lz! 求一份文档,邮箱525221647@qq.com. 1point3acres

Trie那道题也有人贴过,还有一个方法是建后缀树,就不用存指针了,但是每次有个新的char都要从头match一遍
回复

使用道具 举报

我的人缘0
 楼主| 凯伦小龙虾 发表于 2018-4-17 23:20:51 | 显示全部楼层
本楼: 【顶】   0% (0)
 
 
0% (0)   【踩】
全局: 顶  100% (75)
 
 
0% (0)  踩
idatascience 发表于 2018-4-17 23:18
女神,你已经工作了,都不用面System Design么?是在MTV site面的嘛?

我没有面system design, 我在纽约面的。
回复

使用道具 举报

我的人缘1
idatascience 发表于 2018-4-17 23:26:53 | 显示全部楼层
本楼: 【顶】   0% (0)
 
 
0% (0)   【踩】
全局: 顶  84% (250)
 
 
15% (46)  踩
2416363120@qq.com 也求一份~多谢美女~
回复

使用道具 举报

我的人缘0
hyliu0000 发表于 2018-4-17 23:34:43 | 显示全部楼层
本楼: 【顶】   0% (0)
 
 
0% (0)   【踩】
全局: 顶  98% (78)
 
 
1% (1)  踩
凯伦小龙虾 发表于 2018-4-17 22:44
就是说每次出来一个char,我都会从root开始找看有没有符合,如果符合的话,我就把当前这个trienode指针ap ...

挺好的做法,如果想节省空间的话还可以把反向存string到trie里面。

评分

参与人数 1大米 +3 收起 理由
hybangshou01 + 3 很有用的信息!

查看全部评分

回复

使用道具 举报

我的人缘0
axlvlv 发表于 2018-4-17 23:37:05 | 显示全部楼层
本楼: 【顶】   0% (0)
 
 
0% (0)   【踩】
全局: 顶  100% (1)
 
 
0% (0)  踩
334532249@qq.com 谢女神!
回复

使用道具 举报

我的人缘0
hyliu0000 发表于 2018-4-17 23:37:30 | 显示全部楼层
本楼: 【顶】   0% (0)
 
 
0% (0)   【踩】
全局: 顶  98% (78)
 
 
1% (1)  踩
楼主, 所以第一题是一个api设计题? 字典可以提前处理,然后查找api会被call很多次? 第三轮乐扣伞就无是395?但是那道题有api query isAllowed吗? 楼主答得真好! 恭喜

评分

参与人数 2大米 +8 收起 理由
hybangshou01 + 3 很有用的信息!
krizalio001 + 5 给你点个赞!

查看全部评分

回复

使用道具 举报

我的人缘0
phoebezcy 发表于 2018-4-17 23:37:51 | 显示全部楼层
本楼: 【顶】   0% (0)
 
 
0% (0)   【踩】
全局: 顶  100% (8)
 
 
0% (0)  踩
谢谢姑娘,求文档zcy0403@bu.edu
回复

使用道具 举报

我的人缘1
idatascience 发表于 2018-4-17 23:37:56 | 显示全部楼层
本楼: 【顶】   0% (0)
 
 
0% (0)   【踩】
全局: 顶  84% (250)
 
 
15% (46)  踩
凯伦小龙虾 发表于 2018-4-17 23:20 来源一亩.三分地论坛.
我没有面system design, 我在纽约面的。

恭喜~想请问一下你面试的时候人力就说了不面system design的么?女神,你是朋友内推的还是自己投的呀?
回复

使用道具 举报

我的人缘0
Carinaljr 发表于 2018-4-17 23:40:12 | 显示全部楼层
本楼: 【顶】   0% (0)
 
 
0% (0)   【踩】
全局: 顶  0% (0)
 
 
0% (0)  踩
恭喜楼主!祝入职后一切顺利寻求一份文档,感谢!jli762@wisc.edu
回复

使用道具 举报

我的人缘0
 楼主| 凯伦小龙虾 发表于 2018-4-17 23:41:38 | 显示全部楼层
本楼: 【顶】   0% (0)
 
 
0% (0)   【踩】
全局: 顶  100% (75)
 
 
0% (0)  踩
hyliu0000 发表于 2018-4-17 23:37
楼主, 所以第一题是一个api设计题? 字典可以提前处理,然后查找api会被call很多次? 第三轮乐扣伞就无是3 ...

那道题好像是三五久,不好意思,我写错了。。。。第一题可以想象成一个设计题吧,可以和面试官交流,因为优化的方法很多,可以自己提出很多假设哈
回复

使用道具 举报

游客
请先登录

本版积分规则

提醒:发帖可以选择内容隐藏,部分板块支持匿名发帖。请认真读完以下全部说明:

■隐藏内容方法: [hide=200]你想要隐藏的内容比如面经[/hide]
■意思是:用户积分低于200则看不到被隐藏的内容
■可以自行设置积分值,不建议太高(200以上太多人看不到),也不建议太低(那就没必要隐藏了)
■建议只隐藏关键内容,比如具体的面试题目、涉及隐私的信息,大部分内容没必要隐藏。
■微信/QQ/电子邮件等,为防止将来被骚扰甚至人肉,以论坛私信方式发给对方最安全。
■匿名发帖的板块和方法:http://www.1point3acres.com/bbs/thread-405991-1-1.html

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

GMT+8, 2018-8-22 05:57

Powered by Discuz! X3

© 2001-2013 Comsenz Inc. Design By HUXTeam

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