Python Advanced Level Binary Search Mock Interview

To help you prepare for your Python Advanced Level Binary Search interview, here are 1 interview questions and answer examples.

Get More Information About Our Python Advanced Level Binary Search Interview Questions

Question 1 of 1

Find the path with minimum effort.

Answer

This question focuses on the developer's knowledge of Python binary search and loops.

You are given 2-D matrix heights for size n x m. A hiker is at the top-left cell (0, 0) (cells are 0-indexed). Her target is to reach the bottom-right of the cell (n - 1, m - 1). She can move either up, down, left or right from a cell. Your task is to find minimum effort to reach the destination cell. The effort of a path to the destination is the maximum absolute difference of their heights between two consecutive cells of the path.

/*Example*/

Given matrix-
[[1, 2, 2],
 [3, 8, 2],
 [5, 3, 5]]
	expected output = 2
	explanation:- 	The path 1 -> 2 -> 2 -> 2 -> 5 has an effort of 3.
The path 1 -> 3 -> 5 -> 3 -> 5 has an effort of 2.

Definitions:
â— maximum absolute difference for the path 3 -> 4 -> 2 is maxOf(4 - 3, 4 - 2) = maxOf(1, 2) = 2
â— maximum absolute difference for the path 1 -> 3 -> 5 -> 3 -> 5 is maxOf(2, 2, 2, 2) = 2
â— maximum absolute difference for the path 1 -> 2 -> 2 -> 2 -> 5 is maxOf(1, 0, 0, 3) = 3
Constraints
â— 1 <= n, m <= 100
â— 1 <= heights[i][j] <= 106

Solution:

We can use binary search to solve this problem. If we carefully observe, below the minimum effort, there is no way to reach the destination. Letâ€™s say the minimum effort required is min. If we are asked:-
â— Can we reach our destination with an effort of less than min? The answer is definitely no.
â— Can we reach our destination with an effort greater than or equal to min? The answer is definitely yes.
0 1 â€¦ min - 1 min min + 1 â€¦ max-possible
F F F F T T T T
We can do a binary search from 0 to max-possible. The value of max-possible will be the maximum height of a cell in the given matrix. We have a function canReach answers the two questions above. It will return true if the effort passed is greater than or equal to min, false otherwise.
In canReach function, we will do DFS to at least one path using which we can reach the destination with given effort. We will maintain a 2-D array visited to check which nodes we have visited. We will start from the cell (0, 0). We will explore all the neighboring cells of the current cell viz. up, down, left, and right. While exploring a neighboring cell, we will check if it is visited earlier. If it is not visited, we will check if the absolute height difference between the current cell and the neighboring cell is permitted using the isPermissible function (i.e. check if less than given effort). If it is not permitted, we will not do DFS on this cell, because any path will not be possible through this cell. If it is permitted, we will do DFS on this cell and will explore its neighboring cells. If we have reached the destination cell, we simply return true, because there was at least one path using which we could reach the destination with given effort.

def canReach(effort, heights):
	n,m = len(heights), len(heights[0])
	isPossible = False
	# initialize matrix of size n*m
	visited = [ [False for j in range(m)] for i in range(n)]
	moves = [ (1, 0), (0, 1), (-1, 0), (0, -1) ]

	def isPermissible(x1, y1, x2, y2):
		''' 
			tells whether difference of heights 
			h1 and h2 is under effort
		'''
		h1 = heights[x1][y1]
		h2 = heights[x2][y2]
		return abs(h1 - h2) <= effort

	def dfs(isPossible, x1, y1):
		# we have reached the destination return true
		if (x1 == n - 1 and y1 == m - 1):
			return True
		
		visited[x1][y1] = True

		for dx, dy in moves:
			x = x1 + dx
			y = y1 + dy

			valid_x = 0 <= x < n
			valid_y = 0 <= y < m
			valid_coordinate = valid_x and valid_y

			if not valid_coordinate:
				continue

			valid_jump = isPermissible(x1, y1, x, y)

			if not visited[x][y] and valid_jump:
				isPossible=isPossible or dfs(isPossible, x, y)

		return isPossible

	return dfs(isPossible, 0, 0)


def findMinimumEffort(heights):
	'''
		Make a binary search to choose between left and right
		the minimum value of effort
	'''
	left, right = 0, max([max(row) for row in heights])

	while left < right:
		mid = (left + right) // 2
		res = canReach(mid, heights)
		if res:
			right = mid
		else:
			left = mid + 1
	return right

Time complexity- O(n * m * log(106)
Space complexity- O(n * m)

Written by on May 22nd, 2021

Next Question

1 Python Advanced Level Binary Search Interview Questions & Answers

Below is a list of our Python Advanced Level Binary Search interview questions. Click on any interview question to view our answer advice and answer examples. You may view 5 answer examples before our paywall loads. Afterwards, you'll be asked to upgrade to view the rest of our answers.

1. Find the path with minimum effort.

This question focuses on the developer's knowledge of Python binary search and loops.

You are given 2-D matrix heights for size n x m. A hiker is at the top-left cell (0, 0) (cells are 0-indexed). Her target is to reach the bottom-right of the cell (n - 1, m - 1). She can move either up, down, left or right from a cell. Your task is to find minimum effort to reach the destination cell. The effort of a path to the destination is the maximum absolute difference of their heights between two consecutive cells of the path.

/*Example*/

Given matrix-
[[1, 2, 2],
 [3, 8, 2],
 [5, 3, 5]]
	expected output = 2
	explanation:- 	The path 1 -> 2 -> 2 -> 2 -> 5 has an effort of 3.
The path 1 -> 3 -> 5 -> 3 -> 5 has an effort of 2.

Definitions:
â— maximum absolute difference for the path 3 -> 4 -> 2 is maxOf(4 - 3, 4 - 2) = maxOf(1, 2) = 2
â— maximum absolute difference for the path 1 -> 3 -> 5 -> 3 -> 5 is maxOf(2, 2, 2, 2) = 2
â— maximum absolute difference for the path 1 -> 2 -> 2 -> 2 -> 5 is maxOf(1, 0, 0, 3) = 3
Constraints
â— 1 <= n, m <= 100
â— 1 <= heights[i][j] <= 106

Solution:

We can use binary search to solve this problem. If we carefully observe, below the minimum effort, there is no way to reach the destination. Letâ€™s say the minimum effort required is min. If we are asked:-
â— Can we reach our destination with an effort of less than min? The answer is definitely no.
â— Can we reach our destination with an effort greater than or equal to min? The answer is definitely yes.
0 1 â€¦ min - 1 min min + 1 â€¦ max-possible
F F F F T T T T
We can do a binary search from 0 to max-possible. The value of max-possible will be the maximum height of a cell in the given matrix. We have a function canReach answers the two questions above. It will return true if the effort passed is greater than or equal to min, false otherwise.
In canReach function, we will do DFS to at least one path using which we can reach the destination with given effort. We will maintain a 2-D array visited to check which nodes we have visited. We will start from the cell (0, 0). We will explore all the neighboring cells of the current cell viz. up, down, left, and right. While exploring a neighboring cell, we will check if it is visited earlier. If it is not visited, we will check if the absolute height difference between the current cell and the neighboring cell is permitted using the isPermissible function (i.e. check if less than given effort). If it is not permitted, we will not do DFS on this cell, because any path will not be possible through this cell. If it is permitted, we will do DFS on this cell and will explore its neighboring cells. If we have reached the destination cell, we simply return true, because there was at least one path using which we could reach the destination with given effort.

def canReach(effort, heights):
	n,m = len(heights), len(heights[0])
	isPossible = False
	# initialize matrix of size n*m
	visited = [ [False for j in range(m)] for i in range(n)]
	moves = [ (1, 0), (0, 1), (-1, 0), (0, -1) ]

	def isPermissible(x1, y1, x2, y2):
		''' 
			tells whether difference of heights 
			h1 and h2 is under effort
		'''
		h1 = heights[x1][y1]
		h2 = heights[x2][y2]
		return abs(h1 - h2) <= effort

	def dfs(isPossible, x1, y1):
		# we have reached the destination return true
		if (x1 == n - 1 and y1 == m - 1):
			return True
		
		visited[x1][y1] = True

		for dx, dy in moves:
			x = x1 + dx
			y = y1 + dy

			valid_x = 0 <= x < n
			valid_y = 0 <= y < m
			valid_coordinate = valid_x and valid_y

			if not valid_coordinate:
				continue

			valid_jump = isPermissible(x1, y1, x, y)

			if not visited[x][y] and valid_jump:
				isPossible=isPossible or dfs(isPossible, x, y)

		return isPossible

	return dfs(isPossible, 0, 0)


def findMinimumEffort(heights):
	'''
		Make a binary search to choose between left and right
		the minimum value of effort
	'''
	left, right = 0, max([max(row) for row in heights])

	while left < right:
		mid = (left + right) // 2
		res = canReach(mid, heights)
		if res:
			right = mid
		else:
			left = mid + 1
	return right

Time complexity- O(n * m * log(106)
Space complexity- O(n * m)

Written by Jennie Taylor on May 22nd, 2021