推荐:数据科学课程和书籍清单以及培训讲座


一亩三分地论坛

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

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

Amazon OA 2 Round Robin 求助

[复制链接] |试试Instant~ |关注本帖
leoyue 发表于 2016-1-5 11:20:03 | 显示全部楼层 |阅读模式

2016(1-3月) 码农类 本科 全职@Amazon - 内推 - 在线笔试 |Otherfresh grad应届毕业生

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

您需要 登录 才可以下载或查看,没有帐号?获取更多干活,快来注册

x
Round Robin Average Wait Time的题,对                                                                                                                                                                                                [size=11.000000pt]int[] arrival = {0, 1, 3, 9};int[] run = {2, 1, 7, 5};[size=11.000000pt]int q = 2;[size=11.000000pt]的情况,我手算的Average Wait Time是4/4 = 1s,地里的面经的程序算的是1.25s,不知是我算错了还是程序有小bug?                                       
                               
                       
                . from: 1point3acres.com/bbs
. from: 1point3acres.com/bbs
nycok 发表于 2016-1-5 11:46:41 | 显示全部楼层
我跑了我自己的代码(oa test cases all pass),答案也是1
回复 支持 反对

使用道具 举报

 楼主| leoyue 发表于 2016-1-5 12:05:25 | 显示全部楼层
nycok 发表于 2016-1-5 11:46
我跑了我自己的代码(oa test cases all pass),答案也是1

好的好的我再debug一下,顺便问一下层主跑   
int[] arrival1 = {0, 1, 4};. from: 1point3acres.com/bbs
int[] run1 = {5, 2, 3};
int q1 = 3;
这个case是得到2.3333么,就是amazon给的case
回复 支持 反对

使用道具 举报

pengzewen37 发表于 2016-1-5 12:19:48 | 显示全部楼层
你用的是哪个面经的程序算的 我写的算出答案跟你一样
回复 支持 反对

使用道具 举报

 楼主| leoyue 发表于 2016-1-5 12:23:25 | 显示全部楼层
pengzewen37 发表于 2016-1-5 12:19
你用的是哪个面经的程序算的 我写的算出答案跟你一样

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

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

使用道具 举报

pengzewen37 发表于 2016-1-5 12:25:39 | 显示全部楼层
我的跟这个差不多,这是另一个帖子里面的. 涓浜-涓夊垎-鍦帮紝鐙鍙戝竷
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<>();. visit 1point3acres.com for more.
        int curTime = 0;. Waral 鍗氬鏈夋洿澶氭枃绔,
        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 ++) {. more info on 1point3acres.com
                                if (arrive[i] <= curTime) {
.1point3acres缃                                        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 {-google 1point3acres
                        queue.offer(new process(arrive[nextProIdx], excute[nextProIdx]));
                        curTime = arrive[nextProIdx ++];
                }
        }
. visit 1point3acres.com for more.        
        return (double)waitTime / arrive.length;.鐣欏璁哄潧-涓浜-涓夊垎鍦
}
回复 支持 反对

使用道具 举报

pengzewen37 发表于 2016-1-5 12:27:40 | 显示全部楼层
我的跟这个帖子里面3楼差不多http://www.1point3acres.com/bbs/thread-142143-1-1.html
回复 支持 反对

使用道具 举报

 楼主| leoyue 发表于 2016-1-5 12:29:13 | 显示全部楼层
pengzewen37 发表于 2016-1-5 12:27
我的跟这个帖子里面3楼差不多http://www.1point3acres.com/bbs/thread-142143-1-1.html
. 鐗涗汉浜戦泦,涓浜╀笁鍒嗗湴
恩好像是我改写的时候出了错误。。。
回复 支持 反对

使用道具 举报

pengzewen37 发表于 2016-1-5 12:33:29 | 显示全部楼层
leoyue 发表于 2016-1-4 23:29
恩好像是我改写的时候出了错误。。。

啊?所以答案还是1.25?
回复 支持 反对

使用道具 举报

 楼主| leoyue 发表于 2016-1-5 12:34:10 | 显示全部楼层
pengzewen37 发表于 2016-1-5 12:33
啊?所以答案还是1.25?
. 鐣欏鐢宠璁哄潧-涓浜╀笁鍒嗗湴
不。。。是他们写的java跑出来也是1。。。但是我改写成c++就错了
回复 支持 反对

使用道具 举报

pengzewen37 发表于 2016-1-5 12:36:07 | 显示全部楼层
leoyue 发表于 2016-1-4 23:34
不。。。是他们写的java跑出来也是1。。。但是我改写成c++就错了

额。。。那那个1.25是哪来的 诡异
回复 支持 反对

使用道具 举报

 楼主| leoyue 发表于 2016-1-5 13:02:02 | 显示全部楼层
pengzewen37 发表于 2016-1-5 12:36
额。。。那那个1.25是哪来的 诡异

我写错了。。。
回复 支持 反对

使用道具 举报

BrilliantBean 发表于 2016-1-5 13:13:21 | 显示全部楼层
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;. Waral 鍗氬鏈夋洿澶氭枃绔,
                int currTime = 0;. 1point3acres.com/bbs
                int waitTime = 0;. 鐣欏鐢宠璁哄潧-涓浜╀笁鍒嗗湴
                int i = 0;
                PriorityQueue<Process> pq = new PriorityQueue<Process>(len, new Comparator<Process>(){.鏈枃鍘熷垱鑷1point3acres璁哄潧
                        @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;.1point3acres缃
                                        pq.offer(new Process(currTime,tmp.executeTime - q));. From 1point 3acres bbs
                                }else{
                                        currTime += tmp.executeTime;
                                }
                                for(; i < len; i++){.鐣欏璁哄潧-涓浜-涓夊垎鍦
                                        if(arrive <= currTime){
                                                pq.offer(new Process(arrive,execute));
                                        }else
                                                break;
                                }
                        }else{
                                currTime = arrive;
                                pq.offer(new Process(arrive,execute));
. 鐣欏鐢宠璁哄潧-涓浜╀笁鍒嗗湴                                i++;
                        }. 1point 3acres 璁哄潧
                }.1point3acres缃
                return waitTime * 1.0 / len;
               
        }. Waral 鍗氬鏈夋洿澶氭枃绔,
. 1point 3acres 璁哄潧
补充内容 (2016-1-5 13:15):
不知道对不对,还望楼主指出
回复 支持 反对

使用道具 举报

dingmyue 发表于 2016-1-5 17:26:09 | 显示全部楼层
BrilliantBean 发表于 2016-1-5 13:13. 鐣欏鐢宠璁哄潧-涓浜╀笁鍒嗗湴
class Process{
  int arriveTime;
  int executeTime;

else currTime += temp.executeTime改成 curTime += Math.min(tmp.executeTime, q)试试呢  不要写else 因为不管execute多久 都是要更新curTime的. more info on 1point3acres.com
还有就是 那个if () {} 应该放在for loop的后面
回复 支持 反对

使用道具 举报

wbcustc 发表于 2016-1-6 07:27:07 | 显示全部楼层
public class Event{
            int arrive;
            int execute;
            public Event(int arrive,int execute){
                    this.arrive = arrive;
                    this.execute = execute;
            }. visit 1point3acres.com for more.
    }. Waral 鍗氬鏈夋洿澶氭枃绔,
   
    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>(){. From 1point 3acres bbs
                    public int compare(Event e1,Event e2){. 1point3acres.com/bbs
                            return e1.arrive-e2.arrive;
                    }
            });.1point3acres缃
            int nextIndex = 1,currTime = events[0].arrive,waitTime = 0;
            Queue<Event> queue = new LinkedList<>();
            queue.offer(events[0]);
            while(!queue.isEmpty()||nextIndex<n){. more info on 1point3acres.com
                    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;
                            }.1point3acres缃
                           
                            for(int i = nextIndex;i<n;i++){
                                    if(events[i].arrive<=currTime){
                                            queue.offer(events[i]);
                                            nextIndex = i+1;. 鍥磋鎴戜滑@1point 3 acres
                                    }else{
                                            break;. from: 1point3acres.com/bbs
                                    }
                            }. 鍥磋鎴戜滑@1point 3 acres
                            .鏈枃鍘熷垱鑷1point3acres璁哄潧
                              if(!finish){
                                    Event remain = new Event(currTime,currEvent.execute-limit);
                                    queue.offer(remain);
                            }. Waral 鍗氬鏈夋洿澶氭枃绔,
                    }else{
                            currTime = events[nextIndex].arrive;
                            queue.offer(events[nextIndex]);
                            nextIndex++;
                    }.鏈枃鍘熷垱鑷1point3acres璁哄潧
                      . 鐗涗汉浜戦泦,涓浜╀笁鍒嗗湴
            }
            return waitTime*1.0/n;
    }

这个代码debug过很多test case 应该没问题
回复 支持 反对

使用道具 举报

gaocan1992 发表于 2016-1-26 07:34:51 | 显示全部楼层
你的是对的,你看的面经不对
回复 支持 反对

使用道具 举报

llsshh1128 发表于 2016-2-23 07:08:54 | 显示全部楼层
request time: [0,2,4,5]
duration: [7,4,1,4]
q=3
average waiting time : 7

地理给的面经运行出来是7,但我自己手算是6.25啊~ . 1point3acres.com/bbs
很捉急啊,要考oa2了,谁能给我解释一下啊,谢谢啦!!!
回复 支持 反对

使用道具 举报

z165153 发表于 2016-7-29 12:38:44 | 显示全部楼层
leoyue 发表于 2016-1-5 12:23
http://www.1point3acres.com/bbs/thread-144891-1-1.html 给的附件,还有另一个之前的总结贴吧,反正算 ...

lz你好。请问改c++的时候,数组的长度你是怎么得到的呀?还请赐教哈。. 1point 3acres 璁哄潧
nextProIdx < arrive.length
回复 支持 反对

使用道具 举报

phonger 发表于 2017-1-29 16:02:27 | 显示全部楼层
llsshh1128 发表于 2016-2-23 07:08
request time: [0,2,4,5]
duration: [7,4,1,4]. From 1point 3acres bbs
q=3

需要注意的是: 当第一次执行完task 0的时候,task 2 和task 3还没到来,所以task0的第二次执行在task2之前,task的执行顺序如下: task queue
0.1point3acres缃
1,0. from: 1point3acres.com/bbs
0,2,3,1
2,3,1,0
3,1,0.鐣欏璁哄潧-涓浜-涓夊垎鍦
1,0,3
0,3
3
回复 支持 反对

使用道具 举报

本版积分规则

关闭

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

手机版|小黑屋|一亩三分地论坛声明

custom counter

GMT+8, 2017-8-21 05:13

Powered by Discuz! X3

© 2001-2013 Comsenz Inc. Design By HUXTeam

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