Goldman Sachs Interview Question: Given an nxn matrix of number... | Glassdoor

Interview Question

Senior Software Engineer Interview New York, NY

Given an nxn matrix of numbers in ascending order in both

  dimensions how would you go about finding if the number y is in the matrix.
Answer

Interview Answer

2 Answers

0

Since elements of each row are in ascending order, we can apply binary search on each row. Following is my initial draft:

1. Go through every row one by one.
2. Check first element and last element of that row.
3. If our value falls within the range then perform a binary search on that row.
     3a. If the value is found, return true.
4. Otherwise go to next row.

Only when all rows have been checked in this way can we be sure that the element doesn't exist in the matrix.

EXECUTION TIME: Best case O(n + log n), Worst case O(n*log n)

CAVEAT: Make sure to go through all rows before deciding that the element doesn't exist. To know why, consider following matrix:

1 2 3 4
5 6 7 9
8 9 10 11
12 13 14 15

Say we are searching for 8. The range of second row is from 5 to 9 but a binary search won't show 8. But we can't return false here because 8 is in the next row.

SOME IMPROVEMENTS:

1. If value being searched (in the example above) is below 1 (element (0,0)) or above 15 (element (n,n)) then return false.

2. If first element of a row is greater than the element being searched then return false.

Okash on Oct 27, 2013
1

Start with the left-bottom element M[n-1,0] in the matrix M looking for Y. If the element is greater than Y move up (M[n-2, 0]), if it is smaller than Y move to the right (M[n-1,1]), if the element is equals to Y you just found it. Do this recursively until you get to the upper right corner (M[0, n-1]), if you didn't find it the number it is not there, return false. This runs in the worse case 2*n therefore the solution is O(n)

Better Answer on Jun 13, 2015

Add Answers or Comments

To comment on this, Sign In or Sign Up.