要回国了,写个简单的总结吧。

一亩三分地论坛

 找回密码
 Sign Up 注册获取更多干货
码农求职神器Triplebyte:
不用海投
内推多家公司面试
坐标湾区
Games Startup
招聘游戏开发工程师
游戏初创公司招聘工程师、UIUX Designer和游戏策划
把贵司招聘信息放这里
系统
18分钟前
系统
19分钟前
系统
25分钟前
系统
28分钟前
系统
28分钟前
系统
29分钟前
系统
33分钟前
系统
34分钟前
系统
1小时前
全站
Warald 说: MemorialDay大礼包之七:【新功能】每日答题,答对了有大米奖励!加上每日登陆和每日签到,每天可以拿3颗大米!
1小时前
系统
1小时前
系统
1小时前
系统
1小时前
系统
1小时前
系统
1小时前
系统
1小时前
系统
1小时前
系统
1小时前
系统
1小时前
全站
Warald 说: MemorialDay大礼包之五:【新功能】高级模式发帖,图片框里添加“大图片上传”,upto20张X10M
2小时前
系统
2小时前
系统
2小时前
系统
2小时前
系统
2小时前
系统
2小时前
系统
2小时前
系统
2小时前
系统
2小时前
系统
2小时前
系统
2小时前
系统
2小时前
系统
2小时前
系统
2小时前
系统
2小时前
系统
2小时前
系统
2小时前
系统
2小时前
系统
2小时前
系统
2小时前
系统
2小时前
系统
2小时前
系统
2小时前
系统
2小时前
系统
2小时前
系统
2小时前
系统
2小时前
系统
2小时前
系统
2小时前
系统
2小时前
系统
2小时前
系统
2小时前
系统
2小时前
系统
2小时前
系统
2小时前
系统
2小时前
系统
2小时前
系统
2小时前
系统
2小时前
系统
2小时前
系统
2小时前
系统
2小时前
系统
2小时前
系统
2小时前
系统
2小时前
系统
2小时前
系统
2小时前
全站
Warald 说: MemorialDay大礼包之五:【新功能】小喇叭可以点击“发布”,可以在全局、板块或者帖子里发
2小时前
系统
2小时前
系统
2小时前
系统
2小时前
系统
2小时前
系统
2小时前
全站
Warald 说: MemorialDay大礼包之四:【新功能】主题列表页显示图片,欢迎上图
2小时前
系统
2小时前
系统
3小时前
系统
3小时前
系统
3小时前
系统
3小时前
系统
3小时前
系统
3小时前
全站
3小时前
系统
3小时前
系统
3小时前
系统
3小时前
系统
3小时前
系统
3小时前
系统
3小时前
全站
Warald 说: MemorialDay大礼包之二:【新功能】论坛开启用户全局威望值,每楼右上方均可投票。
3小时前
全站
Warald 说: MemorialDay大礼包之一:【新功能】发帖后,可以邀请朋友参与讨论(自动功能)
3小时前
查看: 968|回复: 6
收起左侧

[算法题] 请问这道FB面经题怎么做

[复制链接] |试试Instant~ |关注本帖
我的人缘0
milanelllo13 发表于 2015-7-5 14:27:06 | 显示全部楼层 |阅读模式
  此人很可信:
 
0% (暂未有人投票) 【我投】
  此人瞎逼逼:
 
0% (暂未有人投票) 【我投】

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

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

x
本帖最后由 milanelllo13 于 2015-7-5 14:28 编辑

Given set of points in 2d grid space. Find a grid point such that sum of distance  from all the points to this common point is minimum.    (昨天在一位同学发的面经总结看到的)。想请教一下解法~  谢谢!

                                       
                                
                        
               


上一篇:CC189 出来了
下一篇:第一次刷题,刷完难度2后的困惑
我的人缘0
stellari 发表于 2015-7-5 14:48:18 | 显示全部楼层
  此人很可信:
 
0% (暂未有人投票) 【我投】
  此人瞎逼逼:
 
0% (暂未有人投票) 【我投】
这道题你得先确认“distance”是怎么定义的。比如:是Euclidean distance还是Taxicab distance ? 如果是后者的话,common point取(med(xi), med(yi))即可。其中med(Ni) 代表所有坐标点第N维上的值的中位数。

回复 支持 反对

使用道具 举报

全球28万学生4.7分推荐
我的人缘0
 楼主| milanelllo13 发表于 2015-7-5 14:52:51 | 显示全部楼层
  此人很可信:
 
0% (暂未有人投票) 【我投】
  此人瞎逼逼:
 
0% (暂未有人投票) 【我投】
stellari 发表于 2015-7-5 14:48
这道题你得先确认“distance”是怎么定义的。比如:是Euclidean distance还是Taxicab distance ? 如果是后 ...

谢谢!那如果是Euclidean distance 有不brute force的方法吗?
回复 支持 反对

使用道具 举报

我的人缘0
stellari 发表于 2015-7-5 16:00:55 | 显示全部楼层
  此人很可信:
 
0% (暂未有人投票) 【我投】
  此人瞎逼逼:
 
0% (暂未有人投票) 【我投】
milanelllo13 发表于 2015-7-5 14:52
谢谢!那如果是Euclidean distance 有不brute force的方法吗?

在Euclidean情况下,这样的点称为“几何中位点”,又叫“托里拆利点”。如果不加任何限制,无法用确定性的算法找到。一般只能借助各种逼近算法求近似值。不过具体到这道题,看样子“这个点必须在某个格点位置上”,或者甚至“这个点必须是某个set中的点”(是否如此要向面试官确认清楚)。在这些限制下,可能是有确定性的算法可以做的。
回复 支持 反对

使用道具 举报

我的人缘0
zhuli19901106 发表于 2015-7-6 00:18:37 | 显示全部楼层
  此人很可信:
 
0% (暂未有人投票) 【我投】
  此人瞎逼逼:
 
0% (暂未有人投票) 【我投】
本帖最后由 zhuli19901106 于 2015-7-6 00:23 编辑
stellari 发表于 2015-7-5 16:00
在Euclidean情况下,这样的点称为“几何中位点”,又叫“托里拆利点”。如果不加任何限制,无法用确定性 ...

看见这个猛然想起了POJ上的一道老题,当时搜的关键字是费马点。
http://poj.org/problem?id=2420
就是用你说的随机算法,四个方向搜,一边不断选取更优解,一边缩小步长,直到符合精度要求为止。
回复 支持 反对

使用道具 举报

我的人缘0
readman 发表于 2015-7-6 03:14:21 | 显示全部楼层
  此人很可信:
 
0% (暂未有人投票) 【我投】
  此人瞎逼逼:
 
0% (暂未有人投票) 【我投】
本帖最后由 readman 于 2015-7-6 03:17 编辑
zhuli19901106 发表于 2015-7-6 00:18
看见这个猛然想起了POJ上的一道老题,当时搜的关键字是费马点。
http://poj.org/problem?id=2420
就是 ...

这个, as far as i know...在set就不用离散化了吧.., 做个多边形, 圈起来, 然后三角化, 挨个试试...
回复 支持 反对

使用道具 举报

我的人缘0
road 发表于 2015-7-6 04:33:25 | 显示全部楼层
  此人很可信:
 
0% (暂未有人投票) 【我投】
  此人瞎逼逼:
 
0% (暂未有人投票) 【我投】
Integer (quadratic)programming problem.
可以先用quadratic programming 快速搜索出一个大概的解 在周围grid point 线性寻找
回复 支持 反对

使用道具 举报

游客
请先登录

本版积分规则

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

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

关闭

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

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

custom counter

GMT+8, 2018-5-27 16:43

Powered by Discuz! X3

© 2001-2013 Comsenz Inc. Design By HUXTeam

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