Goldman Sachs

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

Goldman Sachs Senior 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."
Add Tags [?]
Answer

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

Answers & Comments

0
of 0
votes

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

To comment on this question, Sign In with Facebook or Sign Up

Tags are like keywords that help categorize interview questions that have something in common.