七月脸书

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

分割之后src点和target点之间会存在多个节点，每个中间节点需要保存什么状态呢？map主节点，然后reduce任何一个slave节点吗？

mchzh 发表于 2017-8-4 02:41
分割之后src点和target点之间会存在多个节点，每个中间节点需要保存什么状态呢？map主节点，然后reduce任 ...

在slave上记录每个节点的状态

第4题出现的概率很高，这个是有几个什么样的解法？

daguanyuan 发表于 2017-8-4 04:50
在slave上记录每个节点的状态

就是说每一个节点都要map一次，reduce一次？然后这个节点的输入是下一个节点的输出？这样怎么样保证并行呢？多谢！

楼主这题能否举个例子？ “两个list of int ranges， 求加在一起以后的ranges(重合的range合并组成一个新的range)”

mchzh 发表于 2017-8-4 06:39
第4题出现的概率很高，这个是有几个什么样的解法？

priority_queue O(nlogk), quickselect O(n), 如果需要返回结果有序, n + klogk

flgt2014 发表于 2017-8-4 09:10
楼主这题能否举个例子？ “两个list of int ranges， 求加在一起以后的ranges(重合的range合并组成一个新的 ...

感觉应该是LC57，将输入改为两个list.  两个list 排序， two pointer merge.

一亩三分地严打"顶""好贴""收藏了"之类的垃圾回复帖！被警告三次，系统会自动封杀ID！

想支持楼主，请点击帖子下方的"好苗""分享""收藏"键，酌情给楼主加大米（系统不扣你自己的分）。
积分不够看不了帖子，请参考论坛导航里的"帮助"，"新手提纲"里有攒积分指南facebook how to find friends

http://www.geeksforgeeks.org/design-data-structures-for-a-very-large-social-network-like-facebook-or-linkedln/

不知道按照这个链接的思路    去解第一问 的 follow up 的问题行不行？

mchzh 发表于 2017-8-4 06:45
就是说每一个节点都要map一次，reduce一次？然后这个节点的输入是下一个节点的输出？这样怎么样保证并行 ...

slave上记录的是在slave上的节点状态：该节点有没被访问过。