工业界资深数据科学家现场教你修改求职简历
小K现场教你修改求职简历

一亩三分地论坛

 找回密码
 Sign Up 注册获取更多干货
码农求职神器Triplebyte:
不用海投
内推多家公司面试
坐标湾区
DreamCraft创始团队
招聘游戏开发工程师
游戏初创公司招聘工程师、UIUX Designer和游戏策划
高效直聘+内推,70%面试率
AI帮你免费完善简历
直击全美十万个科技职位
把贵司招聘信息放这里
查看: 5502|回复: 51
收起左侧

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)
答: One for loop + HashMap<String, Integer>, 每进来一个word单独处理一下就好了
印度人曰: HashMap 太浪费空间了,提升一下

答: 不要任何数据结构了, two for loop生比吧
印度人曰: 太浪费时间了,中和一下吧
. 1point3acres
答: 用个set吧,只要set里面有了,就跳出loop,和前面的比一下,找到了就返回, 时间是linear的
印度人曰: what are you talking about , I didnt get?

心理答: f*** off, stupid
印度人曰: 再提升一下效率. 围观我们@1point 3 acres

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

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

4.ABC小哥: LeetCode 399
fellow up: 如何只用线性的空间复杂度,而时间复杂度任然是constant: 答: 所有的点连到一个中心点上,这个点相当于一个transit, 和压缩过路径的union find有点像
. Waral 博客有更多文章,
面试官都挺和善的,印度人那一轮答得不是很好,感觉他心理有一个预设的方案,不是他那个就一定不行,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% (261)
 
 
18% (60)  踩
第二题也用trie保存出现过的节点的signature就好了 signature就是类似于 AABBC 都转成ABC这种. Waral 博客有更多文章,
绝对比hashmap省很多空间
回复

使用道具 举报

我的人缘0
yuyuyu0905 发表于 2017-11-14 10:51:32 | 显示全部楼层
本楼: 【顶】   0% (0)
 
 
0% (0)   【踩】
全局: 顶  89% (34)
 
 
10% (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时间复杂度嘛?

谢谢~

他没有告诉我具体怎么实现,我们讨论了一下理论就时间到了

我原来这个题是用hashmap<String, Hashmap<String, Double>>来构建图的

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

.本文原创自1point3acres论坛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中出现了几次,只要都出现了而且没有其他的字母 ...
. 围观我们@1point 3 acres
是的,字符集是256的ASCii. more info on 1point3acres
其他的不用纠结,这个估计是那个烙印现场想的,因为我觉得他想要问的也不是什么很复杂的算法,只是一直让你比较tradeoff. from: 1point3acres
回复

使用道具 举报

我的人缘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)   【踩】
全局: 顶  87% (159)
 
 
12% (22)  踩
感觉第二题整个歪掉了。。
让我写的话,每一个字符串搞一个check value。用比特运算。刚想起来这个是leetcode原题。. more info on 1point3acres
比如 "abc" 搞成 000000...0111. more info on 1point3acres
         "abcd" -> 00000000...1111
然后比较一下两个数是否相等就好。
这样空间是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
感觉第二题整个歪掉了。。
让我写的话,每一个字符串搞一个check value。用比特运算。刚想起来这个是leetc ...
. 一亩-三分-地,独家发布
256个字符

评分

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

查看全部评分

回复

使用道具 举报

游客
请先登录

本版积分规则

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

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

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

GMT+8, 2018-10-22 08:12

Powered by Discuz! X3

© 2001-2013 Comsenz Inc. Design By HUXTeam

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