m*i
2 楼
挂在了设计题, 设计Uber app的两个service。
driver/车
update (carId,log,lat), 1 update per sec.
rider
getCarsAndETA(log,lat), 1 request per sec.
某个城市，假设是SF，有1000辆车，1000个active users.
Q：
单机可以吗？
如何存储数据，用数据库吗？
如何update车移动的数据（设计数据结构）。
如何设计getCarsAndETA求得ETA最小的10辆车 （可以简单的假设距离近就ETA小）。
如果update的响应速度比getCarsAndETA快得多(getCarsAndETA计算量很大），怎么
scale这两个service，即怎么使getCarsAndETA跟得上update的响应速度。
如何scale到其他城市
1）周边小城市
2）距离很远的大城市
看过一个talk讲到Uber用的是google的一个library,将地图分成一个个block，根据某
个点画个圈，只计算圈所覆盖的blocks。
我就是按这个思路答的，不过被指出这样有个问题是如果block size不小，那同一个
block里面车，即使是在两个对角的也算同一个block，以block为单位计算距离的话不
够准确。
各位有什么想法/解法，请不吝赐教。谢谢。
driver/车
update (carId,log,lat), 1 update per sec.
rider
getCarsAndETA(log,lat), 1 request per sec.
某个城市，假设是SF，有1000辆车，1000个active users.
Q：
单机可以吗？
如何存储数据，用数据库吗？
如何update车移动的数据（设计数据结构）。
如何设计getCarsAndETA求得ETA最小的10辆车 （可以简单的假设距离近就ETA小）。
如果update的响应速度比getCarsAndETA快得多(getCarsAndETA计算量很大），怎么
scale这两个service，即怎么使getCarsAndETA跟得上update的响应速度。
如何scale到其他城市
1）周边小城市
2）距离很远的大城市
看过一个talk讲到Uber用的是google的一个library,将地图分成一个个block，根据某
个点画个圈，只计算圈所覆盖的blocks。
我就是按这个思路答的，不过被指出这样有个问题是如果block size不小，那同一个
block里面车，即使是在两个对角的也算同一个block，以block为单位计算距离的话不
够准确。
各位有什么想法/解法，请不吝赐教。谢谢。
i*8
3 楼
我还有个16g 拼个单呗，现在好像对加州来说没意思了
A*d
4 楼
赞楼主的分享精神！这个版太缺了，总有人把我和swjtuer那个傻逼相提并论，最大的
区别就是姐当年把所有面试面筋都奉献出来了，swjtuer就只发挑拨离间贴和阴阳怪气
的留言。
区别就是姐当年把所有面试面筋都奉献出来了，swjtuer就只发挑拨离间贴和阴阳怪气
的留言。
l*i
5 楼
Use a hash map to store locations of cars.
Cars location is updated every second, but reconstruct a KD tree only every
minute.
cache the result of getCarsAndETA() so it is only update every minute.
Cars location is updated every second, but reconstruct a KD tree only every
minute.
cache the result of getCarsAndETA() so it is only update every minute.
l*i
6 楼
To be more accurate. You can compute the velocity of cars and estimate their
locations between minutes.
locations between minutes.
s*n
7 楼
一共就1000辆车 单机存内存应该可以吧 （反正数据每秒上报，后面车的数据覆盖前
面的，不存在持久化问题）
然后将地图分为六边形小块，每个车更新位置时以hexgon id做一个index。 这样找车
的时候查当前六边形附近几个的candidates
找车api算的慢，估计时间都耗在计算距离上了，可以单独提出来做一个前端，部署多
台机器，从后端内存数据库里提取candidate list 然后逐一计算距离。
大家感觉这么的靠谱不
【在 m***i 的大作中提到】
: 挂在了设计题, 设计Uber app的两个service。
: driver/车
: update (carId,log,lat), 1 update per sec.
: rider
: getCarsAndETA(log,lat), 1 request per sec.
: 某个城市，假设是SF，有1000辆车，1000个active users.
: Q：
: 单机可以吗？
: 如何存储数据，用数据库吗？
: 如何update车移动的数据（设计数据结构）。
面的，不存在持久化问题）
然后将地图分为六边形小块，每个车更新位置时以hexgon id做一个index。 这样找车
的时候查当前六边形附近几个的candidates
找车api算的慢，估计时间都耗在计算距离上了，可以单独提出来做一个前端，部署多
台机器，从后端内存数据库里提取candidate list 然后逐一计算距离。
大家感觉这么的靠谱不
【在 m***i 的大作中提到】
: 挂在了设计题, 设计Uber app的两个service。
: driver/车
: update (carId,log,lat), 1 update per sec.
: rider
: getCarsAndETA(log,lat), 1 request per sec.
: 某个城市，假设是SF，有1000辆车，1000个active users.
: Q：
: 单机可以吗？
: 如何存储数据，用数据库吗？
: 如何update车移动的数据（设计数据结构）。
G*A
8 楼
lat是latitude的意思？
【在 m***i 的大作中提到】
: 挂在了设计题, 设计Uber app的两个service。
: driver/车
: update (carId,log,lat), 1 update per sec.
: rider
: getCarsAndETA(log,lat), 1 request per sec.
: 某个城市，假设是SF，有1000辆车，1000个active users.
: Q：
: 单机可以吗？
: 如何存储数据，用数据库吗？
: 如何update车移动的数据（设计数据结构）。
【在 m***i 的大作中提到】
: 挂在了设计题, 设计Uber app的两个service。
: driver/车
: update (carId,log,lat), 1 update per sec.
: rider
: getCarsAndETA(log,lat), 1 request per sec.
: 某个城市，假设是SF，有1000辆车，1000个active users.
: Q：
: 单机可以吗？
: 如何存储数据，用数据库吗？
: 如何update车移动的数据（设计数据结构）。
z*8
9 楼
瓶颈应该不在内存而在cpu上面吧， 2000qps的计算量估计单机扛不住
【在 s*********n 的大作中提到】
: 一共就1000辆车 单机存内存应该可以吧 （反正数据每秒上报，后面车的数据覆盖前
: 面的，不存在持久化问题）
: 然后将地图分为六边形小块，每个车更新位置时以hexgon id做一个index。 这样找车
: 的时候查当前六边形附近几个的candidates
: 找车api算的慢，估计时间都耗在计算距离上了，可以单独提出来做一个前端，部署多
: 台机器，从后端内存数据库里提取candidate list 然后逐一计算距离。
: 大家感觉这么的靠谱不
【在 s*********n 的大作中提到】
: 一共就1000辆车 单机存内存应该可以吧 （反正数据每秒上报，后面车的数据覆盖前
: 面的，不存在持久化问题）
: 然后将地图分为六边形小块，每个车更新位置时以hexgon id做一个index。 这样找车
: 的时候查当前六边形附近几个的candidates
: 找车api算的慢，估计时间都耗在计算距离上了，可以单独提出来做一个前端，部署多
: 台机器，从后端内存数据库里提取candidate list 然后逐一计算距离。
: 大家感觉这么的靠谱不
G*A
10 楼
lat是latitude的意思？
【在 m***i 的大作中提到】
: 挂在了设计题, 设计Uber app的两个service。
: driver/车
: update (carId,log,lat), 1 update per sec.
: rider
: getCarsAndETA(log,lat), 1 request per sec.
: 某个城市，假设是SF，有1000辆车，1000个active users.
: Q：
: 单机可以吗？
: 如何存储数据，用数据库吗？
: 如何update车移动的数据（设计数据结构）。
【在 m***i 的大作中提到】
: 挂在了设计题, 设计Uber app的两个service。
: driver/车
: update (carId,log,lat), 1 update per sec.
: rider
: getCarsAndETA(log,lat), 1 request per sec.
: 某个城市，假设是SF，有1000辆车，1000个active users.
: Q：
: 单机可以吗？
: 如何存储数据，用数据库吗？
: 如何update车移动的数据（设计数据结构）。
z*n
11 楼
我帮lz回答下最后一问，block的那个问题，看过网上的文章，正解（事实人家就是这
么做的）就是把周围的一圈block也考虑进来，然后以实际距离决出一个最近的。。。
lz看到这个会不会很无语
。。
么做的）就是把周围的一圈block也考虑进来，然后以实际距离决出一个最近的。。。
lz看到这个会不会很无语
。。
s*x
12 楼
Block 有好多缺点阿，这是最普通的办法。估计最好是 kd tree , quad tree 或
Geohash, 其实就是 hierarchical block.
每秒update 一次，连数据库都用不着.
1000 辆车，一台机器应该足够了，但要容错，就要加备份。
: 我帮lz回答下最后一问，block的那个问题，看过网上的文章，正解（事实人家
就是这
: 么做的）就是把周围的一圈block也考虑进来，然后以实际距离决出一个最近的
。。。
: lz看到这个会不会很无语
: 。。
【在 z*********n 的大作中提到】
: 我帮lz回答下最后一问，block的那个问题，看过网上的文章，正解（事实人家就是这
: 么做的）就是把周围的一圈block也考虑进来，然后以实际距离决出一个最近的。。。
: lz看到这个会不会很无语
: 。。
Geohash, 其实就是 hierarchical block.
每秒update 一次，连数据库都用不着.
1000 辆车，一台机器应该足够了，但要容错，就要加备份。
: 我帮lz回答下最后一问，block的那个问题，看过网上的文章，正解（事实人家
就是这
: 么做的）就是把周围的一圈block也考虑进来，然后以实际距离决出一个最近的
。。。
: lz看到这个会不会很无语
: 。。
【在 z*********n 的大作中提到】
: 我帮lz回答下最后一问，block的那个问题，看过网上的文章，正解（事实人家就是这
: 么做的）就是把周围的一圈block也考虑进来，然后以实际距离决出一个最近的。。。
: lz看到这个会不会很无语
: 。。
z*8
13 楼
kdtree quadtree不还是把地图分块的思想吗。。。实际上uber就是用的google s2
library把地图分成若干cell
【在 s**x 的大作中提到】
: Block 有好多缺点阿，这是最普通的办法。估计最好是 kd tree , quad tree 或
: Geohash, 其实就是 hierarchical block.
: 每秒update 一次，连数据库都用不着.
: 1000 辆车，一台机器应该足够了，但要容错，就要加备份。
:
:
: 我帮lz回答下最后一问，block的那个问题，看过网上的文章，正解（事实人家
: 就是这
:
: 么做的）就是把周围的一圈block也考虑进来，然后以实际距离决出一个最近的
: 。。。
:
: lz看到这个会不会很无语
library把地图分成若干cell
【在 s**x 的大作中提到】
: Block 有好多缺点阿，这是最普通的办法。估计最好是 kd tree , quad tree 或
: Geohash, 其实就是 hierarchical block.
: 每秒update 一次，连数据库都用不着.
: 1000 辆车，一台机器应该足够了，但要容错，就要加备份。
:
:
: 我帮lz回答下最后一问，block的那个问题，看过网上的文章，正解（事实人家
: 就是这
:
: 么做的）就是把周围的一圈block也考虑进来，然后以实际距离决出一个最近的
: 。。。
:
: lz看到这个会不会很无语
j*3
14 楼
uber设计题感觉向来都是乱问的
k*a
15 楼
看看geohashing的文档
【在 m***i 的大作中提到】
: 挂在了设计题, 设计Uber app的两个service。
: driver/车
: update (carId,log,lat), 1 update per sec.
: rider
: getCarsAndETA(log,lat), 1 request per sec.
: 某个城市，假设是SF，有1000辆车，1000个active users.
: Q：
: 单机可以吗？
: 如何存储数据，用数据库吗？
: 如何update车移动的数据（设计数据结构）。
【在 m***i 的大作中提到】
: 挂在了设计题, 设计Uber app的两个service。
: driver/车
: update (carId,log,lat), 1 update per sec.
: rider
: getCarsAndETA(log,lat), 1 request per sec.
: 某个城市，假设是SF，有1000辆车，1000个active users.
: Q：
: 单机可以吗？
: 如何存储数据，用数据库吗？
: 如何update车移动的数据（设计数据结构）。
s*7
16 楼
难得的正能量帖，先顶再看，感谢分享
【在 m***i 的大作中提到】
: 挂在了设计题, 设计Uber app的两个service。
: driver/车
: update (carId,log,lat), 1 update per sec.
: rider
: getCarsAndETA(log,lat), 1 request per sec.
: 某个城市，假设是SF，有1000辆车，1000个active users.
: Q：
: 单机可以吗？
: 如何存储数据，用数据库吗？
: 如何update车移动的数据（设计数据结构）。
【在 m***i 的大作中提到】
: 挂在了设计题, 设计Uber app的两个service。
: driver/车
: update (carId,log,lat), 1 update per sec.
: rider
: getCarsAndETA(log,lat), 1 request per sec.
: 某个城市，假设是SF，有1000辆车，1000个active users.
: Q：
: 单机可以吗？
: 如何存储数据，用数据库吗？
: 如何update车移动的数据（设计数据结构）。
z*n
17 楼
我怎么记得Google S2的精度要高于Geohash呢。。Geohash主要优点是速度快，对数据
库比较友好吧
【在 s**x 的大作中提到】
: Block 有好多缺点阿，这是最普通的办法。估计最好是 kd tree , quad tree 或
: Geohash, 其实就是 hierarchical block.
: 每秒update 一次，连数据库都用不着.
: 1000 辆车，一台机器应该足够了，但要容错，就要加备份。
:
:
: 我帮lz回答下最后一问，block的那个问题，看过网上的文章，正解（事实人家
: 就是这
:
: 么做的）就是把周围的一圈block也考虑进来，然后以实际距离决出一个最近的
: 。。。
:
: lz看到这个会不会很无语
w*g
18 楼
学习了
w*m
19 楼
大牛们赶快详细写个code吧
s*x
20 楼
那个cell不是简单的分块，是用Hilbert curve 弄的。俺也不憧。
: kdtree quadtree不还是把地图分块的思想吗。。。实际上uber就是用的google
s2
: library把地图分成若干cell
【在 z*********8 的大作中提到】
: kdtree quadtree不还是把地图分块的思想吗。。。实际上uber就是用的google s2
: library把地图分成若干cell
: kdtree quadtree不还是把地图分块的思想吗。。。实际上uber就是用的google
s2
: library把地图分成若干cell
【在 z*********8 的大作中提到】
: kdtree quadtree不还是把地图分块的思想吗。。。实际上uber就是用的google s2
: library把地图分成若干cell
w*m
21 楼
大牛们赶快详细写个code吧
z*n
22 楼
用Hilbert curve弄就是简单的把2维映射到1维，方便数据库检索而已，有一定的错误
率
【在 s**x 的大作中提到】
: 那个cell不是简单的分块，是用Hilbert curve 弄的。俺也不憧。
:
:
: kdtree quadtree不还是把地图分块的思想吗。。。实际上uber就是用的google
: s2
:
: library把地图分成若干cell
:
相关阅读
amazon lab126 杩樻槸Samsung最近形势很好，有很多高级职位空了出来，兄弟们Backend service, tensorflow background求google team matchGoogle onsite面试题全都答出来，能录取么？YUM CHINA 的 CEO 竟然是阿三 ？怎么谈工资？有人举几个个烙印，老美，老毛子被pip的例子吗？NVIDIA package? (转载)关于背景调查求助求内推 sql server developer/DBA (转载)求内推 -- 西雅图地区 微软/波音等类似公司F家可以同时面两个职位吗？请问谁做过 从Dropbox 的文件夹下 一次提取所有Photos and 显示在 Web 上 用Javascript.真是冰火两重天啊Apple backend team 招 engineer/scientist 和PM吴京华Data science/analytics 有推荐练习学习的网站吗？Twitter看样子必须大裁员了请教一个有关离职时间和rsu的问题#wikileaks Google助选希拉里 (转载)