《数据科学面试40+真题讲解》,K神本年度最后一次开课


一亩三分地论坛

 找回密码
 Sign Up 注册获取更多干货
码农求职神器Triplebyte:
不用海投,内推你去多家公司面试
Airbnb 数据科学职位
in analytics and inference
天天打游戏、照样领工资,
你要不要来?
把贵司招聘信息放这里
查看: 1646|回复: 25
收起左侧

Google Onsite 面试经验

[复制链接] |试试Instant~ |关注本帖
danshuiweiwen 发表于 2017-11-14 10:36:20 | 显示全部楼层 |阅读模式

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

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

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

x
11/13 完成了google onsite interview
1.国人:
-google 1point3acresa.输入常数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). 1point 3acres 璁哄潧
答: One for loop + HashMap<String, Integer>, 每进来一个word单独处理一下就好了
印度人曰: HashMap 太浪费空间了,提升一下
.1point3acres缃
答: 不要任何数据结构了, two for loop生比吧
印度人曰: 太浪费时间了,中和一下吧

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

心理答: f*** off, stupid
印度人曰: 再提升一下效率
. 鐗涗汉浜戦泦,涓浜╀笁鍒嗗湴
答: 还是生比, 用一个int[256]把以处理完的存起来
时间到,没空写fellow up的代码了. 鐗涗汉浜戦泦,涓浜╀笁鍒嗗湴
. visit 1point3acres.com for more.
3.国人: Predict Search Term - Trie problem, 返回List<String>, 要求用线性的时间完成, 类似于leetcode Word Search 2.鐣欏璁哄潧-涓浜-涓夊垎鍦
fellow up: time/space complexity analysis. 1point 3acres 璁哄潧
fellow up: 每个单词有权重,权重大的在前面. from: 1point3acres.com/bbs
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, 这样反倒给自己挖了坑, 希望能集一点人品吧

评分

6

查看全部评分

本帖被以下淘专辑推荐:

丑猪宝 发表于 2017-11-15 14:30:03 | 显示全部楼层
真是很怕遇到硬度人,这样不行,那样也不行,再加上黑着个脸,什么心情没有了
回复 支持 1 反对 0

使用道具 举报

yuyuyu0905 发表于 2017-11-14 10:51:32 | 显示全部楼层
楼主能说一下第四题怎么constant时间复杂度嘛?

谢谢~
回复 支持 反对

使用道具 举报

freegyp 发表于 2017-11-14 11:13:59 | 显示全部楼层
第二题意思是不是两个string a、b,不管在a中出现的字母在b中出现了几次,只要都出现了而且没有其他的字母就是一个pair了?还有string里面除了会出现大写字母还会出现其他字符吗?
回复 支持 反对

使用道具 举报

 楼主| danshuiweiwen 发表于 2017-11-14 11:26:03 | 显示全部楼层
yuyuyu0905 发表于 2017-11-14 10:51
楼主能说一下第四题怎么constant时间复杂度嘛?

谢谢~

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

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

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

union find本身使用数组实现的,我觉得这个也是可以用数组的,然后另外一个数组用来保存value就可以了. visit 1point3acres.com for more.

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

使用道具 举报

 楼主| danshuiweiwen 发表于 2017-11-14 11:27:30 | 显示全部楼层
freegyp 发表于 2017-11-14 11:13 鏉ユ簮涓浜.涓夊垎鍦拌鍧.
第二题意思是不是两个string a、b,不管在a中出现的字母在b中出现了几次,只要都出现了而且没有其他的字母 ...

是的,字符集是256的ASCii
其他的不用纠结,这个估计是那个烙印现场想的,因为我觉得他想要问的也不是什么很复杂的算法,只是一直让你比较tradeoff. 涓浜-涓夊垎-鍦帮紝鐙鍙戝竷
回复 支持 反对

使用道具 举报

hychin 发表于 2017-11-14 11:39:55 | 显示全部楼层
第二题也用trie保存出现过的节点的signature就好了 signature就是类似于 AABBC 都转成ABC这种
绝对比hashmap省很多空间
回复 支持 反对

使用道具 举报

jzl921111 发表于 2017-11-14 14:58:04 | 显示全部楼层
第二题不用hashset 拼接起来用string 就可以了呀
回复 支持 反对

使用道具 举报

weiliango 发表于 2017-11-15 04:00:03 | 显示全部楼层
感觉第二题整个歪掉了。。. Waral 鍗氬鏈夋洿澶氭枃绔,
让我写的话,每一个字符串搞一个check value。用比特运算。刚想起来这个是leetcode原题。
比如 "abc" 搞成 000000...0111
         "abcd" -> 00000000...1111
然后比较一下两个数是否相等就好。
这样空间是n,时间是n*k。k是字符串最大程度。

补充内容 (2017-11-15 04:02):.鐣欏璁哄潧-涓浜-涓夊垎鍦
好吧,时间上少乘了个n。。
回复 支持 反对

使用道具 举报

 楼主| danshuiweiwen 发表于 2017-11-15 10:47:49 | 显示全部楼层
weiliango 发表于 2017-11-15 04:00. Waral 鍗氬鏈夋洿澶氭枃绔,
感觉第二题整个歪掉了。。
让我写的话,每一个字符串搞一个check value。用比特运算。刚想起来这个是leetc ...

256个字符

评分

1

查看全部评分

回复 支持 反对

使用道具 举报

 楼主| danshuiweiwen 发表于 2017-11-15 11:03:29 | 显示全部楼层
hychin 发表于 2017-11-14 11:39
第二题也用trie保存出现过的节点的signature就好了 signature就是类似于 AABBC 都转成ABC这种. visit 1point3acres.com for more.
绝对比hashm ...
. 1point3acres.com/bbs
可能是trie,   他最后也没有用什么最好,我当时没往trie的方向想
回复 支持 反对

使用道具 举报

691469063 发表于 2017-11-15 13:41:21 | 显示全部楼层
一亩三分地严打"顶""好贴""收藏了"之类的垃圾回复帖!被警告三次,系统会自动封杀ID!

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

使用道具 举报

691469063 发表于 2017-11-15 13:42:40 | 显示全部楼层
可不可以用prime number编码然后算gcd,不是1就是有common
回复 支持 反对

使用道具 举报

nsbdsxh 发表于 2017-11-15 15:13:40 | 显示全部楼层
感觉第三轮trie树里面是不能加权重的吧,比如origin和oath权重差别很大但都要走o,求指教
回复 支持 反对

使用道具 举报

 楼主| danshuiweiwen 发表于 2017-11-16 00:58:24 | 显示全部楼层
691469063 发表于 2017-11-15 13:42.1point3acres缃
可不可以用prime number编码然后算gcd,不是1就是有common

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

使用道具 举报

dawskiper 发表于 2017-11-17 15:57:39 | 显示全部楼层
nsbdsxh 发表于 2017-11-15 15:13
. 鐣欏鐢宠璁哄潧-涓浜╀笁鍒嗗湴感觉第三轮trie树里面是不能加权重的吧,比如origin和oath权重差别很大但都要走o,求指教

不会有问题啊,如果都要走o,那么可能会在下一个字母再分开,就没有重合了.或者不再分开,两个都是结果,一起返回..鏈枃鍘熷垱鑷1point3acres璁哄潧
而且,这里的权重应该说的是单词的权重,节点的权重只是路过节点的单词中权重最大的权重.
回复 支持 反对

使用道具 举报

siranjoy119 发表于 5 天前 | 显示全部楼层
请问下Lz说的fellow up是follow up的意思还是什么暗语? 感觉用了这么多次也不像typo啊。。
回复 支持 反对

使用道具 举报

samuel1989 发表于 5 天前 | 显示全部楼层
可否详细解释下第四题 constant的解法
回复 支持 反对

使用道具 举报

ws775901 发表于 4 天前 | 显示全部楼层
楼主,第二题最后一个follow up你说的生比,不是不需要数据结构了么,为什么还需要一个int[256]? (反正都是o(n^2))
回复 支持 反对

使用道具 举报

本版积分规则

关闭

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

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

custom counter

GMT+8, 2017-11-25 02:37

Powered by Discuz! X3

© 2001-2013 Comsenz Inc. Design By HUXTeam

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