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


一亩三分地论坛

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

狗家一面+加面面经

[复制链接] |试试Instant~ |关注本帖
Pluto 发表于 2016-11-12 04:35:20 | 显示全部楼层 |阅读模式

2016(10-12月) 码农类 硕士 全职@Google - Other - 技术电面 |Otherfresh grad应届毕业生

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

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

x
贡献两则谷歌家面经。其实第一次觉得自己面的还不错,题目也不难,但还是被要求加面。
11月1号第一次面试,貌似是一个美国大哥。先让我聊了聊实习的project,然后上题目,第一题是给一个String[] of integer和int k(subset的大小), 比如[9,15,3,14]和3, return一个subset,使得subset里面的最大值减最小值是所有subset里面最小的。所以这个例子返回[9,14,15], subset里面的数字不用按照input里的顺序。第二题是Leetcode reconstruct itinerary的简单版本。觉得自己答得还不错,结果被通知加面。
今天第二次面试,晚了10分钟打过来,因为小哥说他忘了带手机……目测美国小哥一枚,题目巨简单无比,让我怀疑这是不是谷歌的面试。第一题让自己定义一个double linked list,node的value是String. 然后写一个function, 给一个head和一个Set<String>, remove list里面value等于set里word的node。第二题是BST,给一个low bound和high bound, return list of nodes,这些nodes的值在low bound和high bound之间。用iterative和recursion两种方法写。
两次面试题目都无比简单,不知道这次小哥会不会让我过,感觉也是挺心累的

评分

3

查看全部评分

本帖被以下淘专辑推荐:

catinclay 发表于 2016-11-12 04:51:03 | 显示全部楼层
第一题是给一个String[] of integer和int k(subset的大小), 比如[9,15,3,14]和3, return一个subset,使得subset里面的最大值减最小值是所有subset里面最小的。
. 鍥磋鎴戜滑@1point 3 acres
请问这题有排序以外的做法吗? 想不到呀...
回复 支持 反对

使用道具 举报

syjohnson 发表于 2016-11-12 06:23:05 | 显示全部楼层
Lz onsite 肯定没问题!顺便问下你的一面第一题可以排序吗?或者说不排序怎么做呢
回复 支持 反对

使用道具 举报

类与对象tju 发表于 2016-11-12 08:25:41 | 显示全部楼层
syjohnson 发表于 2016-11-12 06:23
Lz onsite 肯定没问题!顺便问下你的一面第一题可以排序吗?或者说不排序怎么做呢

能排序感觉有点容易呀.........考点是求出所有subset?然后一个个比?
回复 支持 反对

使用道具 举报

 楼主| Pluto 发表于 2016-11-12 08:52:51 | 显示全部楼层
catinclay 发表于 2016-11-12 04:51
第一题是给一个String[] of integer和int k(subset的大小), 比如[9,15,3,14]和3, return一个subset,使得su ...

是的就是排序做的,所以很简单
回复 支持 反对

使用道具 举报

yyyfightinging 发表于 2016-11-12 13:05:51 | 显示全部楼层
请问lz排序了怎么做 k个k个比么
回复 支持 反对

使用道具 举报

oldfish 发表于 2016-11-12 13:39:47 | 显示全部楼层
yyyfightinging 发表于 2016-11-12 13:05
请问lz排序了怎么做 k个k个比么

排序完之后 第 i 个元素直接和第 k+i-1 个元素比较一下就成了吧

没 O(n) 的方法啦?
回复 支持 反对

使用道具 举报

yd1992 发表于 2016-12-3 00:46:48 | 显示全部楼层
天哪,我跟你一面的题一模一样。不过写的磕磕绊绊,结果莫名其妙onsite。 一直不敢相信为什么这么简单。。。
回复 支持 反对

使用道具 举报

cgxy1991 发表于 2016-12-6 00:15:35 | 显示全部楼层
第一题用普通排序自然简单,但是最好的方法是quick select
回复 支持 反对

使用道具 举报

wkvictor 发表于 2016-12-6 03:38:27 | 显示全部楼层
cgxy1991 发表于 2016-12-6 00:15
第一题用普通排序自然简单,但是最好的方法是quick select

求详细思路。。。
回复 支持 反对

使用道具 举报

snowblower 发表于 2016-12-6 04:01:47 | 显示全部楼层
lz莫担心,一定有onsite的!!!!

评分

1

查看全部评分

回复 支持 反对

使用道具 举报

cgxy1991 发表于 2016-12-6 04:08:51 | 显示全部楼层
wkvictor 发表于 2016-12-6 03:38
求详细思路。。。
. 1point3acres.com/bbs
排序的复杂度是O(nlog(n)). Waral 鍗氬鏈夋洿澶氭枃绔,
quick select可以找到一个数组中第N小的数,复杂度只要O(logn)
这道题要找到第N大的数,变个形就解决了。
回复 支持 反对

使用道具 举报

wkvictor 发表于 2016-12-8 13:07:34 | 显示全部楼层
cgxy1991 发表于 2016-12-6 04:08
排序的复杂度是O(nlog(n))
quick select可以找到一个数组中第N小的数,复杂度只要O(logn)
这道题要找到 ...

quick select不是average O(N)吗? 另外,没懂怎么变形。。求指点,谢啦!
回复 支持 反对

使用道具 举报

cgxy1991 发表于 2016-12-8 15:15:39 | 显示全部楼层
wkvictor 发表于 2016-12-8 13:07. from: 1point3acres.com/bbs
quick select不是average O(N)吗? 另外,没懂怎么变形。。求指点,谢啦!

说错了。就是O(N)。但quick select是找第k小的,所以如果要找第k大的,就要把k变成(n-k+1).    n = array size
回复 支持 反对

使用道具 举报

denilsen 发表于 2016-12-12 10:32:21 | 显示全部楼层
cgxy1991 发表于 2016-12-8 15:15
说错了。就是O(N)。但quick select是找第k小的,所以如果要找第k大的,就要把k变成(n-k+1).    n = array ...

如何把找第K大的任务和这个题联系到一起?
回复 支持 反对

使用道具 举报

cgxy1991 发表于 2016-12-12 10:50:08 | 显示全部楼层
denilsen 发表于 2016-12-12 10:32
如何把找第K大的任务和这个题联系到一起?

最小值+第K大值,即为所有subset中 最小的 min+max
回复 支持 反对

使用道具 举报

denilsen 发表于 2016-12-13 14:59:26 | 显示全部楼层
cgxy1991 发表于 2016-12-12 10:50
最小值+第K大值,即为所有subset中 最小的 min+max

实在无法理解,题目要求的是最小的 max-min   你写的min+max是什么意思呢?如果你意思是max-min的话,第K大的和最小值之差为什么就是呢?
回复 支持 反对

使用道具 举报

david123bbs 发表于 2016-12-27 07:09:10 | 显示全部楼层
denilsen 发表于 2016-12-13 14:59
实在无法理解,题目要求的是最小的 max-min   你写的min+max是什么意思呢?如果你意思是max-min的话,第K ...
. 1point 3acres 璁哄潧
我也無法理解
回复 支持 反对

使用道具 举报

shideck 发表于 2016-12-27 13:21:30 | 显示全部楼层
cgxy1991 发表于 2016-12-12 10:50
最小值+第K大值,即为所有subset中 最小的 min+max

1 100 101 102 103
subset = 3
不能是1 100 101 吧……  只想到了排序+遍历
回复 支持 反对

使用道具 举报

本版积分规则

关闭

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

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

custom counter

GMT+8, 2017-11-21 03:32

Powered by Discuz! X3

© 2001-2013 Comsenz Inc. Design By HUXTeam

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