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

谢谢大家点进来。最近人品还行，拿了amazon 的video，看了很多帖子，知道video大概问OA2里那两题的代码以及优化方法。
楼主OA2是循环列表插入节点以及SJF
对于循环里表插入节点，我觉得就遍历一遍，没有什么高深的算法，估计很难再优化。（有好的优化的方法也请各位帮忙告知，感激不尽）
对于SJF， 之前看过地里一个代码。

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

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

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

JefferyChou 发表于 2015-11-6 01:46
1.列表可能为空
2.它给的不是最小节点，你得找出最小节点和最大节点
3.如果它比最小节点更小或者比最大 ...

LZ请问这样写可以满足后2条吗？没有单独去找最大点和最小点。求指点

do {
                        if (target >= cur.val && target <= cur.next.val)
                                break;
                        if (cur.val > cur.next.val
                                        && (target < cur.next.val || target > cur.val))
                                break;
                        cur = cur.next;
                } while (cur != head);

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 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.

虽然是两层循环，但是总共就 n 次把进程放到heap 里面，每次 heap insert 是 logn， 所以是 nlogn

yanguango 发表于 2015-11-4 06:03
虽然是两层循环，但是总共就 n 次把进程放到heap 里面，每次 heap insert 是 logn， 所以是 nlogn

谢谢哥们。。。我也这么觉得

请问 lz oa2 后多久拿到的video啊？

fuji109 发表于 2015-11-5 12:36
请问 lz oa2 后多久拿到的video啊？

整整三周

求问楼主做完oa2 有没有催过 recruiter  关于进度的问题

楼主你好， 我前一阵子也是做的循环列表差节点的问题。但是有两个test没过。请问下楼主这题有什么比较tricky的地方需要注意的？我觉得我可能有些case没想到。

甯甯 发表于 2015-11-5 15:26
楼主你好， 我前一阵子也是做的循环列表差节点的问题。但是有两个test没过。请问下楼主这题有什么比较trick ...

1.列表可能为空
2.它给的不是最小节点，你得找出最小节点和最大节点
3.如果它比最小节点更小或者比最大节点更大，得把新节点加在最小节点之前，也就是最大节点之后

zZ-IT 发表于 2015-11-5 14:32
求问楼主做完oa2 有没有催过 recruiter  关于进度的问题

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

第一个代码复杂度也不是o(n^2)
虽然两层循环，但每个visit过的process在  if(end[j]!=0) continue; 这行都跳过去了，复杂度应该是O(n)