## Deshaw Inc Interview Question for Software Engineer / Developers

• 0

Comment hidden because of low score. Click to expand.
0
of 0 vote

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

Comment hidden because of low score. Click to expand.
0

I 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

Comment hidden because of low score. Click to expand.
0
of 0 vote

Really interesting, if someone can generate m*n sums in O(n) time...

Comment hidden because of low score. Click to expand.
0

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

Comment hidden because of low score. Click to expand.
0

we know the least element in both the matrixes. why dont we take least element in A and least element in B and make sum that to create matrix C?

Comment hidden because of low score. Click to expand.
0
of 0 vote

a lot of unclear questions here, which are really annoying. kind of wasting time!

Comment hidden because of low score. Click to expand.
0
of 0 vote

go for O(n^2) soln.

Comment hidden because of low score. Click to expand.
0
of 0 vote

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).

Comment hidden because of low score. Click to expand.
0

but for each element of b i.e m elememt you add n element so it will give o(mn)

Comment hidden because of low score. Click to expand.
0
of 0 vote

i think creating m*n elements can not be done in o(n) becoz each operation will take o(1) atleast

Comment hidden because of low score. Click to expand.
0
of 0 vote

Agree, it can not be done in O(n) time. Here is algo:
1) create array C[m*n];
2) generate all sums and store them in C
3) Use count sort which has linear time to sort C in decreasing order

Name:

Writing Code? Surround your code with {{{ and }}} to preserve whitespace.

### Books

is a comprehensive book on getting a job at a top tech company, while focuses on dev interviews and does this for PMs.

### Videos

CareerCup's interview videos give you a real-life look at technical interviews. In these unscripted videos, watch how other candidates handle tough questions and how the interviewer thinks about their performance.