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


一亩三分地论坛

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

脸家电面

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

2017(10-12月) 码农类 硕士 实习@Facebook - 内推 - 技术电面 |Other其他

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

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

x
今天下午的一面,听声音应该是个白人小哥,考了两道原题,还都是原版。。。1.  里口二乌散,纯纯原版,只是时间的表示是11:00am 这种,follow up 如果有一个会是头天晚上11点开到第二天凌晨1点这种跨天的怎么处理. 1point3acres.com/bbs
2. kth largest number. follow up 如果memory < k 怎么办,比如1/2 k, 1/3 k怎么处理

上来被小哥挑了简历里的一个项目讲了讲,说了一下这个项目里遇到的困难。然后扔了kth largest number, 我还看题呢,小哥问我这题你见过么?我选择了诚实,我说这个很基础啊,学priority queue和quick select的时候都会讲的例子嘛,要不咱们跳了吧。然后就是二乌散,太紧张了我都忘了之前怎么写的了,反正写的有点慢,还出了个bug。从描述到follow up完大概搞了快30分钟。。。。。然后还有点时间小哥说上题我们还是说下思路吧,然后就描述了下思路没有写代码-google 1point3acres

感觉还是不适应面试的节奏,下次得说快点写快点,希望能过吧。

第一次发帖,求大米~

评分

6

查看全部评分

向上的牛牛 发表于 2017-11-14 14:27:55 | 显示全部楼层
hhcctvwwa 发表于 2017-11-14 14:04
以我的理解,既然我们把数组分成了m组排好了序,那接下来的问题就是merge m sorted array了,这个空间复 ...

或者楼主这一题就直接利用priority queue求解可以吗?. From 1point 3acres bbs
维护一个size为k/m的min-heap;
首先找到第k/m大的数(计作x);
然后清空heap,用同样的方法再找第2*k/m大的数(这次寻找的时候,所有大于x的数就不需要再扔进heap里了);
以此类推...
直到找到第m * k / m = k大的数?
这样的话时间复杂度就是O(m*n* log(k / m))
回复 支持 2 反对 0

使用道具 举报

落魄酸丁 发表于 2017-11-14 09:42:06 | 显示全部楼层
hhcctvwwa 发表于 2017-11-14 09:39
这应该就是标答吧,sort m个子序列然后merge。当时我没想到,我说的是如果内存是k/m的话就排序m次,每次 ...

内存是k/m的话怎么对两个k/m大的array merge呢,求问这个memory的限制到底在哪呢
回复 支持 1 反对 0

使用道具 举报

zqyzdsjdy 发表于 2017-11-14 09:20:51 | 显示全部楼层
感谢,求问两个follow up 楼主怎么回答的?
回复 支持 反对

使用道具 举报

gyzjay 发表于 2017-11-14 09:29:23 | 显示全部楼层
kth large follow up 是不是external sort后遍历到第k个?
回复 支持 反对

使用道具 举报

 楼主| hhcctvwwa 发表于 2017-11-14 09:39:15 | 显示全部楼层
gyzjay 发表于 2017-11-14 09:29
kth large follow up 是不是external sort后遍历到第k个?

这应该就是标答吧,sort m个子序列然后merge。当时我没想到,我说的是如果内存是k/m的话就排序m次,每次取走k/m个最大值,最后就可以得到结果
回复 支持 反对

使用道具 举报

 楼主| hhcctvwwa 发表于 2017-11-14 09:40:36 | 显示全部楼层
zqyzdsjdy 发表于 2017-11-14 09:20
感谢,求问两个follow up 楼主怎么回答的?

第一个follow up 就是如果晚一天就加24小时,第二个follow up在另一个回复里
回复 支持 反对

使用道具 举报

 楼主| hhcctvwwa 发表于 2017-11-14 14:04:31 来自手机 | 显示全部楼层
落魄酸丁 发表于 2017-11-14 09:42
内存是k/m的话怎么对两个k/m大的array merge呢,求问这个memory的限制到底在哪呢

以我的理解,既然我们把数组分成了m组排好了序,那接下来的问题就是merge m sorted array了,这个空间复杂度用pq是O(m)啊,你每merge一个写入硬盘就好了
回复 支持 反对

使用道具 举报

向上的牛牛 发表于 2017-11-14 15:30:36 | 显示全部楼层
hhcctvwwa 发表于 2017-11-14 09:39
这应该就是标答吧,sort m个子序列然后merge。当时我没想到,我说的是如果内存是k/m的话就排序m次,每次 ...
. 涓浜-涓夊垎-鍦帮紝鐙鍙戝竷
楼主,memory不是k/m吗?子序列应该是 n/(k/m) 个吧?
回复 支持 反对

使用道具 举报

 楼主| hhcctvwwa 发表于 2017-11-14 21:33:57 | 显示全部楼层
向上的牛牛 发表于 2017-11-14 14:27
或者楼主这一题就直接利用priority queue求解可以吗?
维护一个size为k/m的min-heap;
首先找到第k/m大 ...

我回答的就是这个思路,现在想来似乎还挺可行
回复 支持 反对

使用道具 举报

本版积分规则

关闭

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

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

custom counter

GMT+8, 2017-11-25 17:48

Powered by Discuz! X3

© 2001-2013 Comsenz Inc. Design By HUXTeam

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