七月脸书

老题不少
1. MxN 01矩阵迷宫，看有没有 路徑从A点到B点。 Followup：如果矩阵超大需要机群存放，如何设计一个并行算

您好！
本帖隐藏的内容需要积分高于 188 才可浏览
您当前积分为 0。
使用VIP即刻解锁阅读权限或查看其他获取积分的方式

游客，您好！
本帖隐藏的内容需要积分高于 188 才可浏览
您当前积分为 0。
VIP即刻解锁阅读权限 或 查看其他获取积分的方式
Unlock interview details and practice with AI
Curated Interview Questions from Top Companies

ooldown time
4. 求点集中离给定点最近的K个点

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

关于那个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 什么的，面试官说和他想的差不多，应该算是混过去了

第一问的follow up，抛砖引玉来啦.
分割矩阵：按照行的方式分割矩阵，然后每个子矩阵分别存到不同的机器。
逻辑算法：先广搜索。
具体算法（将先广搜索运用到分布式集群上）：采用类似Map-Reduce的方式
Map:master根据节点所在的具体机器的位置发送请求，如：告诉我A节点可达的所有点;
Reduce:slave返回本次请求的结果至master.
这样的方式来模拟先广搜索，来最后找到路径。

别的实在想不到了，有错误的地方请指教。

LZ基本都是原题呀，求问第一题的follow up是如何回答的？ :)

同样问follow up是怎么回答的

同問第一題followup，謝謝樓主

两个list of int ranges， 求加在一起以后的ranges(重合的range合并组成一个新的range) 这题是扫一遍就行了吗?

Followup：如果矩阵超大需要机群存放，如何设计一个并行算法找到AB间的路径 也想知道follow up 怎解...

求大神解答

daguanyuan 发表于 2017-8-4 01:29
第一问的follow up，抛砖引玉来啦.
分割矩阵：按照行的方式分割矩阵，然后每个子矩阵分别存到不同的机器。 ...

嗯，slave 告诉 master 新的可到的点，master 告诉有这些点的slave 继续处理。应该可行。这样是一开始只处理两个seed。如果能更多nodes同时一起处理感觉会更好。

3b 就是 621 task scheduler 么 ？