一亩三分地论坛

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

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

Amazon Shortest Job First 题目讨论贴

[复制链接] |试试Instant~ |关注本帖
zZ-IT 发表于 2015-11-23 03:44:45 | 显示全部楼层 |阅读模式

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

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

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

x
楼主最近拿到了video, OA2遇到的是 SJF 和 day change两题, 对于 SJF 这题,当时用的while循环 加 priorityQueue做的,时间复杂度应该是 O(nlogn), 也见到过地里有人讨论过这题,但都是在题目细节上,想请教一下地里的大神们, SJF这题 在算法上还有没有更优的解法? 如果不用priorityQueue, 还可以怎么写达到nlogn的时间复杂度,如果没有最优的解法了,到时候如果问到优化的话,应该怎么回答? 另外,有同样做这题的同学当时做的时候题目里有提到说 cpu不会空闲和 这种sample 怎么处理[0,0][10,1] 的问题嘛,谢谢大家了!!!

对于day change 个人认为o(n) in place 的方法就是最优了,也不能优化了吧,如果有,也欢迎大家讨论~~~
祝大家都能拿到video 和 offer!
s_asolo 发表于 2015-11-23 06:41:28 | 显示全部楼层
请问楼主day change那道题k天长度为n的数组怎么能直接一步用o(n)的时间算出第K天的样子?想了好久想不出来。
回复 支持 反对

使用道具 举报

 楼主| zZ-IT 发表于 2015-11-23 07:22:34 | 显示全部楼层
s_asolo 发表于 2015-11-23 06:41
请问楼主day change那道题k天长度为n的数组怎么能直接一步用o(n)的时间算出第K天的样子?想了好久想不出来 ...

哦哦 我说的不明确, 其实题目中有提到数组的长度是 7 还是 8, 实际写的时候也是用两层循环写,所以相当于O(k), 更准确说就是O(kn), 然后空间上可以做到in place
回复 支持 反对

使用道具 举报

2446733 发表于 2015-11-23 07:43:38 | 显示全部楼层
LZ约的几号Video?
回复 支持 反对

使用道具 举报

 楼主| zZ-IT 发表于 2015-11-23 08:29:24 | 显示全部楼层
2446733 发表于 2015-11-23 07:43
LZ约的几号Video?

下周二 字数字数
回复 支持 反对

使用道具 举报

2446733 发表于 2015-11-23 09:06:00 | 显示全部楼层
zZ-IT 发表于 2015-11-23 08:29. 涓浜-涓夊垎-鍦帮紝鐙鍙戝竷
下周二 字数字数

等LZ面经哈 跟你的题一模一样。。
回复 支持 反对

使用道具 举报

乳大未必有奶 发表于 2015-11-23 10:30:21 | 显示全部楼层
祝lz的video顺利拿下offer~~lz说的day change是什么题目?可不可以详细的说一下题目,我总结的面经里没有这道题额,还是说法不一样~
回复 支持 反对

使用道具 举报

nostal 发表于 2015-11-23 10:39:33 | 显示全部楼层
有同学说他注意到了不考虑cpu空闲  http://www.1point3acres.com/bbs/forum.php?mod=viewthread&tid=144891&page=9#pid2076010。lz, 我看地理的面经里面写的SJF都是上来就直接执行第一个,那arrTime=[0, 0],excuTime = [2,1]这种情况怎么办?

补充内容 (2015-11-23 10:44):. Waral 鍗氬鏈夋洿澶氭枃绔,
刚看到lz也在问这种情况~
回复 支持 反对

使用道具 举报

 楼主| zZ-IT 发表于 2015-11-23 13:42:37 | 显示全部楼层
乳大未必有奶 发表于 2015-11-23 10:30.1point3acres缃
祝lz的video顺利拿下offer~~lz说的day change是什么题目?可不可以详细的说一下题目,我总结的面经里没有这 ...

之前的题 楼下的链接就有
回复 支持 反对

使用道具 举报

 楼主| zZ-IT 发表于 2015-11-23 13:43:25 | 显示全部楼层
nostal 发表于 2015-11-23 10:39. 1point 3acres 璁哄潧
有同学说他注意到了不考虑cpu空闲  http://www.1point3acres.com/bbs/forum.php?mod=viewthread&tid=144891 ...

同问...你觉得还有没有什么优化的方法 对于 SFJ
回复 支持 反对

使用道具 举报

 楼主| zZ-IT 发表于 2015-11-23 13:44:26 | 显示全部楼层
2446733 发表于 2015-11-23 09:06. 鐣欏鐢宠璁哄潧-涓浜╀笁鍒嗗湴
等LZ面经哈 跟你的题一模一样。。

Okey! 如果我忘掉了,记得私信我, 还有啊, 你觉得SJF 有什么优化的方法嘛,讨论一下
回复 支持 反对

使用道具 举报

nostal 发表于 2015-11-23 21:08:56 | 显示全部楼层
我觉得最优就是priority queue了
回复 支持 反对

使用道具 举报

 楼主| zZ-IT 发表于 2015-11-24 06:47:26 | 显示全部楼层
nostal 发表于 2015-11-23 21:08.鐣欏璁哄潧-涓浜-涓夊垎鍦
我觉得最优就是priority queue了

嗯嗯 谢谢你啦 估计是没有更优的了~~
回复 支持 反对

使用道具 举报

 楼主| zZ-IT 发表于 2015-11-24 06:49:41 | 显示全部楼层
2446733 发表于 2015-11-23 09:06
等LZ面经哈 跟你的题一模一样。。

刚 HR 给我发邮件讲明天 interviewer有事,要给我推到12月份了 现在还不能确定最终是几号,如果你在我前面面了 估计得参考你的面经了....一起加油!!
回复 支持 反对

使用道具 举报

tianqing705 发表于 2016-2-18 00:31:05 | 显示全部楼层
day change可以O(n)吗?我怎么想都觉得是O(n * days)啊?还有也想不到怎么in place,lz可以详细说一下解法吗?

补充内容 (2016-2-18 00:59):
忽略我,下一楼已经想明白了=。=
回复 支持 反对

使用道具 举报

tianqing705 发表于 2016-2-18 00:34:50 | 显示全部楼层
in place就是用一个temp变量存每次的cells[i - 1]吗?但是时间复杂度不是也应该天数和cell数组两个loop?

补充内容 (2016-2-18 00:59):
突然看到有的帖子说cells大小固定是8个=。=好吧,懂了。。。
回复 支持 反对

使用道具 举报

本版积分规则

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

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

关闭

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

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

custom counter

GMT+8, 2016-12-5 08:53

Powered by Discuz! X3

© 2001-2013 Comsenz Inc. Design By HUXTeam

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