GG热腾腾的电面

一面是Range Sum 2D mutable.
今天二面，一个中国男生。 题目有些怪，事后感觉像整数规划的问题， 直接上题。输入： an array of 2-

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

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

完电话后我把贪心解贴了上去，不知还算不算数。 发帖求onsite，顺便求大米！！！

wtcupup 发表于 2016-9-8 23:49
https://leetcode.com/problems/shortest-distance-from-all-buildings/  ???

不是，LC这题是只要建一个building， 我面的那题有多人，多自行车。每人分配一辆车似的人到车的距离之和最小。
应该是一个组合优化问题中的assignment problem。
https://en.wikipedia.org/wiki/Assignment_problem

这应该是个最小费用最大流问题吧...电面考这个确实有点=。=
搞一个二分图,左边是每个人的点People,右边是每个车的点Bike,最左边是源点s,最右边是汇点t.通过边容量限制每个人只能有一辆车,每辆车只能被一个拥有(s到每个People容量为1,每个Bike到t的容量为1).中间边的费用就是车的距离.然后用费用流算法搞搞就能出最优结果.

https://leetcode.com/problems/shortest-distance-from-all-buildings/  ???

假设有k辆车，难道不是把leetcode里面那道shortest distance to all buildings改成求前k个shortest distance吗？这样sum of distance肯定是最小的啊

Josh 发表于 2016-9-9 00:22
假设有k辆车，难道不是把leetcode里面那道shortest distance to all buildings改成求前k个shortest distanc ...

不大一样， 一个人可能里多个车最近，这是后怎么选。
还有假设有ＡＢ两人，　１，２　车，　Ａ　离１，２　比Ｂ都近，　Ａ怎么选？
Ａ可以选１，２中离他最近的，把剩下的留给Ｂ，但是这样也不是最优的。

不是整数规划，至少minimum weight perfect matching

补充内容 (2016-9-9 01:33):
可以解决

可以解决

zhucaiyi1234 发表于 2016-9-9 00:30
不大一样， 一个人可能里多个车最近，这是后怎么选。
还有假设有ＡＢ两人，　１，２　车，　Ａ　离１， ...

我懂你的意思了。那真的蛮难的。我能想到的就是backtracking找出所有permutation并计算距离和。backtracking的时候可以用hashmap记录中间结果可以剪枝

lll_2013 发表于 2016-9-9 02:53
我不知道我有没有理解错题意，person[n]，表示在人在coordinate上坐标，bike[n]表示 bike在coordinate上坐 ...

test case
人的坐标 [0,10], 车 [-10, 9]
按你的方法，人1 陪车2， 人2 配车1。 这样显然没有人 1 配车1， 人2配车2好