Amazon Interview Question Software Engineer / Developers
@lol:
Using an extra array is a direct approach, but YOUNGIFY...is no doubt a very good concept...infact a new concept.
I agree, although it's not completely "new method"... it's just a derivation of HEAPIFY procedure in MIN/MAX heap.
I mentioned all three methods just to convey the interviewer that you know many ways to solve it. Most interviewers expect time-versus-space trade offs to develop an algorithm. First method needs extra O(n^2) space which reduces time by O(n) factor.
I agree with u....but on the other side...K way merging approach is just the another form of HEAPIFY, with a disadvantage...that, we cannot use the information of sorted columns(for K way merging we can look in to the array as either row sorted or column sorted but not both)
Adding to the suggested algorithm of calling youngify, I think we can reduce the number of YOngify calls.
Suppose we have a 5X5 Matrix. The median will have 12 keys less than itself, hence we can replace all the elements that are to the right and bottom of i = 4 and j = 3 (i and j are 0 1 2....) with infinity right at the beginning. So a youngify will run faster every time.
i = 4 and j = 3 because, for i=3 and j=2 we already have 4 * 3 = 12 elements which are for sure lesser.
On a bigger matrix i think it will save a lot of time because whn u do an extractMin and replace it with infinity, this infinity needs to travel shorter distance now.
@anonymous:
Can u plz replicate ur thought process here:
Queries:
- Every time u extract an element from the matrix...u have to call YOUNGIFY(an O(N) operation)..to restore properties of the matrix.
- How r u moving at the diagonal path as every time u have to extract element from A[0][0] only.
Can u plz give us the trace of ur algoritm....it would be helpful.
@bytestorm: your analysis is wrong. Youngify is called (N*N)/2 times. Hence complexity would be O(N^3) in that way.
- lol September 05, 2011Simpler is to read all elements to an O(N^2) sized array, and running median-of-median. Complexity O(N^2).
K-way merging is another option, that would be O(N^2 logN) complexity.