一亩三分地论坛

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

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

GG热腾腾的电面

[复制链接] |试试Instant~ |关注本帖
zhucaiyi1234 发表于 2016-9-8 23:15:16 | 显示全部楼层 |阅读模式

2015(7-9月) 码农类 硕士 全职@Google - 猎头 - 技术电面 |Other在职跳槽

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

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

x
一面是Range Sum 2D mutable.
今天二面,一个中国男生。 题目有些怪,事后感觉像整数规划的问题, 直接上题。输入: an array of 2-tuple people, coordinates of people, an array of 2-tuple bikes,
怎么分配bike。分配规则以及优化的目标函数没有直接说,事后感觉一直在引导我构造一个整数规划问题,最小化 sum of distance。
整数规划是NP hard, 应该可以用贪心算法给出一个次优解。
当时晕了, 没有看出他的意图, 挂完电话后我把贪心解贴了上去,不知还算不算数。 发帖求onsite,顺便求大米!!!-google 1point3acres


鏉ユ簮涓浜.涓夊垎鍦拌鍧.

评分

1

查看全部评分

wtcupup 发表于 2016-9-8 23:49:42 | 显示全部楼层
https://leetcode.com/problems/shortest-distance-from-all-buildings/  ???
回复 支持 反对

使用道具 举报

 楼主| zhucaiyi1234 发表于 2016-9-9 00:07:27 | 显示全部楼层
wtcupup 发表于 2016-9-8 23:49-google 1point3acres
https://leetcode.com/problems/shortest-distance-from-all-buildings/  ???

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

使用道具 举报

Josh 发表于 2016-9-9 00:22:19 | 显示全部楼层
假设有k辆车,难道不是把leetcode里面那道shortest distance to all buildings改成求前k个shortest distance吗?这样sum of distance肯定是最小的啊
回复 支持 反对

使用道具 举报

 楼主| zhucaiyi1234 发表于 2016-9-9 00:30:01 | 显示全部楼层
Josh 发表于 2016-9-9 00:22
假设有k辆车,难道不是把leetcode里面那道shortest distance to all buildings改成求前k个shortest distanc ...

不大一样, 一个人可能里多个车最近,这是后怎么选。
还有假设有AB两人, 1,2 车, A 离1,2 比B都近, A怎么选?
A可以选1,2中离他最近的,把剩下的留给B,但是这样也不是最优的。
回复 支持 反对

使用道具 举报

fatalme 发表于 2016-9-9 00:57:14 来自手机 | 显示全部楼层
不是整数规划,至少minimum weight perfect matching

补充内容 (2016-9-9 01:33):
可以解决
回复 支持 反对

使用道具 举报

Josh 发表于 2016-9-9 00:59:56 | 显示全部楼层
zhucaiyi1234 发表于 2016-9-9 00:30
不大一样, 一个人可能里多个车最近,这是后怎么选。
还有假设有AB两人, 1,2 车, A 离1, ...

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

使用道具 举报

lll_2013 发表于 2016-9-9 02:53:47 | 显示全部楼层
我不知道我有没有理解错题意,person[n],表示在人在coordinate上坐标,bike[n]表示 bike在coordinate上坐标 根据coordinate sort person和bike
人1 车1 车2 人2   --》 (人1 车1) (人2 车2)
人1 人2 车1 车2 -> (人1 车1) (人2 车2). 1point3acres.com/bbs
人1 车1 车2 人2 --> (人1 车1) (人2 车2). 1point3acres.com/bbs
从上面就可以看出无论怎么样要最短距离,肯定是安排坐标上最先出现的人和车组合。不知道对不对,不对的话指出,谢谢



. 鐣欏鐢宠璁哄潧-涓浜╀笁鍒嗗湴补充内容 (2016-9-8 13:58):
上面是1D。如果是2D,就先按照(0,0)画圆,根据r 排序person和bike。然后第一个出现person的地方花圆找第一个出现的车,一次类推
回复 支持 反对

使用道具 举报

 楼主| zhucaiyi1234 发表于 2016-9-9 04:24:45 | 显示全部楼层
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好



回复 支持 反对

使用道具 举报

 楼主| zhucaiyi1234 发表于 2016-9-9 04:27:36 | 显示全部楼层
lll_2013 发表于 2016-9-9 02:53
我不知道我有没有理解错题意,person[n],表示在人在coordinate上坐标,bike[n]表示 bike在coordinate上坐 ...

图是2D的,
1D 为什么从 做到右而不从右到左 , 两种方向得到的结果应该不一样。
回复 支持 反对

使用道具 举报

 楼主| zhucaiyi1234 发表于 2016-9-9 04:27:49 | 显示全部楼层
fatalme 发表于 2016-9-9 00:57
不是整数规划,至少minimum weight perfect matching
. 鐣欏鐢宠璁哄潧-涓浜╀笁鍒嗗湴
补充内容 (2016-9-9 01:33):

可以详细说一下么?
回复 支持 反对

使用道具 举报

dydcfg 发表于 2016-9-9 05:34:16 | 显示全部楼层
这应该是个最小费用最大流问题吧...电面考这个确实有点=。=
搞一个二分图,左边是每个人的点People,右边是每个车的点Bike,最左边是源点s,最右边是汇点t.通过边容量限制每个人只能有一辆车,每辆车只能被一个拥有(s到每个People容量为1,每个Bike到t的容量为1).中间边的费用就是车的距离.然后用费用流算法搞搞就能出最优结果.
回复 支持 反对

使用道具 举报

fatalme 发表于 2016-9-9 06:36:57 来自手机 | 显示全部楼层
差不多,同意楼上的。
回复 支持 反对

使用道具 举报

wtcupup 发表于 2016-9-9 09:08:07 | 显示全部楼层
dydcfg 发表于 2016-9-9 05:34
这应该是个最小费用最大流问题吧...电面考这个确实有点=。=. Waral 鍗氬鏈夋洿澶氭枃绔,
搞一个二分图,左边是每个人的点People,右边是 ...

费用流算法是啥?有具体链接吗
回复 支持 反对

使用道具 举报

johnjavabean 发表于 2016-9-9 09:21:53 | 显示全部楼层
二分图匹配
回复 支持 反对

使用道具 举报

xihaokai1 发表于 2016-9-9 09:22:43 | 显示全部楼层
回复 支持 反对

使用道具 举报

xihaokai1 发表于 2016-9-9 09:23:17 | 显示全部楼层
dydcfg 发表于 2016-9-9 05:34. From 1point 3acres bbs
这应该是个最小费用最大流问题吧...电面考这个确实有点=。=
搞一个二分图,左边是每个人的点People,右边是 ...

如何控制变容量限制每人只有一辆车呢?
回复 支持 反对

使用道具 举报

dydcfg 发表于 2016-9-9 09:30:57 | 显示全部楼层
wtcupup 发表于 2016-9-9 09:08. 1point 3acres 璁哄潧
费用流算法是啥?有具体链接吗

http://courses.csail.mit.edu/6.8 ... -minCostFlowAlg.pdf
.鐣欏璁哄潧-涓浜-涓夊垎鍦
这里有份讲义~
回复 支持 反对

使用道具 举报

dydcfg 发表于 2016-9-9 09:33:09 | 显示全部楼层
xihaokai1 发表于 2016-9-9 09:23
如何控制变容量限制每人只有一辆车呢?

假设源点是s,然后每个人的点是p1,p2...pn.
建图的时候capacity[pi]=1,这样确保每个人最多只有1的流量汇入相当于只能选一辆车.
回复 支持 反对

使用道具 举报

本版积分规则

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

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

关闭

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

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

custom counter

GMT+8, 2016-12-3 22:03

Powered by Discuz! X3

© 2001-2013 Comsenz Inc. Design By HUXTeam

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