七月脸书

不好意思这几天太忙了一直没上

关于那个follow up，当时就是还剩十几分钟，就仅仅和面试官描述了一下思路：

基本逻辑：
1. 巨大迷宫可以划分成格子存储，每块格子能放进单机memory
2. 从起点S用DFS找到格子上下左右边界上所有可达的点集X。对每一个点，记录位置和方向（方向是指接下来的探查方向，比如说点P在当前格子的左边界上，那么下次就应该继续向左边的格子探查;如果在角上，就要探查两个方向，比如向左和向上）
3. 对于点集X中的每一个没有处理过的点，按照探查方向继续用DFS找到相邻格子中上下左右边界上的可达点，并加入X
4. 最终会hit终点e的格子的边界，再看看从边界上的点能不能达到终点e

并行化：

1.所有的迷宫格子数据存在HDFS，
2.点集X可以用一台server存储，加个RPC存取API
3.分布式的worker的逻辑就是 a)从X取几个点 b)load 相应的迷宫格子 c)找到边界点集存进server

最后又提了下failure handling 什么的，面试官说和他想的差不多，应该算是混过去了

bearicc 发表于 2017-8-4 02:13
3b 就是 621 task scheduler 么 ？

看了一下还确实是，天阿都到六百多了

谢谢分享

chrono98 发表于 2017-8-6 07:37
不好意思这几天太忙了一直没上

关于那个follow up，当时就是还剩十几分钟，就仅仅和面试官描述了一下思 ...

多谢分享!
楼主能不能具体说一下, 这个格子是怎么存在HDFS上的? 是(x, y, data)这种么? 另外如何在HDFS上面做DFS啊? 是用map reduce么? 多谢了