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


一亩三分地论坛

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

Dataminr的面试挂

[复制链接] |试试Instant~ |关注本帖
jason9263 发表于 2017-9-15 00:47:23 | 显示全部楼层 |阅读模式

2017(7-9月) 码农类 博士 全职@DataMinr - 网上海投 - 技术电面 |Failfresh grad应届毕业生

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

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

x
                                     聊聊简历,然后开始做题.

                                                        [0, 20]    30
                                                        [5, 10]    20.鏈枃鍘熷垱鑷1point3acres璁哄潧
                                                        [12, 17]  -12.鐣欏璁哄潧-涓浜-涓夊垎鍦
                                                        [15, 20]   15
                                                        [18, 32]  5

输入是 一组  interval  以及与interval 相伴的 val; 鏉ユ簮涓浜.涓夊垎鍦拌鍧.
如果有overlap的时候, 输出maxvalue

例如
[0,20] 与 [5,10] 有overlap, 那么输出 Math.max(30,20,30+50)
[5,10] [12,17] 没有overlap 就输出Math.max(20,-12);


Follow Up . 鍥磋鎴戜滑@1point 3 acres
如何优化.

给了个navie 的方法, 然后followup上卡了.
反正应该是跪了.


. 鐣欏鐢宠璁哄潧-涓浜╀笁鍒嗗湴
.鏈枃鍘熷垱鑷1point3acres璁哄潧

补充内容 (2017-9-15 01:39):
是 30+ 20 不是 30+50  ...typo
2011051305 发表于 2017-9-15 01:19:19 | 显示全部楼层
clrs的interval tree

补充内容 (2017-9-15 01:19):. 涓浜-涓夊垎-鍦帮紝鐙鍙戝竷
这东西。。。。真的 哪个学CS科班出身的孩子帮我讲一下 你们上算法或者高级算法的时候 真的会学这个并且实现吗? 。。。。
回复 支持 反对

使用道具 举报

2011051305 发表于 2017-9-15 01:23:23 | 显示全部楼层
话说naive的方法是指 sort start points, 然后用类似merge的方法来确定overlap? 那就是O(nlogn)?
回复 支持 反对

使用道具 举报

a92921 发表于 2017-9-15 01:32:13 | 显示全部楼层
没看懂30+50什么意思……
回复 支持 反对

使用道具 举报

 楼主| jason9263 发表于 2017-9-15 01:38:10 | 显示全部楼层
a92921 发表于 2017-9-15 01:32
没看懂30+50什么意思……

应该是 30+20 ... typo .. o(╯□╰)o
回复 支持 反对

使用道具 举报

justin 发表于 2017-9-15 01:59:48 | 显示全部楼层
2011051305 发表于 2017-9-14 12:23
话说naive的方法是指 sort start points, 然后用类似merge的方法来确定overlap? 那就是O(nlogn)?

naive应该是O(n^2),就是brute-force扫两遍吧。最优解使用interval tree就是O(nlogn),因为要生成这个tree,tree的深度是logn,然后要插入n次。

merge的方法是处理不了这种情况:
[0, 20] 100. Waral 鍗氬鏈夋洿澶氭枃绔,
[15, 40] 20
[30, 45] 10

你要是merge了前两个变成:. 鐗涗汉浜戦泦,涓浜╀笁鍒嗗湴
[0, 40] 100
[30, 45] 10
=>. from: 1point3acres.com/bbs
[30, 45] 100

然而[30, 45]只跟[15, 40]有overlap,所以它的max应该是20而不是100.merge是会丢失信息的,朋友~

PS,吐槽一下考interval tree的公司。这让我现场写我也写不了啊,除非你给我提示。。。。学过也不记得每个细节了啊
回复 支持 反对

使用道具 举报

本版积分规则

关闭

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

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

custom counter

GMT+8, 2017-11-24 17:50

Powered by Discuz! X3

© 2001-2013 Comsenz Inc. Design By HUXTeam

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