一亩三分地论坛

 找回密码
 获取更多干货,去instant注册!

扫码关注一亩三分地公众号
查看: 2101|回复: 12
收起左侧

[其他] 求问个Amazon OA2 的round robin

[复制链接] |试试Instant~ |关注本帖
TManjusaka 发表于 2015-10-31 10:39:23 | 显示全部楼层 |阅读模式

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

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

x
本帖最后由 TManjusaka 于 2015-10-31 10:56 编辑

求问下round robin这道题:http://www.1point3acres.com/bbs/thread-142143-1-1.html
example: arrive【0,1,4】 duration【5,2,3】 q=3.
这个切换任务的标准是啥?
每隔Q时间都要切换到队首的任务?还是切到队列里所有任务剩余时间最短的?还是切到当前任务和队首任务剩余时间较短的那个?
那个帖子17L有个解释: “第三个到的任务应该等了3秒。P2完成的时候已经在第5秒了。这时p1完成剩下的2秒,到达7秒。p3到达的时间是第4秒,然后第7秒的时候执行p3。”
另外那个帖子一楼的代码我跑过了,前后矛盾的,比如[0,1] [4,2] q =3 输出 2 说明在t=3时由任务1(剩余1)切到了任务2(剩余2). 可是在那个解释里面t=6时(任务1 剩余1,任务3剩余3)并没有切换
最后求下那个帖子里的截图。。多谢各位了 wuskipara@gmail.com

本帖被以下淘专辑推荐:

sanwan 发表于 2015-10-31 12:34:11 | 显示全部楼层
刚刚oa碰到这题,光理解就花了很久。。也没写粗来,打算回去想想
回复 支持 反对

使用道具 举报

zZ-IT 发表于 2015-10-31 13:58:13 | 显示全部楼层
Mark 一下跟帖,想问下楼主,你准备 insert node in cycle linked list那个题的时候,有没有返回值? 有的话返回的是最小节点嘛?
回复 支持 反对

使用道具 举报

 楼主| TManjusaka 发表于 2015-11-1 01:39:40 | 显示全部楼层
sanwan 发表于 2015-10-31 12:34
刚刚oa碰到这题,光理解就花了很久。。也没写粗来,打算回去想想

同学你又把题记下来么。。感觉就是题意理解不清
回复 支持 反对

使用道具 举报

 楼主| TManjusaka 发表于 2015-11-1 01:42:11 | 显示全部楼层
zZ-IT 发表于 2015-10-31 13:58
Mark 一下跟帖,想问下楼主,你准备 insert node in cycle linked list那个题的时候,有没有返回值? 有的 ...

感觉应该没有返回值,有的话就是最小节点了
回复 支持 反对

使用道具 举报

zZ-IT 发表于 2015-11-1 02:48:18 | 显示全部楼层
TManjusaka 发表于 2015-11-1 01:42
感觉应该没有返回值,有的话就是最小节点了

我昨天晚上问了另一个朋友,他好像是之前碰到了这题 insert node, 他说返回的是新加入的节点为开始的linkedlist
回复 支持 反对

使用道具 举报

zZ-IT 发表于 2015-11-1 10:56:24 | 显示全部楼层
楼主,我今天研究了下,应该是 每隔Q时间都要切换到队首的任务,再把当前未完成的加到队尾,楼主可以参考 wikipedia 的解释和图理解 https://en.wikipedia.org/wiki/Round-robin_scheduling, 另外如果楼主求到了截图,望共享! 谢谢啦 416736479@qq.com
回复 支持 反对

使用道具 举报

 楼主| TManjusaka 发表于 2015-11-2 06:07:32 | 显示全部楼层
zZ-IT 发表于 2015-11-1 10:56
楼主,我今天研究了下,应该是 每隔Q时间都要切换到队首的任务,再把当前未完成的加到队尾,楼主可以参考 w ...

嗯对我搞明白了,只要现在的任务进行了Q时间或者当前任务结束了就切换到队首的任务。多谢了!
另外我看了下insert node 那题的确是返回新插入的节点。
回复 支持 反对

使用道具 举报

CSBrogrammer 发表于 2015-11-10 15:50:56 | 显示全部楼层
TManjusaka 发表于 2015-11-2 06:07
嗯对我搞明白了,只要现在的任务进行了Q时间或者当前任务结束了就切换到队首的任务。多谢了!
另外我看 ...

请问如果list里有duplicate elements的话新节点是该插在相同element的最前端还是最后端还是中间任何位置都可以呢?谢谢!
回复 支持 反对

使用道具 举报

 楼主| TManjusaka 发表于 2015-11-11 02:42:20 | 显示全部楼层
CSBrogrammer 发表于 2015-11-10 15:50
请问如果list里有duplicate elements的话新节点是该插在相同element的最前端还是最后端还是中间任何位置 ...

不太清楚啊,感觉不会有duplicate的节点,如果有的话我猜应该是最前面
回复 支持 反对

使用道具 举报

CSBrogrammer 发表于 2015-11-11 02:56:01 | 显示全部楼层
TManjusaka 发表于 2015-11-11 02:42
不太清楚啊,感觉不会有duplicate的节点,如果有的话我猜应该是最前面

好的十分感谢~
回复 支持 反对

使用道具 举报

dwy189 发表于 2015-11-15 11:39:05 | 显示全部楼层
本帖最后由 dwy189 于 2015-11-15 11:52 编辑

请问一下大家,Round robin这题的time complexity是怎么样的呢?除了地里今年七月帖子里的解法外,有什么更优的解法呢?谢谢!
回复 支持 反对

使用道具 举报

本版积分规则

请点这里访问我们的新网站:一亩三分地Instant.

Instant搜索更强大,不扣积分,内容组织的更好更整洁!目前仍在beta版本,努力完善中!反馈请点这里

关闭

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

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

custom counter

GMT+8, 2016-12-8 03:47

Powered by Discuz! X3

© 2001-2013 Comsenz Inc. Design By HUXTeam

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