May 2009 - May 2017 论坛八周年-你的足迹,我的骄傲


一亩三分地论坛

 找回密码
 获取更多干活,快来注册

一亩三分地官方iOS手机应用下载
查看: 1411|回复: 10
收起左侧

Zenefits电面

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

使用道具 举报

Chasego 发表于 2015-10-27 22:46:20 | 显示全部楼层
关注一亩三分地微博:
Warald
liyanjia92 发表于 2015-10-27 11:51
这题怎么做?就是O(N^2)比较吗?

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

使用道具 举报

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

刚想了一个思路,先按开始时间排好, 如下(每一行是个time interval
. From 1point 3acres bbs
1                          8
    2              6
         3    5
                                 9    10
. 鐗涗汉浜戦泦,涓浜╀笁鍒嗗湴
然后对于每一个interval,看它之后的interva(按顺序)l有没有和它冲突, 直到找到一个没有和题冲突或者所有后面的intervals都遍历过。
譬如对于(1, 8),(2,6)和(3,5)都有冲突,因为它们的结束时间都小于或者等于8.
然后接着 (2, 6)用同样的方式找到(3,5). from: 1point3acres.com/bbs
(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 数组
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 1point 3acres bbs

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

使用道具 举报

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

感觉整体算法还是比较直观的,但求问一下这里的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
这道题的做法叫扫描线法,大概由以下几步构成. Waral 鍗氬鏈夋洿澶氭枃绔,
1. 先声明一个class
class point{

你的方法和我描述应该一样?虽然我不用额外的数据结构. 鐣欏鐢宠璁哄潧-涓浜╀笁鍒嗗湴
. visit 1point3acres.com for more.
补充内容 (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。 数据结构,输入输出都是 ...

谢谢哈~字数字数
回复 支持 反对

使用道具 举报

本版积分规则

关闭

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

手机版|小黑屋|一亩三分地论坛声明 ( 沪ICP备11015994号 )

custom counter

GMT+8, 2017-5-27 01:05

Powered by Discuz! X3

© 2001-2013 Comsenz Inc. Design By HUXTeam

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