Practice Backtracking Questions for DSA Coding Interviews

11. Find All Paths from Source to Destination in a Graph

Required Input:

{0: [1, 2], 1: [3], 2: [3], 3: []}, source=0, destination=3

Expected Output:

[[0, 1, 3], [0, 2, 3]]

Code In Python

def all_paths_source_to_dest(graph, source, destination): # Write your logic here pass # Prefilled input graph = { 0: [1, 2], 1: [3], 2: [3], 3: [] } source = 0 destination = 3 print(all_paths_source_to_dest(graph, source, destination))

Run Code?

Click Run Button to view compiled output

12. Find All Possible Combinations of a Phone Number

Required Input:

23'

Expected Output:

['ad', 'ae', 'af', 'bd', 'be', 'bf', 'cd', 'ce', 'cf']

Code In Python

def letter_combinations(digits): # Write your logic here pass # Prefilled input digits = '23' print(letter_combinations(digits))

Run Code?

Click Run Button to view compiled output

13. Solve the N-Queens Problem

Required Input:

N=4

Expected Output:

[['.Q..', '...Q', 'Q...', '..Q.'], ['..Q.', 'Q...', '...Q', '.Q..']]

Code In Python

def solve_n_queens(N): # Write your logic here pass # Prefilled input N = 4 print(solve_n_queens(N))

Run Code?

Click Run Button to view compiled output

14. Find the Kth Permutation Sequence

Required Input:

n=3, k=3

Expected Output:

Code In Python

def get_kth_permutation(n, k): # Write your logic here pass # Prefilled input n = 3 k = 3 print(get_kth_permutation(n, k))

Run Code?

Click Run Button to view compiled output

15. Find All Valid Sudoku Solutions

Required Input:

[['5','3','.','.','7','.','.','.','.'], ..., ['.','.','.','.','8','.','.','7','9']]

Expected Output:

['5', '3', '4', '6', '7', '8', '9', '1', '2']
['6', '7', '2', '1', '9', '5', '3', '4', '8']
['1', '9', '8', '3', '4', '2', '5', '6', '7']
['8', '5', '9', '7', '6', '1', '4', '2', '3']
['4', '2', '6', '8', '5', '3', '7', '9', '1']
['7', '1', '3', '9', '2', '4', '8', '5', '6']
['9', '6', '1', '5', '3', '7', '2', '8', '4']
['2', '8', '7', '4', '1', '9', '6', '3', '5']
['3', '4', '5', '2', '8', '6', '1', '7', '9']

Code In Python

def solve_sudoku(board): # Write your logic here pass # Prefilled input board = [ ['5','3','.','.','7','.','.','.','.'], ['6','.','.','1','9','5','.','.','.'], ['.','9','8','.','.','.','.','6','.'], ['8','.','.','.','6','.','.','.','3'], ['4','.','.','8','.','3','.','.','1'], ['7','.','.','.','2','.','.','.','6'], ['.','6','.','.','.','.','2','8','.'], ['.','.','.','4','1','9','.','.','5'], ['.','.','.','.','8','.','.','7','9'] ] solve_sudoku(board)

Run Code?

Click Run Button to view compiled output

16. Find All Unique Paths in a Grid with Obstacles

Required Input:

[[1, 1, 0], [1, 1, 1], [0, 1, 1]]

Expected Output:

[['Down', 'Right', 'Down', 'Right'], ['Down', 'Right', 'Right', 'Down'], ['Right', 'Down', 'Down', 'Right'], ['Right', 'Down', 'Right', 'Down']]

Code In Python

def unique_paths_with_obstacles(grid): # Write your logic here pass # Prefilled input grid = [ [1, 1, 0], [1, 1, 1], [0, 1, 1] ] print(unique_paths_with_obstacles(grid))

Run Code?

Click Run Button to view compiled output

17. Find the Shortest Hamiltonian Path in a Graph

Required Input:

[[0, 10, 15, 20], [10, 0, 35, 25], [15, 35, 0, 30], [20, 25, 30, 0]]

Expected Output:

Code In Python

def tsp(graph): # Write your logic here pass # Prefilled input graph = [ [0, 10, 15, 20], [10, 0, 35, 25], [15, 35, 0, 30], [20, 25, 30, 0] ] print(tsp(graph))

Run Code?

Click Run Button to view compiled output

18. Find All Unique Factor Combinations

Required Input:

n=12

Expected Output:

[[2, 2, 3], [2, 6], [3, 4]]

Code In Python

def factor_combinations(n): # Write your logic here pass # Prefilled input n = 12 print(factor_combinations(n))

Run Code?

Click Run Button to view compiled output

19. Solve the Knight’s Tour Problem

Required Input:

N=5

Expected Output:

[0, 5, 14, 9, 20]
[13, 8, 19, 4, 15]
[18, 1, 6, 21, 10]
[7, 12, 23, 16, 3]
[24, 17, 2, 11, 22]

Code In Python

def solve_knights_tour(N): # Write your logic here pass # Prefilled input N = 5 print(solve_knights_tour(N))

Run Code?

Click Run Button to view compiled output

20. Find All Possible Word Breaks in a String

Required Input:

catsanddog', ['cat', 'cats', 'and', 'sand', 'dog']

Expected Output:

['cat sand dog', 'cats and dog']

Code In Python

def word_break(s, word_dict): # Write your logic here pass # Prefilled input s = 'catsanddog' word_dict = ['cat', 'cats', 'and', 'sand', 'dog'] print(word_break(s, word_dict))

Run Code?

Click Run Button to view compiled output

2 of 3