亚马逊-群面-一点进阶的idea

看了好多帖子，也不知道onsite的原题到底是啥。。。
不知楼主可否提供一个详细描述了原题的链接？多谢

楼主第二问，是对每个order所有可能的shippingCost里找时间最短的路线对应的productInventory吗？如果是这样，我觉得并不合理呀。例如(括号里是资源数)：当前order(4)可以选productInventory1(5)和productInventory2(4)，productInventory1运输时间短分配给order。下一个order(5)如果只能选productInventory1(1)，结果由于资源给了上一个order，当前order就不满足了。
但是按照每个order能选资源的quantity从大到小排也不一定是最优的

bigpea 发表于 2017-1-6 06:33
楼主第二问，是对每个order所有可能的shippingCost里找时间最短的路线对应的productInventory吗？如果是这 ...

这题估计只能暴力解才能最佳了

bigpea 发表于 2017-1-6 06:33
楼主第二问，是对每个order所有可能的shippingCost里找时间最短的路线对应的productInventory吗？如果是这 ...

你的问题特别的好！有很多人都想不出反例。你说的就是反例里最重要的一种情况。这个是可以和考官讨论的，让他知道你知道有反例。
怎么优化看自己。我给你一个建议，看看你能不能明白：全局排序，局部dfs。
dfs是指数增长，但是如果n=5左右，以现在的计算能力，根本不是个问题。同时加上我帖子上给出的几种优化方法。个人认为可以再极大程度上趋近optimal。但是肯定不可能是是optimal。
（这些东西都很over qualify，不需要全部准备。我当时讲了所有东西。其中一个人都跟不上我的节奏。所以我觉得就说其中一两个“痛点”就可以。）

yysgkgtc511 发表于 2017-1-6 10:21
这题估计只能暴力解才能最佳了

有个人就吃亏在说 “这个是最优解”
这个不是最优的。onsite的时候，不要碰这个雷区。
就说，这个办法可以“improve performance”就可以了
good luck

novking 发表于 2017-1-6 22:34
你的问题特别的好！有很多人都想不出反例。你说的就是反例里最重要的一种情况。这个是可以和考官讨论的， ...

谢谢楼主回复。我也想到了一些解决方法，不过onsite的时候coding会比较复杂。
还想再问一下，什么样的order算是delay呀？有起始时间吗？

有一点对题目没理解，按照我们看到的面经，大多数的描述都是对于每个order，都会调一遍第一问的函数得到一个list，然后在list中根据你的选择找到最合适的shippingcost进行运输？那不是在适当的环节用sort等方法选出最大或者最小就可以了么？没有懂为什么面经里都在说用pq，感觉我对题目什么地方理解有误？

smjjj1992 发表于 2017-1-7 07:52
有一点对题目没理解，按照我们看到的面经，大多数的描述都是对于每个order，都会调一遍第一问的函数得到一 ...

我认为，这个类似于找前top k 的最大/最小值，你可以分析下使用sort 和heap的时间复杂度。

bigpea 发表于 2017-1-7 02:48
谢谢楼主回复。我也想到了一些解决方法，不过onsite的时候coding会比较复杂。
还想再问一下，什么样的or ...

按最基本的方法写。然后时间来得及就写function的方法一点点往上加。有点像js的callback的感觉。
order有deadline。这个是你问的问题吗