View All num of num See all Photos Goldman Sachs This employer has taken extra steps to respond to reviews and provide job seekers with accurate company information, photos, and reviews. Interested for your company?Learn More. www.goldmansachs.com Work in HR? Unlock Free Profile Overview Reviews Salaries Interviews Jobs Photos Benefits 1.9k Reviews 7.4k Salaries 1.9k Interviews Follow Add Review or Salary Follow Add Review or Salary Interview Question Senior Software Engineer Interview New York, NY Goldman Sachs 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. Tags: See more , See less 8 Answer Add Tags Flag as Inappropriate Thank you! Your feedback has been sent to the team and we'll look into it. Oops! We're sorry but your feedback didn't make it to the team. Your input is valuable to us — would you mind trying again? Send Answer Interview Answer 1 Answer ▲ 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 45 6 7 98 9 10 1112 13 14 15Say 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 Flag as Inappropriate Thank you! Your feedback has been sent to the team and we'll look into it. Oops! We're sorry but your feedback didn't make it to the team. Your input is valuable to us — would you mind trying again? Send Add Answers or Comments To comment on this, Sign In or Sign Up.