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

JefferyChou 发表于 2015-11-6 01:48
我这个很神奇，到整整三周时候，我忍不住早上催了一下，中午另外一个邮箱就来video面试，我以为是我催来 ...

哦哦哦，谢谢楼主啦，祝楼主一切顺利！

aiuou 发表于 2015-11-6 02:14
第一个代码复杂度也不是o(n^2)
虽然两层循环，但每个visit过的process在  if(end[j]!=0) continue; 这行都 ...

但是对于每个process，它都找当前进来的process的最短的duration，正常情况是肯定不会到O(n^2)的，但是如果一个比较极端的情况。所有process都一起来，长度是倒序排列的，那每次都得遍历一遍才能找到最短duration,所以时间复杂度应该是(n^2)/2吧。。。
谢谢你的评论哈，我们可以继续探讨

JefferyChou 发表于 2015-11-6 03:35
但是对于每个process，它都找当前进来的process的最短的duration，正常情况是肯定不会到O(n^2)的，但是如 ...

应该是你说的对，我傻了

aiuou 发表于 2015-11-6 05:41
应该是你说的对，我傻了

很感谢你的热心的帮忙看代码分析啊。。。
看其他帖子知道你前两天刚video完，video过程我大概知道，但是还有什么特别需要注意的吗？他是让你分析代码还是让你重写一遍？

JefferyChou 发表于 2015-11-6 05:49
很感谢你的热心的帮忙看代码分析啊。。。
看其他帖子知道你前两天刚video完，video过程我大概知道，但是 ...

就是让你讲讲你的思路，没写code。而且只问了我一道题的思路，然后就让我问问题。

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.

lz你的priority queue解法不是有两个test cases没过么？

甯甯 发表于 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

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空闲的情况。

甯甯 发表于 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嘿嘿