黑车公司 onsite

面的是黑车公司在西雅图的办公室，他们还挺有效率的，周一onsite, 今天（周四）就发来了拒信，理由是：系统设计能力不过关。Anyway, 本来也没特别想去。献上面经，方便后来人：

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

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

想问一下楼主第二题，没弄懂意思，“假如有多个task要执行，设计实现一个task调度执行的算法”，已加米，多谢多谢！

没做题全是design啊  感觉好难

张大虾不吃鸡 发表于 2018-10-13 06:46
想问一下楼主第二题，没弄懂意思，“假如有多个task要执行，设计实现一个task调度执行的算法”，已加米，多 ...

再详细一点说：有M个task, 每个task执行时间为t1, t2, t3, ...tm, 然后机器同时只能执行N个task,其中N远小于M，问 怎么安排，才能使所有的task全部执行完所用时间最短。

konar 发表于 2018-10-13 12:43
再详细一点说：有M个task, 每个task执行时间为t1, t2, t3, ...tm, 然后机器同时只能执行N个task,其中N远 ...

多谢多谢，因为N远小于M，只想到近似解法，就是sum(T)/N？

konar 发表于 2018-10-13 12:43
再详细一点说：有M个task, 每个task执行时间为t1, t2, t3, ...tm, 然后机器同时只能执行N个task,其中N远 ...

这个在n=2的时候都是np-hard的.... t1..tm有限的情况下是背包问题

sfsttz 发表于 2018-10-17 12:27
这个在n=2的时候都是np-hard的.... t1..tm有限的情况下是背包问题

不太懂背包问题，这个题可以greedy吗? 假设N个process, M个task。
1. M个task 按时间逆序
2. N个process 用heap Pop当前total time最小的process，insert新的taks回去

求问楼主面的是什么组嘻嘻

ninjax 发表于 2018-10-19 02:41
不太懂背包问题，这个题可以greedy吗? 假设N个process, M个task。
1. M个task 按时间逆序
2. N个proces ...

我也是这样想的解决方案；但不知道N远小于M的条件怎么应用？

ninjax 发表于 2018-10-19 02:41
不太懂背包问题，这个题可以greedy吗? 假设N个process, M个task。
1. M个task 按时间逆序
2. N个proces ...

在任务3，3，2，2，2的情况下 greedy的结果是【3，2，2】 和【3，2】，max is 7。好像只能dfs啊。