Given an array of numbers, return array of products of all other numbers using Map Reduce

Question

Recently asked in interview : Solve the below question and then do it through Map Reduce

There is an array A[N] of N numbers. You have to compose an array Output[N] such that Output[i] will be equal to multiplication of all the elements of A[N] except A[i]. For example Output[0] will be multiplication of A[1] to A[N-1] and Output[1] will be multiplication of A[0] and from A[2] to A[N-1]. Solve it without division operator and in O(n).

I was able to solve it normally but not sure how it can be done using MapReduce.

Normal Solution : Given an array of numbers, return array of products of all other numbers (no division)

As the size of integer in the computational model is usually to be bounded by a constant factor from what is needed to hold n, in might not be strictly possible (independent from the exclusion of division). — greybeard
– greybeard, Commented Feb 22, 2015 at 8:56
without some assumption I don't think it can be done in O(n). Assume a case with n mappers and n reducers, and each mapper is getting single element. the number of reducers that needs information from each mapper is n-1 - so you are bounded to O(n^2) communication messages. — amit
– amit, Commented Feb 22, 2015 at 10:18

David Eisenstat · Accepted Answer · 2015-02-22 14:20:23Z

1

As amit notes in the comments, if we're limited to one MapReduce, then, under some reasonable assumptions, about the best we can do is to emulate the quadratic algorithm by taking the array A as key-value pairs

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

mapping it like so

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

and then reducing

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

With lg n MapReduces, we can do a more efficient parallel prefix product.

answered Feb 22, 2015 at 14:20

David Eisenstat

65.7k7 gold badges66 silver badges127 bronze badges

Sign up to request clarification or add additional context in comments.

Collectives™ on Stack Overflow

Given an array of numbers, return array of products of all other numbers using Map Reduce

1 Answer 1

Comments

Your Answer

Linked

Hot Network Questions

Collectives™ on Stack Overflow

1 Answer 1

Comments

Your Answer

Sign up or log in

Post as a guest

Linked

Related