San Jose各个房价 <1.5m 区域买房总结

一亩三分地论坛

 找回密码
 Sign Up 注册获取更多干货
码农求职神器Triplebyte:
不用海投
内推多家公司面试
坐标湾区
Games Startup
招聘游戏开发工程师
游戏初创公司招聘工程师、UIUX Designer和游戏策划
把贵司招聘信息放这里
查看: 11848|回复: 316
收起左侧

google 2018四月onsite面筋

    [复制链接] |试试Instant~ |关注本帖
凯伦小龙虾 发表于 2018-4-17 21:48:50 | 显示全部楼层 |阅读模式

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, 同时也是最短。 . Waral 博客有更多文章,

follow-up: 多种方法优化这道题的方法, 楼主先排序 (要求写出查找的平均时间复杂度),
楼主还答了可以把words 存成 s: study, stone, school, star, stor; t : star, stone, store..... 这样的map, 好处是我们查找的时候只需要看target里出现过的char所对应的词,然后找并集,在目标字符串很小的情况下有可能会省很多时间。. Waral 博客有更多文章,


2.白姐姐 . 牛人云集,一亩三分地
用preorder和postorder建树,这道题出来时我说好像没有inorder是做不出来的,然后聚了个例子,面试管说那就假设总是有left subtree的,然后楼主用recursion写了。完了分析时间复杂度,问怎么优化(hashmap 存一边postorder里的val 对应的Index).本文原创自1point3acres论坛

3. 白大哥
类似乐扣伞就无 但不一样的是这个api不能存query, 不负责接收query,不负责发送,只是会每1秒让n个isAllowed() 返回true. 这题我当场有点懵,我就说了那就写一个count和clear, 然后每秒清零count。但这样做会造成每秒前10个可以,会形成每秒一个峰值。面试官问可不可以有一个更平均的分布,我说那就每1/n秒返回一个true, 然后清零... (我知道这样做很笨,但当场没有想到更好的方法。面试官一直强调说不能存任何和query有关的东西(除了计数),只负责yes or no然后保证这个rate的正确性),写完码答了怎么unit test
.本文原创自1point3acres论坛
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之类的就聊完了。

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

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


补充内容 (2018-4-17 23:42):. visit 1point3acres for more.
第三轮是乐扣伞无就,,不好意思我之前写错了

评分

56

查看全部评分

本帖被以下淘专辑推荐:

markpen 发表于 2018-4-18 03:12:29 | 显示全部楼层
凯伦小龙虾 发表于 2018-4-18 02:06
是的,我提出说我可以index 所有query然后random n个,但面试官说好像不能存,而且最好不要有延迟。如果 ...

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

使用道具 举报

 楼主| 凯伦小龙虾 发表于 2018-4-18 03:17:24 | 显示全部楼层
markpen 发表于 2018-4-18 03:12
. visit 1point3acres for more.我觉得这题应该需要query 在每秒内的分布情况。楼主似乎假设了query在一秒内是均匀分布的。否则的话,有 ...

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

使用道具 举报

 楼主| 凯伦小龙虾 发表于 2018-4-17 22:44:16 | 显示全部楼层
zyy6799 发表于 2018-4-17 22:35
请问楼主第四题的字典树怎么做的,指针的意思是指每次拿到一个符合条件的char,把这些指针全部存下来?然后 ...

就是说每次出来一个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], 这样就可以打印了
回复 支持 1 反对 0

使用道具 举报

alanlxl 发表于 2018-4-20 14:02:38 | 显示全部楼层
凯伦小龙虾 发表于 2018-4-17 22:44. from: 1point3acres
就是说每次出来一个char,我都会从root开始找看有没有符合,如果符合的话,我就把当前这个trienode指针ap ...

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

使用道具 举报

markpen 发表于 2018-4-18 11:55:34 | 显示全部楼层
凯伦小龙虾 发表于 2018-4-18 03:17
是的。面试官当时只是说保证rate不被打破,而且不能存之前的信息,所以我当时就有点懵,不清楚怎么做可以 ...

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

使用道具 举报

alyssum14 发表于 2018-4-17 21:58:29 | 显示全部楼层
恭喜楼主,能不能分享下文档呢?邮箱changshi3333@gmail.com,万分感谢~
回复 支持 反对

使用道具 举报

Ramily 发表于 2018-4-17 21:59:22 | 显示全部楼层
感谢楼主!写的好详细! 可以发我一分文档嘛xfxchun@gmail.com 十分感谢!
Mobile Apps Category (English)728x90
回复 支持 反对

使用道具 举报

wtcupup 发表于 2018-4-17 22:27:11 | 显示全部楼层
万分感谢 ! 727229512@qq.com
回复 支持 反对

使用道具 举报

Tir 发表于 2018-4-17 22:34:38 | 显示全部楼层
楼主写的好详细!求一份总结,630415789@qq.com 感谢!
回复 支持 反对

使用道具 举报

zyy6799 发表于 2018-4-17 22:35:08 | 显示全部楼层
请问楼主第四题的字典树怎么做的,指针的意思是指每次拿到一个符合条件的char,把这些指针全部存下来?然后下次碰到以这个指针开头的char然后开始找?
回复 支持 反对

使用道具 举报

blairmn123 发表于 2018-4-17 22:40:34 | 显示全部楼层
谢谢楼主分享,邮箱: zsy1018@live.cn
回复 支持 反对

使用道具 举报

rpg99699016 发表于 2018-4-17 22:40:39 | 显示全部楼层
恭喜lz,邮箱cooperwang1994@gmail.com,求一份总结,多谢!
回复 支持 反对

使用道具 举报

idatascience 发表于 2018-4-17 23:18:34 | 显示全部楼层
女神,你已经工作了,都不用面System Design么?是在MTV site面的嘛?
回复 支持 反对

使用道具 举报

cinderellafly41 发表于 2018-4-17 23:20:23 | 显示全部楼层
恭喜lz! 求一份文档,邮箱525221647@qq.com

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

使用道具 举报

 楼主| 凯伦小龙虾 发表于 2018-4-17 23:20:51 | 显示全部楼层
idatascience 发表于 2018-4-17 23:18
女神,你已经工作了,都不用面System Design么?是在MTV site面的嘛?

我没有面system design, 我在纽约面的。
回复 支持 反对

使用道具 举报

idatascience 发表于 2018-4-17 23:26:53 | 显示全部楼层
2416363120@qq.com 也求一份~多谢美女~
回复 支持 反对

使用道具 举报

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

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

评分

1

查看全部评分

回复 支持 反对

使用道具 举报

axlvlv 发表于 2018-4-17 23:37:05 | 显示全部楼层
334532249@qq.com 谢女神!
回复 支持 反对

使用道具 举报

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

评分

2

查看全部评分

回复 支持 反对

使用道具 举报

phoebezcy 发表于 2018-4-17 23:37:51 | 显示全部楼层
谢谢姑娘,求文档zcy0403@bu.edu
回复 支持 反对

使用道具 举报

idatascience 发表于 2018-4-17 23:37:56 | 显示全部楼层
凯伦小龙虾 发表于 2018-4-17 23:20-google 1point3acres
我没有面system design, 我在纽约面的。

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

使用道具 举报

Carinaljr 发表于 2018-4-17 23:40:12 | 显示全部楼层
恭喜楼主!祝入职后一切顺利寻求一份文档,感谢!jli762@wisc.edu
回复 支持 反对

使用道具 举报

 楼主| 凯伦小龙虾 发表于 2018-4-17 23:41:38 | 显示全部楼层
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

关闭

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

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

custom counter

GMT+8, 2018-5-26 20:38

Powered by Discuz! X3

© 2001-2013 Comsenz Inc. Design By HUXTeam

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