给定一个数字数组，使用Map Reduce返回所有其他数字的乘积数组

Question

最近在采访中被问到：解决以下问题，然后通过Map Reduce进行

有一个由N个数字组成的数组A[N]。你必须组成一个数组Output[N]，这样Output[i]将等于除A[i]之外的所有A[N]元素的乘积。例如，Output[0]将是A[1]到A[N-1]的乘积，Output[1]将是A[0]和从A[2]到A[N-1的乘积。在没有除法运算符的情况下，在O（n）中求解它。

我能够正常地解决它，但不确定如何使用MapReduce来完成它。

正常解决方案：给定一个数字数组，返回所有其他数字的乘积数组（无除法）

Answer 1

amit在评论中指出，如果我们被限制为一个MapReduce，那么，在一些合理的假设下，我们能做的最好的事情就是通过将数组A作为键值对来模拟二次算法

0: (n, A[0]), 1: (n, A[1]), ..., n-1: (n, A[n-1]),

像这样映射

i: (n, A[i]) ->
  [(  0: A[i]), ..., (i-1: A[i]),
   (i+1: A[i]), ..., (n-1: A[i])],

然后降低

i: [A[0], ..., A[i-1], A[i+1], ... A[n-1]] ->
  i: A[0] ... A[i-1] A[i+1] ... A[n-1].

使用lg nMapReduceds，我们可以做一个更高效的并行前缀产品。