一亩三分地论坛

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

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

google onsite 遇到一道非常难的题

[复制链接] |试试Instant~ |关注本帖
jasonust3 发表于 2015-3-21 01:13:01 | 显示全部楼层 |阅读模式

2015(1-3月) 码农类 硕士 全职@Google - 内推 - Onsite |Other

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

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

x
google onsite遇到这样一道难题,求大牛指点
假设在一个N×N的地图里面,有N个建筑物,已经给出每个建筑物的坐标.鐣欏璁哄潧-涓浜-涓夊垎鍦
然后要求输入随便一个坐标点x(a,b) ,
要求输出离 x 最近的建筑物

. 涓浜-涓夊垎-鍦帮紝鐙鍙戝竷
要求:这道题要求找出比O(N)更好的方法,不能把x跟全部建筑物的距离都比一遍。. visit 1point3acres.com for more.


另外,顺便求个分,如果哪位好心人愿意给分的话。谢谢了

评分

6

查看全部评分

本帖被以下淘专辑推荐:

refurbish 发表于 2015-3-21 14:35:59 | 显示全部楼层
几种方法分析一下:
. Waral 鍗氬鏈夋洿澶氭枃绔,
1. 最简单的做法: DP预处理,开一个N*N数组B【i】[j],从每个建筑开始BFS,B【i】[j]中保存距离(i,j)最近的建筑坐标。这个步骤是O(N^3),但是可以优化到O(N^2),存储是O(N^2)
查询的时间开销是O(1)

2. segment tree
对应行和列构造两个线段树,叶子节点保存所含建筑集合。构造时间是O(NlogN),存储是O(NlogN)
查询开销是O(logN), worst能到O(N).鏈枃鍘熷垱鑷1point3acres璁哄潧

3. k-d tree
构造时间复杂度O(NlogN),worst能到O(N^2),存储是O(N)
查询开销是O(logN),worst能到O(N)

4. r tree
构造时间复杂度O(NlogN),worst能到O(N^2),存储是O(N)
查询开销是O(logN),worst能到O(N)
.鐣欏璁哄潧-涓浜-涓夊垎鍦
回复 支持 1 反对 0

使用道具 举报

 楼主| jasonust3 发表于 2015-3-21 10:47:37 | 显示全部楼层
小柯西 发表于 2015-3-21 10:44
不知道这题具体setup是什么。。但是我隐约觉得,这个标记过程也是扫描,在标记的过程中要和建筑物的坐标 ...

k-d树的方法确实可以log(N)
回复 支持 1 反对 0

使用道具 举报

 楼主| jasonust3 发表于 2015-3-21 08:25:10 | 显示全部楼层
cow12331 发表于 2015-3-21 07:59
以为已经知道了每个建筑的坐标,所以每次把建筑周围的点全都标记为离这个建筑最近,每次标记都可以使地图上 ...

这个方法很是起码O(n),第一次标记的时候就O(n)了。。
回复 支持 1 反对 0

使用道具 举报

Linzertorte 发表于 2015-3-21 01:21:37 | 显示全部楼层
传说中的k-d树?
回复 支持 反对

使用道具 举报

57656929bb 发表于 2015-3-21 01:24:12 | 显示全部楼层
以给你的建筑为圆心,半径从1开始,一圈一圈的扫
回复 支持 反对

使用道具 举报

pyemma 发表于 2015-3-21 01:32:15 | 显示全部楼层
应该是K-D tree没跑了
回复 支持 反对

使用道具 举报

 楼主| jasonust3 发表于 2015-3-21 02:12:12 | 显示全部楼层

hmm。。稍微google了一下,貌似是没错。实在牛逼啊,之前完全没听过k-d树
回复 支持 反对

使用道具 举报

唯一 发表于 2015-3-21 04:39:54 | 显示全部楼层
k-d tree 有点丧病。。。
回复 支持 反对

使用道具 举报

shinichish 发表于 2015-3-21 07:35:30 | 显示全部楼层
spatial database好像就是这么实现的。。。所以复杂度是多少?
回复 支持 反对

使用道具 举报

cow12331 发表于 2015-3-21 07:59:23 | 显示全部楼层
以为已经知道了每个建筑的坐标,所以每次把建筑周围的点全都标记为离这个建筑最近,每次标记都可以使地图上少去一些点,而且这个每次少去的点成指数增长(假如一个建筑,第一次可以标记最多周围8个,第二次可以标记16),最差标记n次。所以是平局log(n),最差O(n)
回复 支持 反对

使用道具 举报

elementary 发表于 2015-3-21 09:41:14 | 显示全部楼层
57656929bb 发表于 2015-3-20 12:24
以给你的建筑为圆心,半径从1开始,一圈一圈的扫

1->2->4这样指数的扫?找到range之后再二分?感觉咱俩思路是一样的。
回复 支持 反对

使用道具 举报

cow12331 发表于 2015-3-21 10:21:47 | 显示全部楼层
elementary 发表于 2015-3-21 09:41.1point3acres缃
1->2->4这样指数的扫?找到range之后再二分?感觉咱俩思路是一样的。

大概意思是,比如有一个5*5的矩阵,中间有一个点,第一次标记后中间3*3的矩阵被标记,第二次5*5的矩阵最外圈被标记
回复 支持 反对

使用道具 举报

elementary 发表于 2015-3-21 10:25:52 | 显示全部楼层
cow12331 发表于 2015-3-20 21:21.鏈枃鍘熷垱鑷1point3acres璁哄潧
大概意思是,比如有一个5*5的矩阵,中间有一个点,第一次标记后中间3*3的矩阵被标记,第二次5*5的矩阵最 ...

大概了解了,可是如果是二维的话,标记需要的复杂度是?
回复 支持 反对

使用道具 举报

leyhzm 发表于 2015-3-21 10:29:56 | 显示全部楼层
从点X开始BFS周围的,找到的第一个建筑不就是最近的麻?感觉没什么tricky饿
回复 支持 反对

使用道具 举报

小柯西 发表于 2015-3-21 10:35:24 | 显示全部楼层
leyhzm 发表于 2015-3-21 10:29. from: 1point3acres.com/bbs
从点X开始BFS周围的,找到的第一个建筑不就是最近的麻?感觉没什么tricky饿

x所在的坐标未必有建筑物啊,怎么开始bfs。还有所谓的从周围建筑开始bfs是什么概念?这样能做到比O(N)还快?
回复 支持 反对

使用道具 举报

小柯西 发表于 2015-3-21 10:44:01 | 显示全部楼层
elementary 发表于 2015-3-21 10:25
大概了解了,可是如果是二维的话,标记需要的复杂度是?

不知道这题具体setup是什么。。但是我隐约觉得,这个标记过程也是扫描,在标记的过程中要和建筑物的坐标进行比对。。也得O(n)吧?除非有什么好的预处理方法
回复 支持 反对

使用道具 举报

小柯西 发表于 2015-3-21 10:55:01 | 显示全部楼层
说到k-d tree..给的point list是sorted的吗?如果不是,在构建k-d tree的时候还是要排序,at least O(nlgn)啊。。
回复 支持 反对

使用道具 举报

 楼主| jasonust3 发表于 2015-3-21 10:56:54 | 显示全部楼层
小柯西 发表于 2015-3-21 10:55
说到k-d tree..给的point list是sorted的吗?如果不是,在构建k-d tree的时候还是要排序,at least O(nlgn) ...

pre-process也是可以接受的,要保证的是以后每一次运行都是log n了
回复 支持 反对

使用道具 举报

leyhzm 发表于 2015-3-21 10:58:08 | 显示全部楼层
小柯西 发表于 2015-3-21 10:35
x所在的坐标未必有建筑物啊,怎么开始bfs。还有所谓的从周围建筑开始bfs是什么概念?这样能做到比O(N)还 ...
-google 1point3acres
赶脚你想复杂了,你可能当成计算每个点到建筑物的最近的距离来做了。这道题只要找到最近的就可以了把,比如给的点的(x,y),如果它就是建筑物,那返回这个点本身。如果不是,就划掉这个点(你可以设置一个visited数组),然后继续检查上下左右(划掉的点无需检查),如果上下左右中有建筑物就返回这个建筑物的坐标,如果不是就放入Queue继续BFS,以此类推。一旦有return肯定就是最近的啊。关于时间复杂度:因为一个点最多被check一次,假设只有一个建筑物那最差的情况也只是O(n),现在有三个建筑物,肯定比O(n) 好。PS:如果还需要返回最近的建筑物的距离,设置一个count就好了,每一批Queue变空就count++。最后这个count就是distance
回复 支持 反对

使用道具 举报

leyhzm 发表于 2015-3-21 11:06:55 | 显示全部楼层
顺便问下楼主,看到你前天发的电面面筋,今天就onsite完了????你太快了把0 0你是神马时候电面的呀~
回复 支持 反对

使用道具 举报

本版积分规则

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

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

关闭

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

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

custom counter

GMT+8, 2016-12-3 08:33

Powered by Discuz! X3

© 2001-2013 Comsenz Inc. Design By HUXTeam

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