Amazon OA 2 Round Robin 求助

Round Robin Average Wait Time的题，对                                                                                                                                                                                                [size=11.000000pt]i

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

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

错了还是程序有小bug?                                       
                               
                       
               

public class Event{
            int arrive;
            int execute;
            public Event(int arrive,int execute){
                    this.arrive = arrive;
                    this.execute = execute;
            }
    }
   
    public double roundRobin(int[] arrive,int[] execute,int limit){
            int n = arrive.length;
            Event[] events = new Event[n];
            for(int i = 0;i<n;i++){
                    events[i] = new Event(arrive[i],execute[i]);
            }
            Arrays.sort(events,new Comparator<Event>(){
                    public int compare(Event e1,Event e2){
                            return e1.arrive-e2.arrive;
                    }
            });
            int nextIndex = 1,currTime = events[0].arrive,waitTime = 0;
            Queue<Event> queue = new LinkedList<>();
            queue.offer(events[0]);
            while(!queue.isEmpty()||nextIndex<n){
                    if(!queue.isEmpty()){
                            Event currEvent = queue.poll();
                            waitTime += currTime-currEvent.arrive;
                            boolean finish = true;
                            if(currEvent.execute<=limit){
                                    currTime += currEvent.execute;       
                            }else{
                                    currTime += limit;
                                    finish = false;
                            }
                           
                            for(int i = nextIndex;i<n;i++){
                                    if(events[i].arrive<=currTime){
                                            queue.offer(events[i]);
                                            nextIndex = i+1;
                                    }else{
                                            break;
                                    }
                            }
                           
                              if(!finish){
                                    Event remain = new Event(currTime,currEvent.execute-limit);
                                    queue.offer(remain);
                            }
                    }else{
                            currTime = events[nextIndex].arrive;
                            queue.offer(events[nextIndex]);
                            nextIndex++;
                    }
                     
            }
            return waitTime*1.0/n;
    }

这个代码debug过很多test case 应该没问题

class Process{
  int arriveTime;
  int executeTime;
  Process(int arr, int exe){
    this.arriveTime = arr;
    this.executeTime = exe;
}
}

public static double roundRobin(int[] arrive, int[] execute, int q){
                if(arrive == null || execute == null || arrive.length != execute.length)
                        return 0.0;
                int len = arrive.length;
                int currTime = 0;
                int waitTime = 0;
                int i = 0;
                PriorityQueue<Process> pq = new PriorityQueue<Process>(len, new Comparator<Process>(){
                        @Override
                        public int compare(Process p1, Process p2){
                                return p1.arriveTime - p2.arriveTime;
                               
                        }

                       
                });
               
                while(!pq.isEmpty()  || i < len){
                        if(!pq.isEmpty()){
                                Process tmp = pq.poll();
                                waitTime += currTime - tmp.arriveTime;
                                if(tmp.executeTime > q){
                                        currTime += q;
                                        pq.offer(new Process(currTime,tmp.executeTime - q));
                                }else{
                                        currTime += tmp.executeTime;
                                }
                                for(; i < len; i++){
                                        if(arrive[i] <= currTime){
                                                pq.offer(new Process(arrive[i],execute[i]));
                                        }else
                                                break;
                                }
                        }else{
                                currTime = arrive[i];
                                pq.offer(new Process(arrive[i],execute[i]));
                                i++;
                        }
                }
                return waitTime * 1.0 / len;
               
        }

补充内容 (2016-1-5 13:15):
不知道对不对，还望楼主指出

我的跟这个差不多，这是另一个帖子里面的
http://www.1point3acres.com/bbs/thread-142143-1-1.html
public class process {
        int arriveTime;
        int excuteTime;
        process(int arr, int exc) {
                arriveTime = arr;
                excuteTime = exc;
        }. From 1point 3acres bbs
}

// Assume arrive is sorted..1point3acres缃�
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;
}

我跑了我自己的代码(oa test cases all pass)，答案也是1

nycok 发表于 2016-1-5 11:46
我跑了我自己的代码(oa test cases all pass)，答案也是1

好的好的我再debug一下，顺便问一下层主跑   
int[] arrival1 = {0, 1, 4};
int[] run1 = {5, 2, 3};
int q1 = 3;
这个case是得到2.3333么，就是amazon给的case

你用的是哪个面经的程序算的 我写的算出答案跟你一样

pengzewen37 发表于 2016-1-5 12:19
你用的是哪个面经的程序算的 我写的算出答案跟你一样

http://www.1point3acres.com/bbs/thread-144891-1-1.html 给的附件，还有另一个之前的总结贴吧，反正算出来都是1.25但是应该是错的，能看一下版主你的代码么？

补充内容 (2016-1-5 12:24):
难道是我改写成c++的时候写错了么==但我看了一下应该是对的啊。。。

我的跟这个帖子里面3楼差不多http://www.1point3acres.com/bbs/thread-142143-1-1.html

pengzewen37 发表于 2016-1-5 12:27
我的跟这个帖子里面3楼差不多http://www.1point3acres.com/bbs/thread-142143-1-1.html

恩好像是我改写的时候出了错误。。。

leoyue 发表于 2016-1-4 23:29
恩好像是我改写的时候出了错误。。。

啊？所以答案还是1.25？

pengzewen37 发表于 2016-1-5 12:33
啊？所以答案还是1.25？

不。。。是他们写的java跑出来也是1。。。但是我改写成c++就错了