一亩三分地论坛

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

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

关于 SJF 代码分析以及 Amazon video follow up

[复制链接] |试试Instant~ |关注本帖
JefferyChou 发表于 2015-11-4 04:37:31 | 显示全部楼层 |阅读模式

2015(10-12月) 码农类 硕士 全职@Amazon - 内推 - 技术电面 |Otherfresh grad应届毕业生

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

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

x
谢谢大家点进来。最近人品还行,拿了amazon 的video,看了很多帖子,知道video大概问OA2里那两题的代码以及优化方法。
楼主OA2是循环列表插入节点以及SJF
对于循环里表插入节点,我觉得就遍历一遍,没有什么高深的算法,估计很难再优化。(有好的优化的方法也请各位帮忙告知,感激不尽)
对于SJF, 之前看过地里一个代码。 OA时也是按照那样编的。 代码如下:
  1. public double findAverage(int []request, int[]duration){
  2.                 if(request==null||duration==null||request.length==0||duration.length==0){
  3.                         return 0;
  4.                 }
  5.                 int n=request.length;
  6.                 int []end=new int[n];
  7.                 int curTime=0;. From 1point 3acres bbs
  8.                 for(int i=0;i<n;i++){
  9.                         if(i==0){
  10.                                 curTime=duration[0];
  11.                                 end[0]=duration[0];
  12.                         }else{
  13.                                 int minDuration=Integer.MAX_VALUE;
  14.                                 int curProcess=0;. 1point 3acres 璁哄潧
  15.                                 for(int j=0;j<n;j++){
  16.                                         if(end[j]!=0) continue;
  17.                                         if(request[j]<=curTime){
  18.                                                 if(duration[j]<minDuration){. From 1point 3acres bbs
  19.                                                         minDuration=duration[j];
  20.                                                         curProcess=j;
  21.                                                 }. 涓浜-涓夊垎-鍦帮紝鐙鍙戝竷
  22.                                         }else{
    . From 1point 3acres bbs
  23.                                                 break;
  24.                                         }
  25.                                 }
  26.                                 if(curProcess==0){. From 1point 3acres bbs
  27.                                         curProcess=i;
  28.                                         curTime=request[curProcess];
  29.                                 }
  30.                                 curTime=curTime+duration[curProcess];
  31.                                 end[curProcess]=curTime;. From 1point 3acres bbs
  32.                         }
  33.                 }
  34.                 int waitSum=0;
  35.                 for(int i=0;i<n;i++){
  36.                         waitSum+=end[i]-request[i]-duration[i];
  37.                 }.1point3acres缃
  38.                
  39.                 return (double)waitSum/(double)n;.1point3acres缃
  40.         }
复制代码
个人觉得这个代码很简洁,时间复杂度O(n^2)?
我自己也写了一个用priorityqueue的。代码如下:
  1. public double sjf(int[] arrive, int[] execute){. 鍥磋鎴戜滑@1point 3 acres
  2.                 PriorityQueue<Process> pq = new PriorityQueue<Process>(arrive.length, new Comparator<Process>(){
  3.                         @Override
  4.                         public int compare(Process p1,Process p2){
  5.                                 return p1.processTime-p2.processTime;
  6.                         }
  7.                 });
  8.                 int i = 0;
  9.                 int waitTime = 0;
  10.                 int curTime = 0;
  11.                 while(!pq.isEmpty() || i<arrive.length){.鐣欏璁哄潧-涓浜-涓夊垎鍦
  12.                         if(!pq.isEmpty()){
  13.                                 Process p = pq.poll();
  14.                                 waitTime += (curTime-p.arriveTime);
  15.                                 curTime += p.processTime;
  16.                                 for(;i<arrive.length;i++){
  17.                                         if(arrive[i]<=curTime){
  18.                                                 pq.offer(new Process(arrive[i],execute[i])); 鏉ユ簮涓浜.涓夊垎鍦拌鍧.
  19.                                         }
  20.                                         else{.鐣欏璁哄潧-涓浜-涓夊垎鍦
  21.                                                 break;
  22.                                         }
  23.                                 }
  24.                         }
  25.                         else{. 1point 3acres 璁哄潧
  26.                                 pq.offer(new Process(arrive[i],execute[i]));
  27.                                 curTime = arrive[i++];
  28.                         }
  29.                 }. 1point 3acres 璁哄潧
  30.                 return waitTime*1.0/arrive.length;
  31.         }
复制代码
现在对于我自己写的这个代码,我有点疑惑,到底是O(n*lgn)还是O(n^2*lgn)? 由于priorityqueue只把所有process遍历一遍,我认为是O(nlgn)的,但是呢确实是两重循环。求大家帮忙分析解答。(问题可能比较渣,但是确实不是太确定,不想video时因为这个而挂了). Waral 鍗氬鏈夋洿澶氭枃绔,

另外大家对于SJF还有什么更优化复杂度更低的算法吗?请赐教。. from: 1point3acres.com/bbs

祝大家都能有心仪的offer!!

再次感谢


. from: 1point3acres.com/bbs

补充内容 (2015-11-20 09:31):
对与priorityqueue的解法,这个代码有些问题。。。大家千万不要照抄。。。我自己后来有改,但是帖子上改不了了。。。

评分

1

查看全部评分

yanguango 发表于 2015-11-4 06:03:31 | 显示全部楼层
虽然是两层循环,但是总共就 n 次把进程放到heap 里面,每次 heap insert 是 logn, 所以是 nlogn
回复 支持 反对

使用道具 举报

 楼主| JefferyChou 发表于 2015-11-5 07:05:26 | 显示全部楼层
yanguango 发表于 2015-11-4 06:03
虽然是两层循环,但是总共就 n 次把进程放到heap 里面,每次 heap insert 是 logn, 所以是 nlogn

谢谢哥们。。。我也这么觉得
回复 支持 反对

使用道具 举报

fuji109 发表于 2015-11-5 12:36:39 | 显示全部楼层
请问 lz oa2 后多久拿到的video啊?
回复 支持 反对

使用道具 举报

 楼主| JefferyChou 发表于 2015-11-5 14:20:16 | 显示全部楼层
fuji109 发表于 2015-11-5 12:36. 涓浜-涓夊垎-鍦帮紝鐙鍙戝竷
请问 lz oa2 后多久拿到的video啊?

整整三周
回复 支持 反对

使用道具 举报

zZ-IT 发表于 2015-11-5 14:32:30 | 显示全部楼层
求问楼主做完oa2 有没有催过 recruiter  关于进度的问题
回复 支持 反对

使用道具 举报

甯甯 发表于 2015-11-5 15:26:57 | 显示全部楼层
楼主你好, 我前一阵子也是做的循环列表差节点的问题。但是有两个test没过。请问下楼主这题有什么比较tricky的地方需要注意的?我觉得我可能有些case没想到。
回复 支持 反对

使用道具 举报

 楼主| JefferyChou 发表于 2015-11-6 01:46:07 | 显示全部楼层
甯甯 发表于 2015-11-5 15:26
楼主你好, 我前一阵子也是做的循环列表差节点的问题。但是有两个test没过。请问下楼主这题有什么比较trick ...

1.列表可能为空
2.它给的不是最小节点,你得找出最小节点和最大节点
3.如果它比最小节点更小或者比最大节点更大,得把新节点加在最小节点之前,也就是最大节点之后. 鐣欏鐢宠璁哄潧-涓浜╀笁鍒嗗湴
回复 支持 反对

使用道具 举报

 楼主| JefferyChou 发表于 2015-11-6 01:48:02 | 显示全部楼层
zZ-IT 发表于 2015-11-5 14:32
求问楼主做完oa2 有没有催过 recruiter  关于进度的问题

我这个很神奇,到整整三周时候,我忍不住早上催了一下,中午另外一个邮箱就来video面试,我以为是我催来的,后来我催的那个邮箱过几天跟我说发现已经schedule interview了呀,有什么问题么。。。然后我才知道不是我催来的。
所以。。。其实催了他们是能看到的
回复 支持 反对

使用道具 举报

aiuou 发表于 2015-11-6 02:14:58 | 显示全部楼层
第一个代码复杂度也不是o(n^2)
虽然两层循环,但每个visit过的process在  if(end[j]!=0) continue; 这行都跳过去了,复杂度应该是O(n)
回复 支持 反对

使用道具 举报

zZ-IT 发表于 2015-11-6 02:20:40 | 显示全部楼层
JefferyChou 发表于 2015-11-6 01:48
我这个很神奇,到整整三周时候,我忍不住早上催了一下,中午另外一个邮箱就来video面试,我以为是我催来 ...

哦哦哦,谢谢楼主啦,祝楼主一切顺利!
回复 支持 反对

使用道具 举报

 楼主| JefferyChou 发表于 2015-11-6 03:35:49 | 显示全部楼层
aiuou 发表于 2015-11-6 02:14
第一个代码复杂度也不是o(n^2). visit 1point3acres.com for more.
虽然两层循环,但每个visit过的process在  if(end[j]!=0) continue; 这行都 ...
. From 1point 3acres bbs
但是对于每个process,它都找当前进来的process的最短的duration,正常情况是肯定不会到O(n^2)的,但是如果一个比较极端的情况。所有process都一起来,长度是倒序排列的,那每次都得遍历一遍才能找到最短duration,所以时间复杂度应该是(n^2)/2吧。。。.1point3acres缃
谢谢你的评论哈,我们可以继续探讨
回复 支持 反对

使用道具 举报

aiuou 发表于 2015-11-6 05:41:07 | 显示全部楼层
JefferyChou 发表于 2015-11-6 03:35
但是对于每个process,它都找当前进来的process的最短的duration,正常情况是肯定不会到O(n^2)的,但是如 ...

应该是你说的对,我傻了
回复 支持 反对

使用道具 举报

 楼主| JefferyChou 发表于 2015-11-6 05:49:28 | 显示全部楼层
aiuou 发表于 2015-11-6 05:41. 鍥磋鎴戜滑@1point 3 acres
应该是你说的对,我傻了

很感谢你的热心的帮忙看代码分析啊。。。 鏉ユ簮涓浜.涓夊垎鍦拌鍧.
看其他帖子知道你前两天刚video完,video过程我大概知道,但是还有什么特别需要注意的吗?他是让你分析代码还是让你重写一遍?
回复 支持 反对

使用道具 举报

aiuou 发表于 2015-11-6 06:25:58 | 显示全部楼层
JefferyChou 发表于 2015-11-6 05:49
很感谢你的热心的帮忙看代码分析啊。。。
看其他帖子知道你前两天刚video完,video过程我大概知道,但是 ...
. 鍥磋鎴戜滑@1point 3 acres
就是让你讲讲你的思路,没写code。而且只问了我一道题的思路,然后就让我问问题。
回复 支持 反对

使用道具 举报

甯甯 发表于 2015-11-9 03:27:27 | 显示全部楼层
JefferyChou 发表于 2015-11-6 01:46
1.列表可能为空
2.它给的不是最小节点,你得找出最小节点和最大节点
3.如果它比最小节点更小或者比最大 ...

多谢楼主。我再想想我的代码。

SJF那题,[0, 2, 2], [1, 10, 1]breaks the code. At line 27, if the next process starts at a time beyond the current time, it can't just pick process i. Although test cases seems to overlook that.
Plus, the previous code assumes that process starts at time 0. Hence [1], [1] won't work.
回复 支持 反对

使用道具 举报

CSBrogrammer 发表于 2015-11-9 17:02:23 | 显示全部楼层
lz你的priority queue解法不是有两个test cases没过么?
回复 支持 反对

使用道具 举报

CSBrogrammer 发表于 2015-11-9 17:16:20 | 显示全部楼层
甯甯 发表于 2015-11-9 03:27
多谢楼主。我再想想我的代码。

SJF那题,[0, 2, 2], [1, 10, 1]breaks the code. At line 27, if the  ...

是work的,你仔细看else statement within the while loop,问题不在这里,应该是lz的comparator,得handle when processes have same process time, otherwise polling the heap could cause processes out of order hence return incorrect result
回复 支持 反对

使用道具 举报

甯甯 发表于 2015-11-10 01:39:23 | 显示全部楼层
CSBrogrammer 发表于 2015-11-9 17:16
是work的,你仔细看else statement within the while loop,问题不在这里,应该是lz的comparator,得hand ...

恩我的意思是跑[0, 2, 2][1, 10, 1]的时候楼上的代码都是10/3, 但sjf应该是1/3吧。不过OA的test case里并没有考虑cpu空闲的情况。
回复 支持 反对

使用道具 举报

CSBrogrammer 发表于 2015-11-10 01:50:51 | 显示全部楼层
甯甯 发表于 2015-11-10 01:39
恩我的意思是跑[0, 2, 2][1, 10, 1]的时候楼上的代码都是10/3, 但sjf应该是1/3吧。不过OA的test case里并 ...

恩恩似乎test cases是不考虑cpu空闲的,good for us嘿嘿
回复 支持 反对

使用道具 举报

本版积分规则

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

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

关闭

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

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

custom counter

GMT+8, 2016-12-10 03:46

Powered by Discuz! X3

© 2001-2013 Comsenz Inc. Design By HUXTeam

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