Interview Questions

248.Given two sorted positive integer arrays A(n) and B(n)

Microsoft Interview Questions and Answers

(Continued from previous question...)

248.Given two sorted positive integer arrays A(n) and B(n)

Question:
Given two sorted positive integer arrays A(n) and B(n), we define a set S = {(a,b) | a \in A and b \in B}. Obviously there are n2 elements in S. The value of such a pair is defined as Val(a,b) = a + b. Now we want to get the n pairs from S with largest values.


maybe an answer:


1)A[n]+B[n] will be the largest as the arrays r sorted.
2)Compare x=A[n]+B[n-1] and y=A[n-1]+B[n]...whichever is bigger will be the next number.
3)if x>y then x=A[n]+B[n-2]
else y=A[n-2]+B[n]
4)keep comapring the elements in this fashion..untill u get n nos.
5) this will take O(n) time i guess

(Continued on next question...)

Other Interview Questions