10月28,K神开课讲数据科学,你来吗?


一亩三分地论坛

 找回密码
 获取更多干活,快来注册
Babeltime游戏工作室招工程师、美术和策划
Tubi TV招安卓、前端和机器学习工程师
把贵司招聘信息放这里
查看: 184|回复: 5
收起左侧

Dataminr的面试挂

[复制链接] |试试Instant~ |关注本帖
jason9263 发表于 5 天前 | 显示全部楼层 |阅读模式

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

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

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

x
                                     聊聊简历,然后开始做题.
.1point3acres缃
                                                        [0, 20]    30
                                                        [5, 10]    20
                                                        [12, 17]  -12
                                                        [15, 20]   15. 1point 3acres 璁哄潧
                                                        [18, 32]  5
. from: 1point3acres.com/bbs
输入是 一组  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);. 1point3acres.com/bbs


Follow Up
如何优化.

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





补充内容 (2017-9-15 01:39):. 鐗涗汉浜戦泦,涓浜╀笁鍒嗗湴
是 30+ 20 不是 30+50  ...typo
2011051305 发表于 5 天前 | 显示全部楼层
clrs的interval tree

补充内容 (2017-9-15 01:19):
.鏈枃鍘熷垱鑷1point3acres璁哄潧这东西。。。。真的 哪个学CS科班出身的孩子帮我讲一下 你们上算法或者高级算法的时候 真的会学这个并且实现吗? 。。。。
回复 支持 反对

使用道具 举报

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

使用道具 举报

a92921 发表于 5 天前 | 显示全部楼层
没看懂30+50什么意思……
回复 支持 反对

使用道具 举报

 楼主| jason9263 发表于 5 天前 | 显示全部楼层
a92921 发表于 2017-9-15 01:32. 1point 3acres 璁哄潧
没看懂30+50什么意思……

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

使用道具 举报

justin 发表于 5 天前 | 显示全部楼层
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
[15, 40] 20
[30, 45] 10

你要是merge了前两个变成:
[0, 40] 100
[30, 45] 10
=>
[30, 45] 100

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

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

使用道具 举报

本版积分规则

关闭

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

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

custom counter

GMT+8, 2017-9-20 03:10

Powered by Discuz! X3

© 2001-2013 Comsenz Inc. Design By HUXTeam

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