San Jose各个房价 <1.5m 区域买房总结

一亩三分地论坛

 找回密码
 Sign Up 注册获取更多干货
E轮2.5亿美元融资
K12教育独角兽一起作业
北京-诚聘人工智能/教育/大数据岗
坐标湾区
Games Startup
招聘游戏开发工程师
游戏初创公司招聘工程师、UIUX Designer和游戏策划
码农求职神器Triplebyte:
不用海投
内推多家公司面试
把贵司招聘信息放这里
查看: 3501|回复: 25
收起左侧

GG热腾腾的电面

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

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

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

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

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
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记录中间结果可以剪枝
Mobile Apps Category (English)728x90
回复 支持 反对

使用道具 举报

头像被屏蔽
lll_2013 发表于 2016-9-9 02:53:47 | 显示全部楼层
提示: 作者被禁止或删除 内容自动屏蔽
回复 支持 反对

使用道具 举报

 楼主| 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好
. visit 1point3acres for more.

. From 1point 3acres bbs
回复 支持 反对

使用道具 举报

 楼主| 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. Waral 博客有更多文章,
不是整数规划,至少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
这应该是个最小费用最大流问题吧...电面考这个确实有点=。=
搞一个二分图,左边是每个人的点People,右边是 ...
. 牛人云集,一亩三分地
费用流算法是啥?有具体链接吗
回复 支持 反对

使用道具 举报

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

使用道具 举报

xihaokai1 发表于 2016-9-9 09:22:43 | 显示全部楼层
wtcupup 发表于 2016-9-9 09:08 来源一亩.三分地论坛.
费用流算法是啥?有具体链接吗

https://en.wikipedia.org/wiki/Maximum_flow_problem
回复 支持 反对

使用道具 举报

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
费用流算法是啥?有具体链接吗

. from: 1point3acres 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.. Waral 博客有更多文章,
建图的时候capacity[pi]=1,这样确保每个人最多只有1的流量汇入相当于只能选一辆车.
回复 支持 反对

使用道具 举报

本版积分规则

提醒:发帖可以选择内容隐藏,部分板块支持匿名发帖。请认真读完以下全部说明:

■隐藏内容方法: [hide=200]你想要隐藏的内容比如面经[/hide]
■意思是:用户积分低于200则看不到被隐藏的内容
■可以自行设置积分值,不建议太高(200以上太多人看不到),也不建议太低(那就没必要隐藏了)
■建议只隐藏关键内容,比如具体的面试题目、涉及隐私的信息,大部分内容没必要隐藏。
■微信/QQ/电子邮件等,为防止将来被骚扰甚至人肉,以论坛私信方式发给对方最安全。
■匿名发帖的板块和方法:http://www.1point3acres.com/bbs/thread-405991-1-1.html

关闭

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

手机版|小黑屋|一亩三分地论坛声明

custom counter

GMT+8, 2018-5-26 06:56

Powered by Discuz! X3

© 2001-2013 Comsenz Inc. Design By HUXTeam

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