Goldman Sachs

www.goldmansachs.com
Work in HR? Unlock Free Profile

# Goldman SachsSenior Software Engineer Interview Question

I interviewed in New York, NY and was asked:
"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."

Part of a Senior Software Engineer Interview Review - one of 1,589 Goldman Sachs Interview Reviews

0
of 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