G**O
发帖数: 147 | 1 网上找到的资料一般都是在说geo hash原理是什么，基本没找到讨论具体怎么存储，读
和写怎么弄的，特来请教各位大神。
比如我的use case是，支持
寻找附近 5km 内的POI， 可以返回所有POI， 但是同时要支持分类查询：饭店，酒吧
，电影院...
首先想到GeoHashing来做，就是获取用户的地理位置，算出一个位置，比如 9u9qvu,
六位应该精度就够了。
然后要找附近 9u9qv[0] -- 9u9qv[z] 的所有的东西。我们可以用SQL
poi_table
id geohash name category....
SQL 的query可以这样 S3L3CT FROM table WHERE geohash Iike 9u9qv[%]
如果要查询酒吧
可以 geohash Iike 9u9qv[%] and category = bar
这样即使通过geohash 建立一个 index，效率似乎还是不够高。
如果用NoSQL, 应该怎么存，效率会比较高
1. 用什么类型的NoSQL
2. 具体怎么存。
3. 怎么处理POI 跃变的问... 阅读全帖 |
|
F****n
发帖数: 3271 | 2 geohash是给没有spatial data structure的检索系统用的
比如说你只能用一个全文本的搜索引擎，geohash可以用来mimic spatial indexing
你可以把event wx4g0ec1 用所有的prefixes(w, wx, wx4...）索引
这样对任何一级的搜索都能找到
但是如果你自己build一个搜索系统，没有必要用geohash
geohash就是一个很蹩脚的quadtree(essentially a trie), 并不efficient,
应该直接上spatial data structure.
一般来说r-tree is the best. |
|
p******a
发帖数: 130 | 3 可以用hbase存。查询的时候需要比较附近9个block的数据。
[在 GPRO (GoPro) 的大作中提到：]
:网上找到的资料一般都是在说geo hash原理是什么，基本没找到讨论具体怎么存储，
读和写怎么弄的，特来请教各位大神。
:比如我的use case是，支持
:寻找附近 5km 内的POI， 可以返回所有POI， 但是同时要支持分类查询：饭店，酒吧
:，电影院...
:首先想到GeoHashing来做，就是获取用户的地理位置，算出一个位置，比如 9u9qvu,
六位应该精度就够了。
:然后要找附近 9u9qv[0] -- 9u9qv[z] 的所有的东西。我们可以用SQL
:poi_table
:id geohash name category....
:SQL 的query可以这样 S3L3CT FROM table WHERE geohash Iike 9u9qv[%]
:如果要查询酒吧
:.......... |
|
发帖数: 1 | 4 1 如果是搜索引擎用lucene或者solr/elatic search
2 要建不同长度的geohash索引
搜索的时候 根据需要搜索的半径 选择长度合适的geohash
可以以用户所在geohash块为中心 搜9宫格 9宫格要能框住需要的圆 且9宫格越小越好
搜出来超过半径的结果放弃掉
这样应该没有边界问题 |
|
a****i
发帖数: 1182 | 5 怎么在一个分布系统保存和读取geohash
比如说有个event在 wx4g0ec1，显然它也在w, wx, wx4...里
具体实现的时候，每一级geohash都会指向这个event，w -> "wx4g0ec1"
wx -> "wx4g0ec1" ...
还是说上一级只需要指向下一级就可以？ w -> wx -> wx4 ... -> "wx4g0ec1"
在读取的时候又怎么做呢？比如说读最新的十个event，在某个location范围
zoom in/out |
|
m*******n
发帖数: 113 | 6 看一下geohash找neighbor的函数你就明白了。数据应该是扁平存的。 |
|
a****i
发帖数: 1182 | 7 感觉应该是存最高精度的geohash
比如9位的
在起service的时候，从数据库里读出来，然后按照geohas建棵树
9: {...}
9u: {...}
9u9: {...}
|
|
z****e
发帖数: 54598 | 8
lol
geohash你要继续吗？
geohash的市场很大？
您别逗了，geohash只是一种编码方式
而且prefix相同还未必代表距离近，not always
你用geohash纯粹自取其辱啊 |
|
c*********n
发帖数: 1057 | 9 Re这个。
里面讲的很清楚怎么样apply geohash to query.如果我没有理解错的话，用里面说的
方法可以省去前面大牛讲的design中的index server，就是存放每个grid中的PO壹的信
息的
给一个point and range,应该可以计算出minimum geohash prefix that contains the
area
然后用这个a list of geohash prefix去storage layer 拿所有符合要求的POI就可以
了。
如果哪里理解有误请指出 |
|
r*******e
发帖数: 7583 | 10 直接geohash的话，怎么快速找出5mile之内的其他geohash key？
我觉得可以把map按照经纬坐标划为很多grids
每个grid用左上角+右下角坐标当key，value是在这个grid里的POI list
对一个给定的位置，可以很快算出与5mile为半径的圆重合的grids
然后把这些grids的POI读出来，按距离排一下，把超过5mile的过滤掉
至于这个grid的granularity，就是需要讨论的细节了 |
|
y*c
发帖数: 904 | 11 首先数据库要是spatial的，就是上面所说的geohash的，给一个geohash/quadkey, 能
拿到所有的POI，但是拿到之后，内存里可能需要做更小规模的filter, R-tree based
algorithm管用。 |
|
r*******e
发帖数: 7583 | 12 直接geohash的话，怎么快速找出5mile之内的其他geohash key？
我觉得可以把map按照经纬坐标划为很多grids
每个grid用左上角+右下角坐标当key，value是在这个grid里的POI list
对一个给定的位置，可以很快算出与5mile为半径的圆重合的grids
然后把这些grids的POI读出来，按距离排一下，把超过5mile的过滤掉
至于这个grid的granularity，就是需要讨论的细节了 |
|
y*c
发帖数: 904 | 13 首先数据库要是spatial的，就是上面所说的geohash的，给一个geohash/quadkey, 能
拿到所有的POI，但是拿到之后，内存里可能需要做更小规模的filter, R-tree based
algorithm管用。 |
|
k******a
发帖数: 44 | 14 这是一个point of interest点问题，不少公司的design题都有这个。
看到过一个用geohash的做法，就是将二维数据变成一维数据。geohash一放狗就看到了。
俺们这样的土人搞不了那么高深的，就用经纬度做HASHMAP的GRID，然后对于每一个
CELL里的点用图表示。缩小范围以后，用BFS搜吧。 |
|
z*********n
发帖数: 1451 | 15
我怎么记得Google S2的精度要高于Geohash呢。。Geohash主要优点是速度快，对数据
库比较友好吧 |
|
|
a****i
发帖数: 1182 | 17 能明白geohash怎么来的，但是不太清楚这个怎么在一个分布系统保存和读取
比如说有个event在 wx4g0ec1，显然它也在w, wx, wx4...里
具体实现的时候，每一级geohash都会指向这个event，还是说上一级只需要指向下一级
就可以？
在读取的时候又怎么做呢？比如说读最新的十个event，在某个location范围 |
|
d******e
发帖数: 2265 | 18 你要找poi活着user,肯定是在后端做了。
那么，最简单的scan，计算，就是你说的o(n).
这对uber这样的级别数据库是不可行的。
其次，rtree range query. postgre gis 支持。但是这个不可scalable.
在其次， kd tree, k维还是太复杂。
geohash将为一维,这个可以用btree index了。甚至可以做成hash+trie，纯内存结构。
update, query 都是常数到o(log(n)) + o(t)级别的操作。t在bounding box里面的用
户数目。
geohash本质就是经纬度变成01然后base 36编码。 |
|
s*****n
发帖数: 5488 | 19 来自主题: JobHunting版 - G 家面经 楼主什么背景，这题都很难啊。
1. quadtree其实就是geohash.可以用zorder排序的。所以第一题应该是map reduce.
所有的的点来一遍就可以得到intersection
2. 双向搜是biidrectional dijistra吧。
4.最后那个其实是n-gram markov chain.里面水挺深的。简单prefix tree是不行的。
否则那么多怎么选。然后算概率还要调整。尼玛，不看书老夫早基本忘了叫什么了。没
有NLP背景这题太坑爹了。
的。 |
|
s*****n
发帖数: 5488 | 20 来自主题: JobHunting版 - G 家面经 楼主什么背景，这题都很难啊。
1. quadtree其实就是geohash.可以用zorder排序的。所以第一题应该是map reduce.
所有的的点来一遍就可以得到intersection
2. 双向搜是biidrectional dijistra吧。
4.最后那个其实是n-gram markov chain.里面水挺深的。简单prefix tree是不行的。
否则那么多怎么选。然后算概率还要调整。尼玛，不看书老夫早基本忘了叫什么了。没
有NLP背景这题太坑爹了。
的。 |
|
w******j
发帖数: 185 | 21 任给一个手机的位置信号(经纬度)，需要返回附近5mile
的POI，怎么设计这样的系统
像他们这种公司，比如说google用big table存储map数据，facebook 用hbase吧？
是不是先用一个geohash找到存这个位置的shard,在从这个shard 里面找poi？
可以把每个shard 的poi都提前存起来....
这个怎么能说45分钟呢... |
|
|
w******j
发帖数: 185 | 23 任给一个手机的位置信号(经纬度)，需要返回附近5mile
的POI，怎么设计这样的系统
像他们这种公司，比如说google用big table存储map数据，facebook 用hbase吧？
是不是先用一个geohash找到存这个位置的shard,在从这个shard 里面找poi？
可以把每个shard 的poi都提前存起来....
这个怎么能说45分钟呢... |
|
|
c*********i
发帖数: 46 | 25 上周FB onsite, 但是悲剧了，下面是HR的回复：
overall there were some very strong points throughout your interview day and
the engineers really enjoyed the conversations. Unfortunately, it was
primarily the architecture and design that did not go as well as we would
hope。
我全天就一个烙印，就是这个system design 这轮，题目是POI 5miles. 我用geohash
做的， 最后scale的时候，首先想到根据地域，然后他说有问题。自己struggle了一下
，然后提到另外一种方案，达到了他想要的scale的方法，他最后也表示满意，也算了
需要的memory， 和机器数，他也表示满意。我不敢说我答的很好，最起码也不是太差
吧。
但是还是被拒了因为这轮，而且是唯一的烙印，这些巧合不得不让我有些联想。HR 后
来又让我去面另外一个组，也算给了另... 阅读全帖 |
|
c*********i
发帖数: 46 | 26 就是HR给我推荐了另外一个做系统performance的组，重新面试！
关于scale: 刚开始提出把地域相近的data shard 在一起，这样，因为是求5miles的
POI，相近的点可以group在一个DB里，不用跨DB。但是他提出这样设计有个问题，我想
了一会说，是的，这样可能有的db数据多，有的少，不balance.他问怎么解决，我想了
一会说(这个中间是有点不是很smooth我承认)，说可以hash之前生成的geohash值，映
射到不同的DB，这样，load 就balance了，但是要从不同的DB里取数据。还说这样也有
弊端，提了一下consistent hashing. 他说可以。 然后就问问题了。
大体上就是这了，我知道自己系统设计不是很强，但是也觉得答的没有那么差呀！ |
|
k****i
发帖数: 128 | 27 我以为F家是general hire，不分组的
对于rehash了，geohash本来的意义就没了，直接存成经纬度不就行了。另外rehash后
你怎么index到临近点呢？
这题我觉得应该按grid分片，一个grid里的POI存在一起，临近grid分散到不同机器上
。 |
|
|
b******g
发帖数: 77 | 29 Offer:
=====
背景：非cs PhD+两年半经验
申请了Amazon，FB 和 G。
A家Rejected：1st 电面遇三哥，被黑
f家Offer： ~24w/year + 5w sign on
g家Offer： ~25w/year + 3.5w sign on
两个Offer都很好，很难选择，最后去了狗。
FB 是板上的大哥帮我内推的，人非常非常好，很热心，很可惜最后没去，特别特别的
感谢他。
G家是哥们内推的，帮忙收集了很多准备材料，有问必答。
最感谢的是，老婆，岳父，岳母，提供充足的后期保障，说实话，照顾宝宝比什么写码
刷题，累得多。
面经：
====
A家电面：
-----------
三哥，出了5道题，30分钟全部搞定，还是被黑了。当时没有经验，应该面试完后
立刻投诉。出结果后才向HR投诉，未果。
1 given 2 strings，can you construct str1 using chars in str2？
2 binary tree inorder traversal，both recursiv... 阅读全帖 |
|
b**********5
发帖数: 7881 | 30 楼主， 是不是说geohashing， 然后存 user id 和geoposition pair， 然后在自己和
相邻的区域找friends？
我fb面试时， 一个中国男， 我说Geo hash ing， 他直接说， 没听说过， 还有其他
方法么？ |
|
b******g
发帖数: 77 | 31 Offer:
=====
背景：非cs PhD+两年半经验
申请了Amazon，FB 和 G。
A家Rejected：1st 电面遇三哥，被黑
f家Offer： ~24w/year + 5w sign on
g家Offer： ~25w/year + 3.5w sign on
两个Offer都很好，很难选择，最后去了狗。
FB 是板上的大哥帮我内推的，人非常非常好，很热心，很可惜最后没去，特别特别的
感谢他。
G家是哥们内推的，帮忙收集了很多准备材料，有问必答。
最感谢的是，老婆，岳父，岳母，提供充足的后期保障，说实话，照顾宝宝比什么写码
刷题，累得多。
面经：
====
A家电面：
-----------
三哥，出了5道题，30分钟全部搞定，还是被黑了。当时没有经验，应该面试完后
立刻投诉。出结果后才向HR投诉，未果。
1 given 2 strings，can you construct str1 using chars in str2？
2 binary tree inorder traversal，both recursiv... 阅读全帖 |
|
b**********5
发帖数: 7881 | 32 楼主， 是不是说geohashing， 然后存 user id 和geoposition pair， 然后在自己和
相邻的区域找friends？
我fb面试时， 一个中国男， 我说Geo hash ing， 他直接说， 没听说过， 还有其他
方法么？ |
|
f*******r
发帖数: 976 | 33 恭喜！
Offer:
=====
背景：非cs PhD+两年半经验
申请了Amazon，FB 和 G。
A家Rejected：1st 电面遇三哥，被黑
f家Offer： ~24w/year + 5w sign on
g家Offer： ~25w/year + 3.5w sign on
两个Offer都很好，很难选择，最后去了狗。
FB 是板上的大哥帮我内推的，人非常非常好，很热心，很可惜最后没去，特别特别的
感谢他。
G家是哥们内推的，帮忙收集了很多准备材料，有问必答。
最感谢的是，老婆，岳父，岳母，提供充足的后期保障，说实话，照顾宝宝比什么写码
刷题，累得多。
面经：
====
A家电面：
-----------
三哥，出了5道题，30分钟全部搞定，还是被黑了。当时没有经验，应该面试完后
立刻投诉。出结果后才向HR投诉，未果。
1 given 2 strings，can you construct str1 using chars in str2？
2 binary tree inorder traversal，both rec... 阅读全帖 |
|
b**********5
发帖数: 7881 | 34 6. how to design a system to automatically detect hotspot on geo graph, a
hotspot is an area such that 打车的request远多于available driver的数量
这个你怎么回答的？ request此时， availabl driver都需要remember他们的location
， 你用geohash 作为key？ 但肯定又不能只是compare相同的key， 而是要compare一
个区域是不是hotspot |
|
k******a
发帖数: 44 | 35 设计题就是F常见的POI吧，我的思路。
看过以前的文章，主要是用geohash将二维坐标转换为一维的数值或者字符串。
以后就好办了，将所有已知数据（key-value）保存在distriubted key-value map
这样，取某个点所在区域，以及周边区域的数据都是可以并行进行的。
用 cache 提高存取速度。利用LRU算法维护，保证热点地区的数据总在cache。
用map/reduce同时查找多个周边地区，然后汇总。 |
|
e***i
发帖数: 231 | 36 geohash O(1)
k-d tree O(lgn) |
|
l****c
发帖数: 782 | 37 说说这次面试遇到的system design题，不想全英文，就中英文混杂了。
1。 POI － geohash， kd tree 两种方法都要求。
2。Shorten URL － 单机solution，distribute system solution，cache的使用，怎
么盈利，怎么避免为黄色网址服务，怎么得到实时logging metrics，etc。
3. large distributed system 怎么log 各种 data analysis 可能需要的各种query
，怎么得到过去一周或一个月top 10 requests／ exceptions。
4. news feed 整个流程（twitter ，facebook类似但不一样，不一样在哪里），是用
pull还是push，是为每个用户保存一个queue吗？new year时high traffic会出现哪些
特殊情况，怎么解决？
5. 微博上用户更改用户名，从前端都后端都需要相应做什么操作。后端数据怎么相应
存储用户的微博内容。这个没有想像中那么简单。。。
6. 当你更新code base里的一个读写数据的b... 阅读全帖 |
|
l********s
发帖数: 276 | 38 不知道为啥只有4关
1. 亚裔，聊天，然后一道题: 字符match to 其他字符，给你一个字符串，求所有可能
的字符串match。
2. 亚裔，又是聊天，然后是wordsearch，基本是原题，但四个方向的变成八个方向了。
3. 白人design, geohash + kd tree那道题，感觉做的不好，我说每句话面试官都要打
算一下问个问题，导致最后时间都回答他的问题了，连草图都没画出来。最后果然挂在
这一轮。
4. 白人一个字符串，比如"a(bb)a((bc)())", 返回"a(bb)a(bc)()"就是保留valid的括
号。刚开始这白人一副不屑的样子，我说什么他都说OK, 好像意思是说“我知道你做不
出来”，后来做出来了又一道one edit distance，原题。
面试官都很年轻，这次碰到的亚裔都很nice, 在此表示感谢。道是碰到的白人不行，才
工作了两年就很Arrogant. |
|
e***i
发帖数: 231 | 39 献个丑，胡乱指点江山啊
Level 1 乘客跟司机应该更重视哪边？（乘客）
Level 2 如何缩短乘客等待时间？（司机十秒抢单机制v.s. queue）
Level 3 乘客叫车流程：
request with location，
ack & profile dispatch，
ETA，
picked up confirmation （driver side）,
routing (A*),
arrival confirmation,
credit card processing,
feedback loop,
receipt email trigger,
coupon and promotion,
refund and dispute,
rider request cancellation,
driver rating,
peak hour fare surge (machine learning)
Level 4
4.1 Nearest Drivers algorithm: Zoning and confinement? Distance
calculation? Geohas... 阅读全帖 |
|
g**t
发帖数: 49 | 40 为什么不用geohash？据说Uber用的是Google s2 cell
alabama |
|
n***a
发帖数: 222 | 41 给定N个2D坐标（可以设想为餐厅的位置），要求输入任意坐标，可以返回方圆d距离内
的所有餐厅
非sys design， 所以应该不能用geohashing 或者spatial index之类的 |
|
s**x
发帖数: 7506 | 42 Block 有好多缺点阿，这是最普通的办法。估计最好是 kd tree , quad tree 或
Geohash, 其实就是 hierarchical block.
每秒update 一次，连数据库都用不着.
1000 辆车，一台机器应该足够了，但要容错，就要加备份。
: 我帮lz回答下最后一问，block的那个问题，看过网上的文章，正解（事实人家
就是这
: 么做的）就是把周围的一圈block也考虑进来，然后以实际距离决出一个最近的
。。。
: lz看到这个会不会很无语
: 。。
|
|
|
m**c
发帖数: 22 | 44 consistant hashing on geohash key, 各个node无非就是做bit_and filtering（kd-
tree based on mega store还能加速），如能同时做top-k on timestamp更快。 |
|
|
G**O
发帖数: 147 | 46 思路和key value差不多吧？
row key 还是 9u9qv 。 然后里面可以存这个prefix下所有的POI。
问题就是如果要更大，或者更小范围，就需要另外存 9u9q, 。
还是说 row key 存的是每个POI 具体的位置，然后查询的时候做 range query
, |
|
p******a
发帖数: 130 | 47 不是指定要查5km范围的地点吗？
[在 GPRO (GoPro) 的大作中提到：]
:思路和key value差不多吧？
:row key 还是 9u9qv 。 然后里面可以存这个prefix下所有的POI。 |
|
G**O
发帖数: 147 | 48 哦，抱歉没说清楚，5km是个例子。总之就是一个合理范围。 |
|
|
p******a
发帖数: 130 | 50 距离加大就多查几个block中的点
[在 mknoodle (mknoodle) 的大作中提到：]
:哥，能5KM，也要能10KM啊 |
|
