## Amazon Interview Question for Software Engineer / Developers

Country: United States
Interview Type: Phone Interview

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

Perform Binary search in each and every row. I think this is optimal with complexity O(n log n)

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

1-check the first element of the each row if first element is greater than the item to be searched ignore that row.
2-check the last element of each row if it is less than item to be searched ignore this row also.
do 1 and\or 2 for every row and after that apply the binary search on remaining row.

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

@Maxximus, @Kuldeep
Your estimate for time complexity is wrong. Its still O(nlogn). Filtering rows on basis of range does not guarantee that the number of valid rows will be very small compared to n. You can easily imagine a matrix for which n=1000000 and number of invalid rows = 100. In these cases, even after filtering the number of rows is O(n) and for each row a binary search means O(logn) time for that row. Thus, it still comes out O(nlogn).

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

Hmm.... anyone knows better than O (n log n) ??
O(n log n) is trivial .....

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

Feel the same. O(n log n)

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

It's not possible to do better than O(nlogn) if each row provides no information regarding anything in any other row. You'll have to do a binary search on each row.

You have n independent problems, the optimal solution to each of which is O(log n). So O(n log n) is the minimum.

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

we can skip some rows checking if the number lies in the range for the row.
but worst case nlogn

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

Also, if the matrix is like { 1 4 7
2 5 8
3 6 9}
and if we want to search for 5, we can't eliminate any rows by looking at the range. We are compelled to do the binary search on every row

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

I think it should be O(nlogn)...in the worst case ..and yaa we can check whether element is present between the range of first element of row and last element of row and accordindgly we can call binary search

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

The matrix is sorted row-wise also means you consider the elements in each column, they are also sorted top down. So, we can first perform a binary search on say the first column, reach a particular row and then perform another binary search on the row to get to the required element.
For a MxN matrix, this solves the problem in O(log M) + O (log N)
You just need to search the required row !!

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

First of all, according to the problem statement, the columns are unsorted. So this solution is clearly out.

Second of all, that wouldn't work even if the columns were sorted. Think about it: just because you know that the element is > arr[k][0] and < arr[k+1][0], for some k, doesn't mean the element is positioned somewhere like arr[k][i], for some i. The element could be at arr[0][j] for some j, for example.

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

Yes eugene. That's correct. This works only for the case where the elements are sorted row wise and also column wise. Basically I meant I have some completely sorted matrix as we go through the rows down the matrix. Sorry I missed the explicitly stated point that the elements are not sorted column-wise

Comment hidden because of low score. Click to expand.
-1
of 1 vote

Guys. I dont know who is using my name and posting rubbish comments

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

LOL LOL LOL

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

FOF!

Comment hidden because of low score. Click to expand.
-1
of 1 vote

Create a one dimentional sorted array outofit which can be done in o(n) time
Now searching for an element in this wll take o(logn). This will give us o(n) + o(logn) time i.e. o(n) time. Please let me know if i am wrong here

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

It takes O(n^2 log n) to make a sorted 1D array out of this.

Comment hidden because of low score. Click to expand.
-1
of 1 vote

The program logic is very easy. It has been made little tricky. :-)

Comment hidden because of low score. Click to expand.
-1
of 1 vote

find the row by checking the range and then do a binary search on the row

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

You can't do binary search on unsorted row!

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

@Lybo : As per question .. rows are sorted

Comment hidden because of low score. Click to expand.
-1
of 1 vote

find the row by checking the range and then do a binary search on the row

Comment hidden because of low score. Click to expand.
-1
of 1 vote

I think O(nlogn) is correct

Comment hidden because of low score. Click to expand.
-1
of 1 vote

Maintaining a HashMap<RowNo,Lowest Element> would enable O(n - no of elements in a row) search

Comment hidden because of low score. Click to expand.
-2
of 2 vote

Just as Kuldeep mentioned, check the range and then do a binary search on the particular row. Checking the range takes O(n) as we need to scan N rows and this will dominate the algorithm complexity. So it does take only O(n) instead of O(nlogn)

Comment hidden because of low score. Click to expand.
-2
of 4 vote

We need to use matrix properties in this ques. start from any element in the matrix and compare with elements which is around that element, then move your pointer to the element which is more close to it then again repeat the process until you find the element.

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

it will take O(n^2) time in worst case.
what if the number we are searching for, is not present in the matrix?

Comment hidden because of low score. Click to expand.
-2
of 2 vote

Using magnifying glass! LOL!

Comment hidden because of low score. Click to expand.
-2
of 2 vote

You f***kng people!!!!!!!!! I am a LOLER LOL LOL LOL!!!! CLAP CLAP CLAP

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

LOL!

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.