Amazon Interview Report
- 0of 0 votes
AnswersIm sure everyones heard of this.
Matrix with rows and column sorted. Find a particular element.
I mentioned the O(m+n) solution. He asked to make it better.
Thought for a while, then told him that you start with the last element of the first row and once you find the row which might contain the element, do a binary search on that row (since its sorted).
This further brings down the complexity to O(m+logn).
He said make it even better.
So I said do a binary search on the last column and look for the row where the element in the previous row is smaller and the element in the current row is greater than or equal to the target.
So the complexity becomes O(log m + log n).
He said ok.
When I was about to code this, he said there are two ways to implement it.
1) One you implement the dual binary search method.
2) Make use of the facts that the rows and columns are sorted.
Thought this over for a while and mentioned that instead of doing two binary searches, you can do just one considering the entire matrix as a linear array and doing binary search.
The complexity would be log(m*n)=log(m) + log(n).(Same as the previous optimal solution).
There would be some logic involved in translating the indices to (row,col) pairs. I got this working, but he wanted me to return the (row,col) pair if the element was found or (-1,-1) if not found.
For this he gave me the function signature
void find(int A[][10], int m, int n, int target,int&row, int col)
which is what I couldn't figure out. Here m = number of rows and n=no of cols
Here is the solution I gave// Initially pass start as 0 and end as m*n when calling function find(int A[][10],int start,int end,int target,int cols) { int mid = (start+end)/2; if (start > end) { element not found; } int r = mid/cols; int c = mid%cols; if(A[r][c] == target) { element found; } else if (target>A[r][c]) { start = mid+1; find(A[][10],start,end,target,cols); } else { end = mid-1; find(A[][10],start,end,target,cols); } }
Can somebody tell me how i can return the (row,col) pairs (yes! return two values) using the function signature he mentioned.
- sreemana@buffalo.edu March 30, 2012 in United States
PS: Thanks for reading the whole post.. I know its kinda long. But I hope it helps someone.| Report Duplicate | Flag | PURGE
Amazon Software Engineer / Developer - 0of 0 votes
AnswerDifference between threads and process.
- sreemana@buffalo.edu March 30, 2012 in United States
Simple enough.| Report Duplicate | Flag | PURGE
Amazon Software Engineer / Developer