一亩三分地论坛

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

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

新鲜狗狗店面,感觉是跪了啊。。。

[复制链接] |试试Instant~ |关注本帖
tcswdys 发表于 2016-9-1 03:05:53 | 显示全部楼层 |阅读模式

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

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

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

x
刚面完,感觉是跪了。。。。第二问说思路的时候估计思路不对,对面一直说不懂。。。
写到45min的时候就说到时间啦就挂电话。。也不让问问题或者再写一会儿,明明我感觉再一下应该可以出来的。。。
来上问题吧。。。一条街上有n个供热站,每个覆盖m的范围。给一个数组里面有每个房子的位置,都是一维的,要求每个房子都被供热站覆盖到。第一个问给定m,求最小的n。第二问给定n,求最小的m
祝好运

评分

1

查看全部评分

本帖被以下淘专辑推荐:

  • · google|主题: 57, 订阅: 4
zhan8803705 发表于 2016-9-1 03:13:50 | 显示全部楼层
楼主可以说说思路吗,我一个小时后面
回复 支持 反对

使用道具 举报

 楼主| tcswdys 发表于 2016-9-1 03:16:44 | 显示全部楼层
zhan8803705 发表于 2016-9-1 03:13
楼主可以说说思路吗,我一个小时后面

第二问一直在提示说用第一问。。。第一问贪心已经就行
回复 支持 反对

使用道具 举报

hxtang 发表于 2016-9-1 03:21:26 | 显示全部楼层
第一问greedy第二问递归?

补充内容 (2016-9-1 08:44):
第2问递归可以优化成2D DP,更新m[i, l]计算第1个到第i个房子放l个供热站需要的最小的m.
这个做法理论上可能没有二分搜索好(但因为剪枝实际上可能还是够快),不过算一种标(无)准(聊)解法...
回复 支持 反对

使用道具 举报

hxtang 发表于 2016-9-1 03:25:00 | 显示全部楼层
tcswdys 发表于 2016-9-1 03:16
第二问一直在提示说用第一问。。。第一问贪心已经就行

用第一问的话想到一个略傻的方法
把房子pairwise的距离从小到大排序,作为candidate的m值。然后一个个试能不能用n个供热站cover
回复 支持 反对

使用道具 举报

ytsr 发表于 2016-9-1 03:35:53 | 显示全部楼层
tcswdys 发表于 2016-9-1 03:16. more info on 1point3acres.com
第二问一直在提示说用第一问。。。第一问贪心已经就行

第一问greedy就行,很直接。
第二问直接考虑的话也有很多奇奇怪怪的算法,如果面试官提示就用第一问的话那就binary search就行了。
假如第一问的答案是 n=f(m), 这f(m)肯定是递减的, 那第二问就是找最小的满足 f(m)<=n 的m。这种算法要调用第一问多次,是不是最优就不知道了。不过既然面试官要用第一问的结果,应该不会效率太差吧。。。
回复 支持 反对

使用道具 举报

aangel 发表于 2016-9-1 05:50:30 | 显示全部楼层
多谢楼主分享,想进一步问一下题意,输入是提供房子的一维坐标,比如[1,3,5,7,9,10]. 涓浜-涓夊垎-鍦帮紝鐙鍙戝竷
这里的供热站n个和m米的覆盖范围,请问供热站是可以任意选取地方建设的吗?如果供热站是可以任意移动的,那两问都用贪心就好了啊,
如果供热站的是给定位置的,即供热站的位置坐标是定死的,那么感觉贪心也可以做啊,
另外这个供热覆盖m米指的应该是前后吧,比如一个供热站坐标是1,m为3,那么这个供热站覆盖的房子可以[-2,4],对吗?
回复 支持 反对

使用道具 举报

ytsr 发表于 2016-9-1 05:52:27 | 显示全部楼层
aangel 发表于 2016-9-1 05:50
多谢楼主分享,想进一步问一下题意,输入是提供房子的一维坐标,比如[1,3,5,7,9,10]
这里的供热站n个和m米 ...

第二问怎么贪心?
回复 支持 反对

使用道具 举报

xpli521 发表于 2016-9-1 07:53:49 | 显示全部楼层
hxtang 发表于 2016-8-31 12:25
用第一问的话想到一个略傻的方法
把房子pairwise的距离从小到大排序,作为candidate的m值。然后一个个试 ...

我最开始想到的大致也是这样, 但好像不行。。这样只能保证一个供电站cover至少2个房子,如果供电站总数n很小,房子很多,那么一个供电站需要cover>=2个房子。。
回复 支持 反对

使用道具 举报

hxtang 发表于 2016-9-1 08:06:33 | 显示全部楼层
xpli521 发表于 2016-9-1 07:53. visit 1point3acres.com for more.
我最开始想到的大致也是这样, 但好像不行。。这样只能保证一个供电站cover至少2个房子,如果供电站总数n ...

如果m是房子i到j的距离,那么m自动cover了i到j之间的所有房子,cover的房子可能是>2的。
比如i是第一幢房子,j是最后一幢房子,那么n=1也没关系,因为m cover了所有房子。
最后搜具体的m值的时候像ytsr说的可以二分。
回复 支持 反对

使用道具 举报

xpli521 发表于 2016-9-1 08:07:09 | 显示全部楼层
Binary search感觉是靠谱的,如果一直要调用第一问的话。。
回复 支持 反对

使用道具 举报

xpli521 发表于 2016-9-1 08:08:25 | 显示全部楼层
hxtang 发表于 2016-8-31 17:06
如果m是房子i到j的距离,那么m自动cover了i到j之间的所有房子,cover的房子可能是>2的。
比如i是第一幢 ...

哦哦你说的是i到j呀,我以为说的是i到i+1呢,那应该可以
回复 支持 反对

使用道具 举报

hkc593 发表于 2016-9-1 08:23:18 | 显示全部楼层
第一问为什么不是两个房子的最大间距除以吗?
回复 支持 反对

使用道具 举报

dfsocean 发表于 2016-9-1 10:33:29 | 显示全部楼层
hkc593 发表于 2016-9-1 08:23
第一问为什么不是两个房子的最大间距除以吗?

因为并不需要覆盖整个街道吧
回复 支持 反对

使用道具 举报

lll_2013 发表于 2016-9-1 11:04:26 | 显示全部楼层
第二题可不可以直接通过sort后的house[size], 得到最大m = house[size - 1] - house[0] / n,然后根据当前m 来iterate house这个数组,把边界往内部缩小,遍历完之后update 这个m
回复 支持 反对

使用道具 举报

y2323k23 发表于 2016-9-1 13:11:17 | 显示全部楼层
请问下楼主, 第一题贪心怎么做的呢
回复 支持 反对

使用道具 举报

mazytes 发表于 2016-9-1 13:36:04 | 显示全部楼层
第一问给房子排序,从左扫到右就好。第二问二分查找,先假设一个m,用第一问算n,n富裕了减小m,否则增加
回复 支持 反对

使用道具 举报

wtcupup 发表于 2016-9-1 13:37:57 | 显示全部楼层
lll_2013 发表于 2016-9-1 11:04
第二题可不可以直接通过sort后的house, 得到最大m = house - house[0] / n,然后根据当前m 来iterate house ...

没看懂 求具体代码
回复 支持 反对

使用道具 举报

mazytes 发表于 2016-9-1 13:38:10 | 显示全部楼层
OA是面经的意思吗?
回复 支持 反对

使用道具 举报

yuranrobin 发表于 2016-10-25 09:49:16 | 显示全部楼层
这么复杂 根本不会做啊
回复 支持 反对

使用道具 举报

本版积分规则

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

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

关闭

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

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

custom counter

GMT+8, 2016-12-3 04:17

Powered by Discuz! X3

© 2001-2013 Comsenz Inc. Design By HUXTeam

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