一亩三分地论坛

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

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

AMAZON OA2 新的一个coding题!!!

  [复制链接] |试试Instant~ |关注本帖
novac812 发表于 2015-9-22 13:20:54 | 显示全部楼层 |阅读模式

2015(7-9月) 码农类 硕士 全职@Amazon - 猎头 - 在线笔试 |Passfresh grad应届毕业生

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

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

x
OA2 重点想说下code的一个题,真的是个大坑啊。。。。做了半天还是有bug,不过为了造福地里的同学。特地截了图,不过太大不让传 = =。希望对大家有帮助。是robin wait time。. Waral 鍗氬鏈夋洿澶氭枃绔,
大概是这样,给一个int[] arrival time, int[] Execution time, int q. 例子: 【0,1,4】 【5,2,3】 q=3. 输出的是average wait time 2.3333333

这个q大家一定要注意啊。。。。已经不是non-pre的了。. more info on 1point3acres.com
. visit 1point3acres.com for more.
希望对大家有帮助。

话说咋求大米啊?
. visit 1point3acres.com for more.

补充内容 (2015-11-17 08:06):
图在124,125楼。

评分

20

查看全部评分

本帖被以下淘专辑推荐:

DWill008 发表于 2015-11-16 10:30:42 | 显示全部楼层
熊亮亮111 发表于 2015-11-16 09:49
我也是这么理解的,然后第10秒的时候完成 p3  但是这样的话应该是10/3=3.3333333啊  而不是2.333333.

我是这么理解的,有不对的地方请指出.1point3acres缃
我拿贴子里面给出的例子来说明下吧。
【0,1,4】 【5,2,3】 q = 3
.鏈枃鍘熷垱鑷1point3acres璁哄潧
第0秒,任务1进队列。我们peek目前队列中有的任务是任务1,我们发现任务1开始时间第0秒,目前也是第0秒,所以任务1等待时间是0。然后任务1执行3秒,它自身还有2秒钟。 鏉ユ簮涓浜.涓夊垎鍦拌鍧.
这时候我们查看3秒的时候哪些任务达到了,发现任务2在第1秒到达。于是任务2进队列。
这时候我们查看任务1有没有执行完,发现没有执行完,于是我们poll任务1,再把任务1 add到队列末尾。
这时候队列的顺序是任务2,任务1.

现在我们再次peek队列,于是找到任务2.我们发现任务2在第1秒到达了,目前我们在第3秒。所以等待时间是3-1=2.. Waral 鍗氬鏈夋洿澶氭枃绔,
我们重复刚刚的步骤,发现任务2执行时间只要2秒,于是我们到第5秒。这时候我们查找第5秒哪些任务到达了。我们发现任务3也到达了。于是任务3进队列。
所以目前队列顺序是任务2,任务1,任务3.
我们又发现任务2已经执行完了,于是我们把任务2 poll出队列,不再把它放进队列里了。
所以现在队列里面剩余的任务是任务1,任务3..鏈枃鍘熷垱鑷1point3acres璁哄潧

于是我们再peek队列。请注意,这时候的q被重新设置过了,不是3-2=1秒,而是又是3秒。. 鐗涗汉浜戦泦,涓浜╀笁鍒嗗湴
我们再次peek队列,找到任务1,目前是在第5秒,我们刚刚执行过任务1,他暂停在第3秒,所以任务1又等了2秒。目前秒数是2+2=4秒。
目前任务1还有2秒。我们执行完任务1以后,到达第5+2 = 7把他扔出队列。目前队列里只有任务3了。. 1point 3acres 璁哄潧

然后我们再peek,现在只有任务3了,目前我们在第7秒。任务3进来的时候在第4秒。所以任务3等了7-4 = 3秒。所以等待时间又加3秒。
所以最终等待时间是2+2+3 = 7秒。平均等待时间是7/3 = 2.3333秒。

评分

3

查看全部评分

回复 支持 11 反对 0

使用道具 举报

dwl1222 发表于 2015-9-25 06:36:11 | 显示全部楼层
public class process {
        int arriveTime;
        int excuteTime;
        process(int arr, int exc) {. Waral 鍗氬鏈夋洿澶氭枃绔,
                arriveTime = arr;
                excuteTime = exc;
        }
}

// Assume arrive is sorted.
public double roundRobin(int[] arrive, int[] excute, int q) {
        LinkedList<process> queue = new LinkedList<>();.鐣欏璁哄潧-涓浜-涓夊垎鍦
        int curTime = 0;. from: 1point3acres.com/bbs
        int waitTime = 0;
        int nextProIdx = 0;. visit 1point3acres.com for more.
        while (!queue.isEmpty() || nextProIdx < arrive.length) {. 鐗涗汉浜戦泦,涓浜╀笁鍒嗗湴
                if (!queue.isEmpty()) {
                        process cur = queue.poll();. visit 1point3acres.com for more.
                        waitTime += curTime - cur.arriveTime;
                        curTime += Math.min(cur.excuteTime, q);
                        for (int i = nextProIdx; i < arrive.length; i ++) {
                                if (arrive[i] <= curTime) {
                                        queue.offer(new process(arrive[i], excute[i]));
                                        nextProIdx = i + 1;
                                } else {. 涓浜-涓夊垎-鍦帮紝鐙鍙戝竷
                                        break;
                                }
                        }
                        if (cur.excuteTime > q) {. 鐣欏鐢宠璁哄潧-涓浜╀笁鍒嗗湴
                                queue.offer(new process(curTime, cur.excuteTime - q);
                        }. visit 1point3acres.com for more.
                } else {
                        queue.offer(new process(arrive[nextProIdx], excute[nextProIdx]));
                        curTime = arrive[nextProIdx ++];. more info on 1point3acres.com
                }
        }
       
        return (double)waitTime / arrive.length;
}
回复 支持 8 反对 1

使用道具 举报

rosalind324 发表于 2015-11-24 11:09:30 | 显示全部楼层
https://www.youtube.com/watch?v=aWlQYllBZDs

这里有视频介绍的很清楚!Round Robin Algorithm Tutorial (CPU Scheduling)

评分

2

查看全部评分

回复 支持 5 反对 0

使用道具 举报

 楼主| novac812 发表于 2015-11-17 08:06:25 | 显示全部楼层
第二个图,发在这里啦。
Screen Shot 2015-09-21 at 17.45.21.png

评分

1

查看全部评分

回复 支持 1 反对 0

使用道具 举报

熊亮亮111 发表于 2015-11-18 08:35:53 | 显示全部楼层
dwl1222 发表于 2015-11-18 05:20
我觉得并不是。不是说有两个循环就是n^2的。你仔细看代码: 里面的nextProIdx是一直在增加的。本质上就是 ...

看着你的头像实在是让我分心啊。 我跟朋友讨论了一下,又觉得是O(n),for循环里边就是把没有执行的任务添加到queue里, 然后while里边再取出来执行, 所以一共n个任务 O(n)
回复 支持 1 反对 0

使用道具 举报

hza47 发表于 2015-9-22 13:40:52 | 显示全部楼层
楼主可以吧截图发给我吗,我有一个OA2要做了, 谢谢了楼主, 邮箱是 hza47@sfu.ca
回复 支持 反对

使用道具 举报

DWill008 发表于 2015-9-23 00:21:54 | 显示全部楼层
请问lz,arrival time这个数组给你的时候都是排好序的吗?
还有,你说的non-pre是指,每隔q个时间,任务会自动切换,还是说即使在q时间内,只要有一个execution time比当前执行任务剩余时间更短的任务到达,当前任务也会被切换掉?-google 1point3acres

补充内容 (2015-9-23 02:50):
再问下lz,[0,1,4] [5,2,3] q = 3的average wait time 答案 2.33333 是OA给的吗?
回复 支持 反对

使用道具 举报

DWill008 发表于 2015-9-23 00:30:55 | 显示全部楼层

q是指quantum,round robin的算法每隔quantum个时间都会强制切换到下一个任务,如果当前任务没有执行完的话。
回复 支持 反对

使用道具 举报

wenqiang88 发表于 2015-9-23 06:48:57 | 显示全部楼层
DWill008 发表于 2015-9-23 00:30
q是指quantum,round robin的算法每隔quantum个时间都会强制切换到下一个任务,如果当前任务没有执行完的 ...
鏉ユ簮涓浜.涓夊垎鍦拌鍧.
哦,明白啦,多谢LZ
回复 支持 反对

使用道具 举报

 楼主| novac812 发表于 2015-9-23 07:28:25 | 显示全部楼层
恩啊,我的例子是OA里面给的例子。
回复 支持 反对

使用道具 举报

ffjjcclxxx 发表于 2015-9-23 09:25:44 | 显示全部楼层
楼主能把图发我信箱吗 jedfeng.career@gmail.com
回复 支持 反对

使用道具 举报

miyaha 发表于 2015-9-23 13:54:48 | 显示全部楼层
多谢楼主分享啊! 马上也要做oa2了。。。可是我算出来的是2.666啊。。。
回复 支持 反对

使用道具 举报

zmh1991 发表于 2015-9-23 13:56:34 | 显示全部楼层
楼主,如果是preempt的话,那average wait time我算的是2.66666666,能不能把截图发我一下?我邮箱625651613@qq.com,谢谢楼主~
回复 支持 反对

使用道具 举报

沼泽地的青蛙 发表于 2015-9-25 01:53:41 | 显示全部楼层
求楼主发截图,我会追加大米决不食言!souverlai.nate@gmail.com跪谢楼主!offer多多!
回复 支持 反对

使用道具 举报

rhett.lhy 发表于 2015-9-25 02:16:34 | 显示全部楼层
楼主好人!求截图!sophie.cst6@hotmail.com
回复 支持 反对

使用道具 举报

Warren 发表于 2015-9-25 03:03:50 | 显示全部楼层
LZ. 同求截图!ywqapply@gmail.com
回复 支持 反对

使用道具 举报

cleverley 发表于 2015-9-25 03:51:21 | 显示全部楼层
DWill008 发表于 2015-9-23 00:21
请问lz,arrival time这个数组给你的时候都是排好序的吗?. 1point 3acres 璁哄潧
还有,你说的non-pre是指,每隔q个时间,任务会 ...

请问arrival time是什么意思啊?
回复 支持 反对

使用道具 举报

cleverley 发表于 2015-9-25 03:55:22 | 显示全部楼层
DWill008 发表于 2015-9-23 00:21
请问lz,arrival time这个数组给你的时候都是排好序的吗?
还有,你说的non-pre是指,每隔q个时间,任务会 ...

是不是这样理解啊,0秒到达一个任务,需要执行5秒,其实执行了三秒,就跳到了下一个一秒的时候到达的任务了。所以第二个任务等了2秒,第一个任务等第二个任务执行的时候又等了两秒,于是跳回了第一个任务执行两秒,第三个到的任务等一秒,最后执行完成。
回复 支持 反对

使用道具 举报

ipadthree 发表于 2015-9-25 04:51:10 | 显示全部楼层
楼主好人,求截图,我这周末就做OA2了~~邮箱ipodtouchin2008@gmail.com,十分感谢!!
回复 支持 反对

使用道具 举报

DWill008 发表于 2015-9-25 05:11:59 | 显示全部楼层
cleverley 发表于 2015-9-25 03:55
是不是这样理解啊,0秒到达一个任务,需要执行5秒,其实执行了三秒,就跳到了下一个一秒的时候到达的任务 ...
. 鐗涗汉浜戦泦,涓浜╀笁鍒嗗湴
第三个到的任务应该等了3秒。P2完成的时候已经在第5秒了。这时p1完成剩下的2秒,到达7秒。p3到达的时间是第4秒,然后第7秒的时候执行p3。
回复 支持 反对

使用道具 举报

zchang3 发表于 2015-9-25 06:19:46 | 显示全部楼层
请问楼主是什么时候投的?
回复 支持 反对

使用道具 举报

沼泽地的青蛙 发表于 2015-9-25 07:30:29 | 显示全部楼层
还有请问楼主遇见的另一道题是什么题?
回复 支持 反对

使用道具 举报

本版积分规则

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

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

关闭

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

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

custom counter

GMT+8, 2016-12-4 03:43

Powered by Discuz! X3

© 2001-2013 Comsenz Inc. Design By HUXTeam

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