Airbnb 2018年春季E6 package

一亩三分地论坛

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

最近看过此主题的会员

E轮2.5亿美元融资
K12教育独角兽一起作业
北京-诚聘人工智能/教育/大数据岗
码农求职神器Triplebyte:
不用海投
内推多家公司面试
坐标湾区
Games Startup
招聘游戏开发工程师
游戏初创公司招聘工程师、UIUX Designer和游戏策划
查看: 4535|回复: 50
收起左侧

Google Onsite 面试经验

[复制链接] |试试Instant~ |关注本帖
我的人缘0
danshuiweiwen 发表于 2017-11-14 10:36:20 | 显示全部楼层 |阅读模式
本楼: 【顶】   100% (1)
 
 
0% (0)   【踩】
全局: 顶  100% (24)
 
 
0% (0)  踩

2017(10-12月) 码农类General 硕士 全职@Google - 内推 - Onsite  | Other | fresh grad应届毕业生

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

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

x
11/13 完成了google onsite interview
1.国人:
a.输入常数N, 生成1 - 2 ^ N, 然后头尾两两合并,直到最后只有一个数组,暴力解就可以了
b.find the only one peek in integer array, 答: binary search

2.印度人: List Of String, find out the first pair with common unique characters (ABCCC和CAB就满足条件,应为他们都有ABC). more info on 1point3acres
答: One for loop + HashMap<String, Integer>, 每进来一个word单独处理一下就好了
印度人曰: HashMap 太浪费空间了,提升一下
.本文原创自1point3acres论坛
答: 不要任何数据结构了, two for loop生比吧
印度人曰: 太浪费时间了,中和一下吧

答: 用个set吧,只要set里面有了,就跳出loop,和前面的比一下,找到了就返回, 时间是linear的
印度人曰: what are you talking about , I didnt get?. 围观我们@1point 3 acres

心理答: f*** off, stupid
印度人曰: 再提升一下效率

答: 还是生比, 用一个int[256]把以处理完的存起来
时间到,没空写fellow up的代码了

3.国人: Predict Search Term - Trie problem, 返回List<String>, 要求用线性的时间完成, 类似于leetcode Word Search 2
. Waral 博客有更多文章,fellow up: time/space complexity analysis. 1point 3acres 论坛
fellow up: 每个单词有权重,权重大的在前面
fellow up: 尽可能减少排序的时间,答: 建树的时候每个节点放一个PriorityQueue
fellow up: 如果权重可以更新的话,怎样用logN的时间完成,答: 实现自定义的priorityQueue, 可以randomAccess任意节点

4.ABC小哥: LeetCode 399
fellow up: 如何只用线性的空间复杂度,而时间复杂度任然是constant: 答: 所有的点连到一个中心点上,这个点相当于一个transit, 和压缩过路径的union find有点像

面试官都挺和善的,印度人那一轮答得不是很好,感觉他心理有一个预设的方案,不是他那个就一定不行,fellow up答的不好。感觉fellow up挺重要的,代码写的太快,面试官为了hold住面试就必须要一直想fellow up, 这样反倒给自己挖了坑, 希望能集一点人品吧

评分

参与人数 10大米 +36 收起 理由
Effiel + 3 很有用的信息!
5919393 + 3 谢谢分享!给你点个赞!
HoraceWang + 5 楼主长的太帅了
kjkwang123 + 5 感谢信息!
eval + 5 很有用的信息!
17scientist + 1 &lt;font style=&quot;vertical-align: inh
famillerose + 3 赞详细
nsbdsxh + 5 很有用的信息!
reliveinfire + 3 很有用的信息!
crazymarbury + 3 +++

查看全部评分


上一篇:2小时前的脸家挂经
下一篇:狗狗面经总结贴

本帖被以下淘专辑推荐:

我的人缘0
丑猪宝 发表于 2017-11-15 14:30:03 | 显示全部楼层
本楼: 【顶】   100% (4)
 
 
0% (0)   【踩】
全局: 顶  100% (32)
 
 
0% (0)  踩
真是很怕遇到硬度人,这样不行,那样也不行,再加上黑着个脸,什么心情没有了
回复

使用道具 举报

我的人缘0
hychin 发表于 2017-11-14 11:39:55 | 显示全部楼层
本楼: 【顶】   100% (1)
 
 
0% (0)   【踩】
全局: 顶  81% (236)
 
 
18% (53)  踩
第二题也用trie保存出现过的节点的signature就好了 signature就是类似于 AABBC 都转成ABC这种
绝对比hashmap省很多空间
回复

使用道具 举报

我的人缘0
yuyuyu0905 发表于 2017-11-14 10:51:32 | 显示全部楼层
本楼: 【顶】   0% (0)
 
 
0% (0)   【踩】
全局: 顶  88% (32)
 
 
11% (4)  踩
楼主能说一下第四题怎么constant时间复杂度嘛?

谢谢~
回复

使用道具 举报

我的人缘0
freegyp 发表于 2017-11-14 11:13:59 | 显示全部楼层
本楼: 【顶】   0% (0)
 
 
0% (0)   【踩】
全局: 顶  100% (2)
 
 
0% (0)  踩
第二题意思是不是两个string a、b,不管在a中出现的字母在b中出现了几次,只要都出现了而且没有其他的字母就是一个pair了?还有string里面除了会出现大写字母还会出现其他字符吗?
回复

使用道具 举报

我的人缘0
 楼主| danshuiweiwen 发表于 2017-11-14 11:26:03 | 显示全部楼层
本楼: 【顶】   0% (0)
 
 
0% (0)   【踩】
全局: 顶  100% (24)
 
 
0% (0)  踩
yuyuyu0905 发表于 2017-11-14 10:51
楼主能说一下第四题怎么constant时间复杂度嘛?

谢谢~

他没有告诉我具体怎么实现,我们讨论了一下理论就时间到了. 围观我们@1point 3 acres

我原来这个题是用hashmap<String, Hashmap<String, Double>>来构建图的. 1point 3acres 论坛

如果用union find的话,可能需要一个列表来储存所有union set的根节点

union find本身使用数组实现的,我觉得这个也是可以用数组的,然后另外一个数组用来保存value就可以了. 一亩-三分-地,独家发布

我仔细想了一下,其实搜索的时间按照他的方法是约等于constant,但是有可能会有很多union set,这样就有很多root node,不是严格的constant
回复

使用道具 举报

我的人缘0
 楼主| danshuiweiwen 发表于 2017-11-14 11:27:30 | 显示全部楼层
本楼: 【顶】   0% (0)
 
 
0% (0)   【踩】
全局: 顶  100% (24)
 
 
0% (0)  踩
freegyp 发表于 2017-11-14 11:13
第二题意思是不是两个string a、b,不管在a中出现的字母在b中出现了几次,只要都出现了而且没有其他的字母 ...
.本文原创自1point3acres论坛
是的,字符集是256的ASCii
其他的不用纠结,这个估计是那个烙印现场想的,因为我觉得他想要问的也不是什么很复杂的算法,只是一直让你比较tradeoff-google 1point3acres
Mobile Apps Category (English)728x90
回复

使用道具 举报

我的人缘0
jzl921111 发表于 2017-11-14 14:58:04 | 显示全部楼层
本楼: 【顶】   0% (0)
 
 
0% (0)   【踩】
全局: 顶  87% (7)
 
 
12% (1)  踩
第二题不用hashset 拼接起来用string 就可以了呀
回复

使用道具 举报

我的人缘0
weiliango 发表于 2017-11-15 04:00:03 | 显示全部楼层
本楼: 【顶】   0% (0)
 
 
0% (0)   【踩】
全局: 顶  81% (93)
 
 
18% (21)  踩
感觉第二题整个歪掉了。。
让我写的话,每一个字符串搞一个check value。用比特运算。刚想起来这个是leetcode原题。. 1point 3acres 论坛
比如 "abc" 搞成 000000...0111
         "abcd" -> 00000000...1111.本文原创自1point3acres论坛
然后比较一下两个数是否相等就好。
这样空间是n,时间是n*k。k是字符串最大程度。

补充内容 (2017-11-15 04:02):
好吧,时间上少乘了个n。。
回复

使用道具 举报

我的人缘0
 楼主| danshuiweiwen 发表于 2017-11-15 10:47:49 | 显示全部楼层
本楼: 【顶】   0% (0)
 
 
0% (0)   【踩】
全局: 顶  100% (24)
 
 
0% (0)  踩
weiliango 发表于 2017-11-15 04:00
感觉第二题整个歪掉了。。
. 1point3acres让我写的话,每一个字符串搞一个check value。用比特运算。刚想起来这个是leetc ...

256个字符

评分

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

查看全部评分

回复

使用道具 举报

我的人缘0
 楼主| danshuiweiwen 发表于 2017-11-15 11:03:29 | 显示全部楼层
本楼: 【顶】   0% (0)
 
 
0% (0)   【踩】
全局: 顶  100% (24)
 
 
0% (0)  踩
hychin 发表于 2017-11-14 11:39
第二题也用trie保存出现过的节点的signature就好了 signature就是类似于 AABBC 都转成ABC这种-google 1point3acres
绝对比hashm ...

可能是trie,   他最后也没有用什么最好,我当时没往trie的方向想
回复

使用道具 举报

我的人缘0
691469063 发表于 2017-11-15 13:41:21 | 显示全部楼层
本楼: 【顶】   0% (0)
 
 
0% (0)   【踩】
全局: 顶  100% (2)
 
 
0% (0)  踩
一亩三分地严打"顶""好贴""收藏了"之类的垃圾回复帖!被警告三次,系统会自动封杀ID!

想支持楼主,请点击帖子下方的"好苗""分享""收藏"键,酌情给楼主加大米(系统不扣你自己的分)。
积分不够看不了帖子,请参考论坛导航里的"帮助","新手提纲"里有攒积分指南
回复

使用道具 举报

我的人缘0
691469063 发表于 2017-11-15 13:42:40 | 显示全部楼层
本楼: 【顶】   0% (0)
 
 
0% (0)   【踩】
全局: 顶  100% (2)
 
 
0% (0)  踩
可不可以用prime number编码然后算gcd,不是1就是有common
回复

使用道具 举报

我的人缘0
nsbdsxh 发表于 2017-11-15 15:13:40 | 显示全部楼层
本楼: 【顶】   0% (0)
 
 
0% (0)   【踩】
全局: 顶  95% (131)
 
 
4% (6)  踩
感觉第三轮trie树里面是不能加权重的吧,比如origin和oath权重差别很大但都要走o,求指教
回复

使用道具 举报

我的人缘0
 楼主| danshuiweiwen 发表于 2017-11-16 00:58:24 | 显示全部楼层
本楼: 【顶】   0% (0)
 
 
0% (0)   【踩】
全局: 顶  100% (24)
 
 
0% (0)  踩
691469063 发表于 2017-11-15 13:42
可不可以用prime number编码然后算gcd,不是1就是有common

不需要这么复杂,个人觉得考点不在这
回复

使用道具 举报

我的人缘0
dawskiper 发表于 2017-11-17 15:57:39 | 显示全部楼层
本楼: 【顶】   0% (0)
 
 
0% (0)   【踩】
全局: 顶  100% (13)
 
 
0% (0)  踩
nsbdsxh 发表于 2017-11-15 15:13. 留学申请论坛-一亩三分地
感觉第三轮trie树里面是不能加权重的吧,比如origin和oath权重差别很大但都要走o,求指教

不会有问题啊,如果都要走o,那么可能会在下一个字母再分开,就没有重合了.或者不再分开,两个都是结果,一起返回.
而且,这里的权重应该说的是单词的权重,节点的权重只是路过节点的单词中权重最大的权重.
回复

使用道具 举报

我的人缘0
siranjoy119 发表于 2017-11-20 05:40:50 | 显示全部楼层
本楼: 【顶】   0% (0)
 
 
0% (0)   【踩】
全局: 顶  93% (76)
 
 
6% (5)  踩
请问下Lz说的fellow up是follow up的意思还是什么暗语? 感觉用了这么多次也不像typo啊。。
回复

使用道具 举报

我的人缘0
samuel1989 发表于 2017-11-20 05:52:30 | 显示全部楼层
本楼: 【顶】   0% (0)
 
 
0% (0)   【踩】
全局: 顶  100% (14)
 
 
0% (0)  踩
可否详细解释下第四题 constant的解法
回复

使用道具 举报

我的人缘0
ws775901 发表于 2017-11-21 17:42:31 | 显示全部楼层
本楼: 【顶】   0% (0)
 
 
0% (0)   【踩】
全局: 顶  44% (252)
 
 
55% (316)  踩
楼主,第二题最后一个follow up你说的生比,不是不需要数据结构了么,为什么还需要一个int[256]? (反正都是o(n^2))
回复

使用道具 举报

游客
请先登录

本版积分规则

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

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

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

custom counter

GMT+8, 2018-7-17 15:57

Powered by Discuz! X3

© 2001-2013 Comsenz Inc. Design By HUXTeam

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