10月28,K神开讲数据科学:AB Test/实验设计


一亩三分地论坛

 找回密码
 Sign Up 注册获取更多干货
天天打游戏、照样领工资、还办H1B
这份工作你要不要?
把贵司招聘信息放这里
查看: 1564|回复: 10
收起左侧

Zenefits电面

[复制链接] |试试Instant~ |关注本帖
头像被屏蔽
qiaoyu314 发表于 2015-6-1 10:31:29 | 显示全部楼层 |阅读模式
提示: 作者被禁止或删除 内容自动屏蔽
liyanjia92 发表于 2015-10-27 11:51:31 | 显示全部楼层
这题怎么做?就是O(N^2)比较吗?
回复 支持 反对

使用道具 举报

Chasego 发表于 2015-10-27 22:46:20 | 显示全部楼层
liyanjia92 发表于 2015-10-27 11:51
这题怎么做?就是O(N^2)比较吗?

至少需要排序,根据开始时间和结束时间分别排序
回复 支持 反对

使用道具 举报

Chasego 发表于 2015-10-27 23:05:33 | 显示全部楼层
liyanjia92 发表于 2015-10-27 11:51. 1point 3acres 璁哄潧
这题怎么做?就是O(N^2)比较吗?
. 1point3acres.com/bbs
刚想了一个思路,先按开始时间排好, 如下(每一行是个time interval

1                          8
    2              6. from: 1point3acres.com/bbs
         3    5
                                 9    10

然后对于每一个interval,看它之后的interva(按顺序)l有没有和它冲突, 直到找到一个没有和题冲突或者所有后面的intervals都遍历过。. 鐣欏鐢宠璁哄潧-涓浜╀笁鍒嗗湴
譬如对于(1, 8),(2,6)和(3,5)都有冲突,因为它们的结束时间都小于或者等于8.
然后接着 (2, 6)用同样的方式找到(3,5). visit 1point3acres.com for more.
(3,5) 没有和后面冲突
最后一行(9, 10) 不用管
回复 支持 反对

使用道具 举报

aiuou 发表于 2015-10-31 12:48:07 | 显示全部楼层
这道题的做法叫扫描线法,大概由以下几步构成. 涓浜-涓夊垎-鍦帮紝鐙鍙戝竷
1. 先声明一个class
class point{
     int time;.鐣欏璁哄潧-涓浜-涓夊垎鍦
     int intervalIndex;
     String attribute;
. 涓浜-涓夊垎-鍦帮紝鐙鍙戝竷
2. 把每一个interval拆成两个point, start 和 end. 存在一个一维的数组里 point[] points
3. 按照point.time sort 数组
.鏈枃鍘熷垱鑷1point3acres璁哄潧4. 用一条扫描线从左向右扫,同时maintain一个set。 如果扫到的point是start 就把这个start point对应的interval index加入set, 如果扫到的是一个end point就把这个end point对应的interval index 从set中删除。这就使得当你每扫到一个新的start point时,set里的interval都还没有结束,也就是说这个新加入的start point所对应的interval 与目前set中的所有interval overlap。把这些overlap 都加到result里面去。. 鐗涗汉浜戦泦,涓浜╀笁鍒嗗湴
5.扫描所有点后,返回result. from: 1point3acres.com/bbs

复杂度就是sort的o(nlgn)
回复 支持 反对

使用道具 举报

jyang_2015 发表于 2015-11-4 14:07:06 | 显示全部楼层
aiuou 发表于 2015-10-31 12:48
这道题的做法叫扫描线法,大概由以下几步构成
1. 先声明一个class
class point{

. 1point 3acres 璁哄潧感觉整体算法还是比较直观的,但求问一下这里的time和 attribute具体指什么呢?
回复 支持 反对

使用道具 举报

jyang_2015 发表于 2015-11-4 14:41:47 | 显示全部楼层
jyang_2015 发表于 2015-11-4 14:07
感觉整体算法还是比较直观的,但求问一下这里的time和 attribute具体指什么呢?

哦 我懂了,这里time其实就可以用position,然后attribute 我们可以其实存一个指针用来link start point 和 end point。这样你从set中删除end point对应的interval index时(i.e. start point) 就可以O(1) time了。

但这种方法有个要注意的问题就是边界点怎么办? 比如[1,2]和[2,4] 算conflict么?如果算的话,sort的时候除了要根据当前点的position,还要看对应的同一个interval的另一个端点的postiion哈
回复 支持 反对

使用道具 举报

Chasego 发表于 2015-11-9 01:55:19 | 显示全部楼层
aiuou 发表于 2015-10-31 12:48
这道题的做法叫扫描线法,大概由以下几步构成
1. 先声明一个class
class point{

你的方法和我描述应该一样?虽然我不用额外的数据结构. 涓浜-涓夊垎-鍦帮紝鐙鍙戝竷

补充内容 (2015-11-9 02:17):
主要考虑到你每次把冲突部分加进去的时候,所用的时间还是和加入的冲突的个数成正比(即使你用了set)。换句话说,除了排序的方法,你的方法和我一样,找conflict pair 的时间和conflict 的pair的个数成正比?
回复 支持 反对

使用道具 举报

misshary 发表于 2016-2-12 20:22:20 | 显示全部楼层
求题目细节,貌似lz被屏蔽了~~~~
回复 支持 反对

使用道具 举报

freetrek 发表于 2016-2-29 13:56:39 | 显示全部楼层
“Skype电面,美国人。 题目:给定很多time interval,找到所有有conflict的pair。 数据结构,输入输出都是自己设计。” @misshary
回复 支持 反对

使用道具 举报

misshary 发表于 2016-3-23 20:54:35 | 显示全部楼层
freetrek 发表于 2016-2-29 13:56
“Skype电面,美国人。 题目:给定很多time interval,找到所有有conflict的pair。 数据结构,输入输出都是 ...
. From 1point 3acres bbs
谢谢哈~字数字数
回复 支持 反对

使用道具 举报

本版积分规则

关闭

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

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

custom counter

GMT+8, 2017-10-19 06:01

Powered by Discuz! X3

© 2001-2013 Comsenz Inc. Design By HUXTeam

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