## xyz Interview Question for Developer Program Engineers

Country: United States
Interview Type: Phone Interview

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

There are surprisingly 4 solutions to this problem! We can start with the brute force and improve from O(n^2) -> O(nlogn) -> O(n) -> O(lgn). I have outlined the 4 solutions below with explanations.
PS:- I would appreciate if you can plz upvote :P, I put in some effort to clearly explain the solution. :P

Python solution:

``````# Brute Force - Look at each element one by one
# O(n^2) solution
def searchVersion1(matrix, target):
for i, row in enumerate(matrix):
for j, sq in enumerate(row):
if sq == target:
return True
return False

# Since each row is sorted, perform binary search
# Since there are n rows, the runtime is O(n*lgn)
def searchVersion2(matrix, target):
def binarySearchHelper(row, target, low, high):
while low <= high:
mid = (low + high) // 2
if row[mid] == target:
return True
elif row[mid] < target:
low = mid + 1
elif row[mid] > target:
high = mid - 1
return False

for i, row in enumerate(matrix):
if binarySearchHelper(row, target, 0, len(row)-1):
return True
return False

# O(n) solution
# We can start from top-right corner of the matrix
# and move up to bottom right. If current element < target, move down
# else if element > target, move left. If we go out of bounds, we can
def searchVersion3(matrix, target):
x, y = 0, len(matrix[0])-1

while 0 <= x < len(matrix) and 0 <= y < len(matrix[0]):
currentElement = matrix[x][y]
if currentElement == target:
return True
elif currentElement < target:
x += 1 # Move down
elif currentElement > target:
y -= 1 # Move left
return False

# O(lgn) solution
# Treat the 2-d matrix as a 1-d sorted array
# and just map the indices using math while applying binary search.
def searchVersion4(matrix, target):
rows, cols = len(matrix), len(matrix[0])
low, high = 0, rows * cols - 1

while low <= high:
mid = (low + high) // 2
curRow = mid // cols
curCol = mid % cols
currentElement = matrix[curRow][curCol]
if currentElement == target:
return True
elif currentElement < target:
low = mid + 1
else:
high = mid - 1
return False

matrix =  \
[
[1 , 3, 5, 7, 9] ,
[11,13,15,16,20],
[21,22,23,24,25],
[30,32,35,40,45],
]

print(searchVersion1(matrix, 23)) # True
print(searchVersion1(matrix, 28)) # False
print(searchVersion1(matrix, 5)) # True
print(searchVersion1(matrix, 10))# False
print('#' * 20)
print(searchVersion2(matrix, 23))# True
print(searchVersion2(matrix, 28))# False
print(searchVersion2(matrix, 5))# True
print(searchVersion2(matrix, 10))# False
print('#' * 20)
print(searchVersion3(matrix, 23))# True
print(searchVersion3(matrix, 28))# False
print(searchVersion3(matrix, 5))# True
print(searchVersion3(matrix, 10))# False
print('#' * 20)
print(searchVersion4(matrix, 23))# True
print(searchVersion4(matrix, 28))# False
print(searchVersion4(matrix, 5))# True
print(searchVersion4(matrix, 10))# False``````

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

Binary search to find the row and binary search to find the element in the row, log(n) + log(n). Complexity should be log(n).

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

Also, you can do a single binary search, if you can mange the index conversion from two dimensional to single dimensional. As in (row, column) (2,3) means index 2n+3. So you can run in binary search on from 1 and n*n.

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.