## Deshaw Inc Interview Question

Software Engineer / DevelopersI think the following algo works

Create a fresh array C of size nXm

First take the least element of A and sum it with every element in the Array B and put the result in C

Note that the first m elements in the C now are already sorted. Repeat the same procedure with second element of A with every element of B. Now merge the first m element of C with the next m elements (Merge routine of merge sort). This should give you O(mn) algo

i think they asked the sum between mapped values..index i of A with index i of B...otherwise no meaning of asking O(n) solution

We can generate the first row solution[0][i] by adding a[i] with b[0]. for subsequent rows we can just add solution[j][i] = solution[j-1][i] + (a[i]-a[i-1]). In this way we need not to hit the b array again, we are just manipulating the solution itself. Thus reducing the complexity of solution to o(n).

How could it be O(n). Since you have compare each element of A with each element of B. its atleast O(mn) where m is size of A and n is Size B

- Ravi June 07, 2010