AMAZON OA2 新的一个coding题！！！

OA2 重点想说下code的一个题，真的是个大坑啊。。。。做了半天还是有bug，不过为了造福地里的同学。特地截了图，不过太大不让传 = =。希望对大家有帮助。是robin wait time。

您好！
本帖隐藏的内容需要积分高于 188 才可浏览
您当前积分为 0。
使用VIP即刻解锁阅读权限或查看其他获取积分的方式

游客，您好！
本帖隐藏的内容需要积分高于 188 才可浏览
您当前积分为 0。
VIP即刻解锁阅读权限 或 查看其他获取积分的方式
Unlock interview details and practice with AI
Curated Interview Questions from Top Companies

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

第二个图，发在这里啦。

熊亮亮111 发表于 2015-11-16 09:49
我也是这么理解的，然后第10秒的时候完成 p3  但是这样的话应该是10/3=3.3333333啊  而不是2.333333.

我是这么理解的，有不对的地方请指出
我拿贴子里面给出的例子来说明下吧。
【0，1，4】 【5，2，3】 q ＝ 3

第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.
我们重复刚刚的步骤，发现任务2执行时间只要2秒，于是我们到第5秒。这时候我们查找第5秒哪些任务到达了。我们发现任务3也到达了。于是任务3进队列。
所以目前队列顺序是任务2，任务1，任务3.
我们又发现任务2已经执行完了，于是

您好！
本帖隐藏的内容需要积分高于 155 才可浏览
您当前积分为 0。
使用VIP即刻解锁阅读权限或查看其他获取积分的方式

游客，您好！
本帖隐藏的内容需要积分高于 155 才可浏览
您当前积分为 0。
VIP即刻解锁阅读权限 或 查看其他获取积分的方式
Unlock interview details and practice with AI
Curated Interview Questions from Top Companies

所以等待时间又加3秒。
所以最终等待时间是2+2+3 ＝ 7秒。平均等待时间是7/3 ＝ 2.3333秒。

public class process {
        int arriveTime;
        int excuteTime;
        process(int arr, int exc) {
                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;
        int waitTime = 0;
        int nextProIdx = 0;
        while (!queue.isEmpty() || nextProIdx < arrive.length) {
                if (!queue.isEmpty()) {
                        process cur = queue.poll();
                        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);
                        }
                } else {
                        queue.offer(new process(arrive[nextProIdx], excute[nextProIdx]));
                        curTime = arrive[nextProIdx ++];
                }
        }
       
        return (double)waitTime / arrive.length;
}

https://www.youtube.com/watch?v=aWlQYllBZDs

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

q是啥意思？

请问lz，arrival time这个数组给你的时候都是排好序的吗？
还有，你说的non-pre是指，每隔q个时间，任务会自动切换，还是说即使在q时间内，只要有一个execution time比当前执行任务剩余时间更短的任务到达，当前任务也会被切换掉？

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

wenqiang88 发表于 2015-9-22 13:29
q是啥意思？

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

DWill008 发表于 2015-9-23 00:30
q是指quantum，round robin的算法每隔quantum个时间都会强制切换到下一个任务，如果当前任务没有执行完的 ...

哦，明白啦，多谢LZ

恩啊，我的例子是OA里面给的例子。

多谢楼主分享啊！ 马上也要做oa2了。。。可是我算出来的是2.666啊。。。