一亩三分地论坛

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

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

Amazon OA 2 Round Robin 求助

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

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

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

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

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?                                       
                                . Waral 鍗氬鏈夋洿澶氭枃绔,
                        . 涓浜-涓夊垎-鍦帮紝鐙鍙戝竷
               

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};
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
}
. visit 1point3acres.com for more.
// Assume arrive is sorted..1point3acres缃�
public double roundRobin(int[] arrive, int[] excute, int q) {.鏈枃鍘熷垱鑷1point3acres璁哄潧
        LinkedList<process> queue = new LinkedList<>();
        int curTime = 0;
        int waitTime = 0;
        int nextProIdx = 0;. 1point 3acres 璁哄潧
        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;
                                }
                        }. 1point3acres.com/bbs
                        if (cur.excuteTime > q) {
                                queue.offer(new process(curTime, cur.excuteTime - q);
                        }.鏈枃鍘熷垱鑷1point3acres璁哄潧
                } else {
                        queue.offer(new process(arrive[nextProIdx], excute[nextProIdx]));
                        curTime = arrive[nextProIdx ++];
                }
        }
        
        return (double)waitTime / arrive.length;.鏈枃鍘熷垱鑷1point3acres璁哄潧
}
回复 支持 反对

使用道具 举报

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. From 1point 3acres bbs
恩好像是我改写的时候出了错误。。。

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

使用道具 举报

 楼主| leoyue 发表于 2016-1-5 12:34:10 | 显示全部楼层
pengzewen37 发表于 2016-1-5 12:33. Waral 鍗氬鏈夋洿澶氭枃绔,
啊?所以答案还是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;. 鍥磋鎴戜滑@1point 3 acres
    this.executeTime = exe;
}. 涓浜-涓夊垎-鍦帮紝鐙鍙戝竷
}
-google 1point3acres
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>(){. visit 1point3acres.com for more.
                        @Override
                        public int compare(Process p1, Process p2){
                                return p1.arriveTime - p2.arriveTime;
                               
                        }
. 涓浜-涓夊垎-鍦帮紝鐙鍙戝竷
                       
                });
               
                while(!pq.isEmpty()  || i < len){
                        if(!pq.isEmpty()){-google 1point3acres
                                Process tmp = pq.poll();
                                waitTime += currTime - tmp.arriveTime;
                                if(tmp.executeTime > q){. visit 1point3acres.com for more.
                                        currTime += q;
                                        pq.offer(new Process(currTime,tmp.executeTime - q));
                                }else{
                                        currTime += tmp.executeTime;
                                }. visit 1point3acres.com for more.
                                for(; i < len; i++){
. visit 1point3acres.com for more.                                        if(arrive <= currTime){
                                                pq.offer(new Process(arrive,execute));
. 1point 3acres 璁哄潧                                        }else
                                                break;
                                }
                        }else{. more info on 1point3acres.com
                                currTime = arrive;
                                pq.offer(new Process(arrive,execute));
                                i++;.鐣欏璁哄潧-涓浜-涓夊垎鍦
                        }
                }
                return waitTime * 1.0 / len;
               
        }. more info on 1point3acres.com

补充内容 (2016-1-5 13:15):
不知道对不对,还望楼主指出
回复 支持 反对

使用道具 举报

dingmyue 发表于 2016-1-5 17:26:09 | 显示全部楼层
BrilliantBean 发表于 2016-1-5 13:13.鏈枃鍘熷垱鑷1point3acres璁哄潧
class Process{
. From 1point 3acres bbs  int arriveTime;
  int executeTime;

else currTime += temp.executeTime改成 curTime += Math.min(tmp.executeTime, q)试试呢  不要写else 因为不管execute多久 都是要更新curTime的
还有就是 那个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;
            }
    }
   
. 1point 3acres 璁哄潧    public double roundRobin(int[] arrive,int[] execute,int limit){
            int n = arrive.length;. from: 1point3acres.com/bbs
            Event[] events = new Event[n];
            for(int i = 0;i<n;i++){-google 1point3acres
                    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++;
                    }
                      . 涓浜-涓夊垎-鍦帮紝鐙鍙戝竷
            }. 1point3acres.com/bbs
            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啊~
很捉急啊,要考oa2了,谁能给我解释一下啊,谢谢啦!!!
回复 支持 反对

使用道具 举报

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

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

使用道具 举报

本版积分规则

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

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

关闭

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

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

custom counter

GMT+8, 2016-12-9 08:18

Powered by Discuz! X3

© 2001-2013 Comsenz Inc. Design By HUXTeam

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