Grokking Modern System Design Interview for Engineers & Managers
Ace your System Design Interview and take your career to the next level. Learn to handle the design of applications like Netflix, Quora, Facebook, Uber, and many more in a 45-min interview. Learn the RESHADED framework for architecting web-scale applications by determining requirements, constraints, and assumptions before diving into a step-by-step design process.
You may remember the maze game from childhood where a player starts from one place and ends up at another destination via a series of steps. This game is also known as the rat maze problem.
A rat starts at a position (source
) and can only move in two directions:
The goal is to reach the destination.
In computer science, we can solve the maze game using array indexes or the maze matrix.
First, we generate the corresponding matrix of the maze. White represents the area where the rat can travel and is represented by 1
. Grey represents the area where the rat cannot go and is represented by 0
.
{1, 0, 0, 0}
{1, 1, 0, 1}
{0, 1, 0, 0}
{1, 1, 1, 1}
For the given maze the path above should ideally be good to go from beginning to end.
To solve the maze problem, the program is required to generate the following matrix, where 1
represents the path taken by the rat to travel from source to destination.
{1, 0, 0, 0}
{1, 1, 0, 0}
{0, 1, 0, 0}
{0, 1, 1, 1}
Now, we all must be thinking, “how does a program interpret what path to take, where to move, or what happens in case of a dead-end?”
Well, the answer is easy – it uses an approach called the Backtracking Algorithm. Backtracking is an algorithmic technique used to recursively solve problems by trying to build a solution incrementally.
The program is solved one step at a time.
In the example below, we will be adopting this backtracking recursive approach. The example will follow a path and always keep a check if a destination is reached. If yes
, a result will be returned. If No
, it will backtrack to explore other paths.
Firstly, create a matrix to store your solution. It should contain all zeros and should be of the same size as the maze matrix.
Make a recursive call with the position of the rat in the matrix:
If the position provided is invalid, return from the function.
Otherwise, mark the position as 1 in the solution matrix.
Recursively call for position (i+1, j), (i, j+1), (i-1, j), and (i, j-1).
# size of maze matrixN = 4# check is position is valid to movedef checkpos(maze, x, y ):if x >= 0 and x < N:if y >= 0 and y < N:if maze[x][y] == 1:return Truereturn Falsedef Helper(maze):# solution matrixsol = [[0, 0, 0, 0],[0, 0, 0, 0],[0, 0, 0, 0],[0, 0, 0, 0]]if mazesolver(maze, 0, 0, sol) == False:return Falsefor i in sol:for j in i:print(str(j) + " ", end ="")print("")return Truedef mazesolver(maze, x, y, sol):# if destination reachedif x == N - 1 and y == N - 1 and maze[x][y]== 1:sol[x][y] = 1return True# Check if position is validif checkpos(maze, x, y) == True:if sol[x][y] == 1:return Falsesol[x][y] = 1# forward directionif mazesolver(maze, x + 1, y, sol) == True:return True## if above doesnt work, move in down directionif mazesolver(maze, x, y + 1, sol) == True:return True# if above two do not work, move back in left direction. Backtrackif mazesolver(maze, x - 1, y, sol) == True:return True# Else, move upwardsif mazesolver(maze, x, y - 1, sol) == True:return True# if nothing works, backtrack and set the pos to 0 as we# will not be using the path.sol[x][y] = 0return Falsemaze = [[1, 0, 0, 0],[1, 1, 0, 1],[0, 1, 0, 0],[1, 1, 1, 1]]Helper(maze)
RELATED TAGS
CONTRIBUTOR
Grokking Modern System Design Interview for Engineers & Managers
Ace your System Design Interview and take your career to the next level. Learn to handle the design of applications like Netflix, Quora, Facebook, Uber, and many more in a 45-min interview. Learn the RESHADED framework for architecting web-scale applications by determining requirements, constraints, and assumptions before diving into a step-by-step design process.