Apply your knowledge of recursion and backtracking with these common interview problems. Try to solve them on your own before looking at the solution!
Write a recursive function to reverse a given string.
Example:
Input: "hello"
Output: "olleh"
The base case is an empty string, which is its own reverse. The recursive step involves taking the first character, putting it at the end, and calling the function on the rest of the string.
reverse("hello") = reverse("ello") + 'h'
= (reverse("llo") + 'e') + 'h'
= ...and so on.
def reverse_string(s):
# Base Case: if the string is empty, return it
if len(s) == 0:
return s
# Recursive Case:
else:
# Call the function on the substring (from index 1 to end)
# and append the first character to the end
return reverse_string(s[1:]) + s[0]
# Example usage:
my_string = "hello"
print(f"Original: {my_string}")
print(f"Reversed: {reverse_string(my_string)}")
Given n pairs of parentheses, write a function to generate all combinations of well-formed parentheses.
Example:
Input: n = 3
Output: ["((()))", "(()())", "(())()", "()(())", "()()()"]
This is a classic backtracking problem. We build the string from left to right. We can add a '(' if we have open parentheses left to place. We can add a ')' if the number of closing parentheses is less than the number of open parentheses used so far. The recursion stops when the string length is $2 \times n$.
def generate_parentheses(n):
solutions = []
def backtrack(current_string, open_count, close_count):
# Base Case: if the string is complete
if len(current_string) == n * 2:
solutions.append(current_string)
return
# Recursive Cases:
# 1. Add an open parenthesis if we can
if open_count < n:
backtrack(current_string + "(", open_count + 1, close_count)
# 2. Add a close parenthesis if it's valid to do so
if close_count < open_count:
backtrack(current_string + ")", open_count, close_count + 1)
backtrack("", 0, 0)
return solutions
# Example usage:
n = 3
print(f"Valid parentheses for n={n}: {generate_parentheses(n)}")
Given an array nums of distinct integers, return all the possible permutations. You can return the answer in any order.
Example:
Input: nums = [1, 2, 3]
Output: [[1,2,3], [1,3,2], [2,1,3], [2,3,1], [3,1,2], [3,2,1]]
We use backtracking to explore all possible arrangements. The core idea is to iterate through the numbers. For each number, if it hasn't been used yet in the current permutation, we add it, then recursively call the function to build the rest of the permutation. After the recursive call returns, we "backtrack" by removing the number, allowing it to be used in a different position in other permutations.
def permute(nums):
result = []
def backtrack(current_permutation, remaining_nums):
# Base Case: if there are no remaining numbers, we have a full permutation
if not remaining_nums:
result.append(list(current_permutation))
return
# Recursive Case: iterate through remaining numbers
for i in range(len(remaining_nums)):
# Choose a number
num = remaining_nums[i]
# Explore
new_remaining = remaining_nums[:i] + remaining_nums[i+1:]
current_permutation.append(num)
backtrack(current_permutation, new_remaining)
# Backtrack (un-choose)
current_permutation.pop()
backtrack([], nums)
return result
# Example usage:
nums = [1, 2, 3]
print(f"Permutations of {nums}: {permute(nums)}")
Write a program to solve a Sudoku puzzle by filling the empty cells. An empty cell is indicated by the character '.'.
Constraint: You may assume that the given Sudoku puzzle will have a single unique solution.
This problem is solved using backtracking. We find an empty cell (a '.'). Then, we try to place numbers from 1 to 9 in that cell. For each number, we check if placing it is valid (doesn't violate Sudoku rules). If it's valid, we recursively call our solver to continue filling the board. If the recursive call successfully solves the puzzle, we are done. If not, we "backtrack" by resetting the cell to '.' and try the next number.
def solve_sudoku(board):
def is_valid(row, col, num):
# Check row
if num in board[row]:
return False
# Check column
for i in range(9):
if board[i][col] == num:
return False
# Check 3x3 box
box_row_start = (row // 3) * 3
box_col_start = (col // 3) * 3
for i in range(3):
for j in range(3):
if board[box_row_start + i][box_col_start + j] == num:
return False
return True
def find_empty():
for i in range(9):
for j in range(9):
if board[i][j] == '.':
return (i, j)
return None
def backtrack():
empty_cell = find_empty()
if not empty_cell:
return True # Puzzle solved
row, col = empty_cell
for i in range(1, 10):
num = str(i)
if is_valid(row, col, num):
board[row][col] = num # Choose
if backtrack(): # Explore
return True
board[row][col] = '.' # Backtrack
return False
backtrack()
return board
# Example usage will be more complex and require a full board as input.
# This code provides the core logic.