Advice > Software engineering

47 backtracking interview questions [easy, medium, hard]

By Gareth Dwyer on December 13, 2021 How we wrote this article
Backtracking interview questions

To ace your coding interview for a software engineering job, you’ll need to understand backtracking. Backtracking is a technique that solves a problem by exploring possible solutions to its sub-problems, abandoning any that will not lead to a valid solution. This technique can be used to find a single solution or to do an exhaustive search for all solutions to a problem.

Let’s take a look at some typical backtracking questions.

5 typical backtracking interview questions

  • Given an array nums of distinct integers, return all the possible permutations. You can return the answer in any order.

  • Write a program to solve a Sudoku puzzle by filling the empty cells.

  • Given a string s, partition s such that every substring of the partition is a palindrome. Return all possible palindrome partitioning of s.

  • Given a string s and a dictionary of strings wordDict, add spaces in s to construct a sentence where each word is a valid dictionary word. Return all such possible sentences in any order.

  • Given n pairs of parentheses, write a function to generate all combinations of well-formed parentheses

Below, we take a look at 47 backtracking questions and provide you with links to high quality solutions to them. 

This is an overview of what we’ll cover:

  1. Easy backtracking interview questions
  2. Medium backtracking interview questions
  3. Hard backtracking interview questions
  4. Backtracking basics
  5. Backtracking cheat sheet
  6. How to prepare for a coding interview
Click here to practice coding interviews with ex-FAANG interviewers

Let's get started.

1. Easy backtracking interview questions

You might be tempted to try to read all of the possible questions and memorize the solutions, but this is not feasible. Interviewers will always try to find new questions, or ones that are not available online. Instead, you should use these questions to practice the fundamental concepts of backtracking.

As you consider each question, try to replicate the conditions you’ll encounter in your interview. Begin by writing your own solution without external resources in a fixed amount of time.

If you get stuck, go ahead and look at the solution, but then try the next one alone again. Don’t get stuck in a loop of reading as many solutions as possible! We’ve analysed dozens of questions and selected ones that are commonly asked and have clear and high quality answers.

Backtracking questions don't tend to be very easy, so we've only included one example in this first section.

Question 1: Binary watch

2. Medium backtracking interview questions

Here are some moderate-level questions that are often asked in a video call or onsite interview. You should be prepared to write code or sketch out the solutions on a whiteboard if asked.

Question 2: Letter combinations of a phone number
Question 3: Generate parentheses
Question 4: Permutations
Question 5: Subsets
Question 6: Word search
Question 7: Combination sum
Question 8: Word search II
Question 9: Palindrome partitioning
Question 10: Combination sum II
Question 11: Permutations II
Question 12: Subsets II
Question 13: Gray code
Question 14: Combinations
Question 15: Path sum II
Question 16: Combination sum III
Question 17: Matchsticks to square
Question 18: Restore IP addresses
Question 19: Increasing subsequences
Question 20: Beautiful arrangement
Question 21: Letter case permutation
Question 22: All paths from source to target
Question 23: Partition to K equal sum subsets
Question 24: Letter tile possibilities
Question 25: Path with maximum gold
Question 26: Maximum length of a concatenated string with unique characters
Question 27: Split array into Fibonacci sequence
Question 28: Split a string into the max number of unique substrings 
Question 29: Construct the lexicographically largest valid sequence
Question 30: Iterator for combination
Question 31: Splitting a string into descending consecutive values
Question 32: Closest dessert cost

3. Hard backtracking interview questions

Similar to the medium section, these more difficult questions may be asked in an onsite or video call interview. You will likely be given more time if you are expected to create a full solution.

Question 33: Word break II
Question 34: Sudoku solver
Question 35: Stickers to spell word
Question 36: Remove invalid parentheses
Question 37: Expression add operators
Question 38: N-Queens
Question 39: Unique paths III
Question 40: 24 Game
Question 41: N-Queens II
Question 42: Verbal arithmetic puzzle
Question 43: Longest subsequence repeated K times
Question 44: Number of squareful arrays
Question 45: Find minimum time to finish all jobs
Question 46: Maximum path quality of a graph
Question 47: Distribute repeating integers

4. Backtracking basics

In order to crack questions about backtracking, you’ll need to have a strong understanding of the algorithm, how it works, and when to use it.

4.1 What is backtracking?

Backtracking is a form of brute-force problem solving, but with the ability to discard potential solutions early, before they are fully explored. It is an algorithmic paradigm for incrementally finding solutions to problems. As soon as a candidate will not result in the final complete solution being valid, the algorithm will “backtrack.” Therefore, backtracking can be applied when it is possible to test the validity of partial solutions.

Graph coloring provides us with an example of a backtracking algorithm in action. Suppose we have the following map of the continents and have a problem that requires us to give each continent a color such that no two adjacent continents have the same color, using the fewest colors possible. Such a condition is known as a constraint. We can test partial solutions against this constraint and discard them early if it’s clear the constraint won’t be met. This is the essence of backtracking.

Backtracking map coloring

Here, Europe and Asia should not be allowed to have the same color, and it's possible to color the map using only three colors.

It’s easier to view this problem as an undirected graph, like this:

Backtracking undirected graph

Each node is a continent, and the edges between the nodes represent adjacent continents. Now our problem is coloring each node so that no two adjacent nodes have the same color, using the fewest colors (e.g. EU and AS should have different colors).

The solution starts by giving the American (AM) continent the first color – red. Europe (EU) is next, and since AM is already colored red, EU takes the next available color – blue. The algorithm prunes the search tree here by not considering red for EU, because all complete solutions that color AM and EU both red will be invalid. Therefore, the subsolution coloring both AM and EU red is also invalid.

Asia (AS) is next. AS can take red, since it is not connected to AM and the objective is to use the fewest colors. If no coloring of Africa (AF) and Australia and the Pacific Islands (AU) allows AS to be red, then the algorithm will backtrack to this point, and choose the next available color for AS. In that instance, blue will be skipped, since EU has been colored blue in this partial solution, so green might be next. However, in this example red is a valid color for AS with AF getting the color green and AU the color blue.

Backtracking example

4.1.1 Use cases for backtracking

Backtracking can be applied to the following problems:

  • Most Constraint Satisfaction Problems (CSP) like:
    • The knight’s tour problem
    • The n queens problem
    • Solving sudoku
    • Solving crosswords
    • Graph coloring
  • Most brute-force algorithms
  • String pattern matching
  • To adapt a longest common subsequence (LCS) algorithm to print all the LCS in order
  • Finding all subsets of a set
  • Finding all paths from a source to a destination

4.1.2 Example implementation

Backtracking implementations are commonly recursive and similar to depth-first search (DFS), except that only valid subsolutions are expanded in backtracking, whereas DFS will expand all the subsolutions of a node in the search space.

Our graph coloring results in the following implementation:

Here backtracking is just a wrapper around our recursive function. It prepares our solution colors to None for each node in the graph. The first node to color is then selected and if the recursive call succeeds, the solution can be returned.

The recursive call has the base case of current being None, meaning all the nodes have a valid color. Else, every possible color for the current node will be tested by adding it to the solution. If the complete solution is valid then the recursion can end, else backtracking needs to happen by setting the color back to None and the next color or node can be tested.

There are two helper functions that are specific to each problem being solved with backtracking. The first is select_unassigned to select the next node that needs to be colored. In this implementation, this helper function colors the nodes from 0 to n by finding the first open spot in solution. When no open spot is found, it means all the nodes are colored, so None is returned to stop the recursion. The second helper, get_domain_values, returns valid values for each node at a specific subsolution. For our example, this is where the algorithm should not consider red as a color for EU when AM is already red. This is done by looping through all the available colors and only yielding when a neighboring node does not already have the same color (the break together with the else is used in python to continue the outer loop).

The variable graph is an adjacency matrix where a graph[i][j] = 1 means that i and j are neighbors and AM is i = 0; EU is 2; AS is 3; AU is 4; and AF is 5.

Some heuristics can be used on the helper functions to improve performance. For the example above, after AM is red and EU is blue, the only value left for AF is green. But AF is last in the adjacency matrix, so it will be evaluated last. By evaluating AF earlier, the search space can be pruned earlier. Choosing the node with the least possible values is called the minimum-remaining-values (MRV) heuristic, and changes the implementation as follows:

Here, all the empty spots in solution are again found. But rather than stopping at the first empty spot, all valid colors for a spot are found with their count stored in dict in the first loop. If dict is empty, then all the nodes have a color and the recursion can stop, else the MRV is found using a heap.

Other heuristics are also possible. One is deciding the very first node to color using the degree heuristic to reduce the branching factor of future choices. The degree heuristic will choose the node with the largest number of constraints first – for our continents example, it is AF, since it has 4 edges while the other nodes have 3 or 2 edges. The degree heuristic can also be used to break a tie in the MRV heuristic.

Another heuristic is for getting the next color in get_domain_values. In our example, after AM is red and EU is green, it would be a bad idea to give AS blue since that will reduce the valid colors for AF (AF gets blue in the final solution). So trying red for AS first is a better idea by using the least constraining value heuristic.

The idea with heuristics is to reduce branching by selecting nodes that will fail as early as possible, but to go for a maximum search space depth by selecting values (colors) that will fail as late as possible. Together, these two tactics result in earlier success.

4.1.3 How backtracking compares to other algorithms

A brute-force depth-first search (DFS) is similar to backtracking. A brute-force DFS will fully consider all the values (colors) for a node, but backtracking is able to prune its search space by only evaluating values that result in a valid subsolution.

An algorithm that does not need to backtrack when it hits a dead-end is a greedy algorithm. A greedy algorithm only works for optimization problems with the greedy choice property to render the need for backtracking obsolete. But a greedy algorithm can only return a single solution, while backtracking can return all possible solutions.

Need a boost in your career as a software engineer?

If you want to improve your skills as an engineer or leader, tackle an issue at work, get promoted, or understand the next steps to take in your career, book a session with one of our software engineering coaches.

5. Backtracking cheat sheet

Backtracking cheat sheet

You can download the cheat sheet here.

5.1 Related algorithms and techniques

5.2 Cheat sheet explained

The cheat sheet above is a summary of information you might need to know for an interview, but it’s usually not enough to simply memorize it. Instead, aim to understand each result so that you can give the answer in context.

The cheat sheet is broken into time complexity and space complexity (the processing time and memory requirements for backtracking). Backtracking is related to several data structures, which are also included in the cheat sheet.

For more information about time and space requirements of different algorithms, read our complete guide to big-O notation and complexity analysis.

5.2.1 Time complexity

In our graph coloring example, the worst case will give each node its own color. Therefore, let m = |V| be the number of colors. This is also our branching factor at each node in the search space. Since every node needs to be assigned a color, the search space has a height of |V| to give a time-complexity of O(m^|V|).

For all implementations, the get_domain_values will always determine the branching factor and the height will be the same size as solution. But for a problem like the n queens problem, solution is a 2D array with size n^2.

5.2.2 Space complexity

For the graph coloring problem, both solution and the implicit stack have a size of |V| to give a O(|V|) space complexity. The complexity will be bound to solution, and therefore gives the n queens problem a space complexity of O(n^2).

5.2.3 Related algorithms: dynamic programming and local search

Graph coloring can also be solved with other algorithmic paradigms, like dynamic programming. A dynamic programming solution will take O(2.4423^|V|) time and space. In general, dynamic programming offers a polynomial time complexity.

Another way of solving a CSP is to use a local search algorithm. For the n queens problem, a local search algorithm will randomly fill the board with all the queens and then iteratively move conflicting queens (to the least conflicting spot, for example). One such implementation uses the min-conflicts heuristic to solve a 1 million queen problem in an average of 50 steps for a constant time complexity. However, local searches can get stuck at a local minimum.

6. How to prepare for a coding interview

6.1 Practice on your own

Before you start practicing interviews, you’ll want to make sure you have a strong understanding of not only backtracking but also the rest of the relevant algorithms and data structures. You’ll also want to start working through lots of coding problems.

Check out the guides below for lists of questions organized by difficulty level, links to high-quality answers, and cheat sheets.

Algorithm guides

Data structure guides

To get used to an interview situation, where you’ll have to code on a whiteboard, we recommend solving the problems in the guides above on a piece of paper or google doc.

6.2 Practice with others

However, sooner or later you’re probably going to want some expert interventions and feedback to really improve your coding interview skills.

That’s why we recommend practicing with ex-interviewers from top tech companies. If you know a software engineer who has experience running interviews at a big tech company, then that's fantastic. But for most of us, it's tough to find the right connections to make this happen. And it might also be difficult to practice multiple hours with that person unless you know them really well.

Here's the good news. We've already made the connections for you. We’ve created a coaching service where you can practice 1-on-1 with ex-interviewers from leading tech companies. Learn more and start scheduling sessions today.

 

Related articles:

Meta logo rendered in 3D
Software engineeringMar 15, 2024
Meta Job Offer Negotiation (4 Steps to a $50k+ Increase)
Negotiating an offer can feel uncomfortable and stressful. But going through this short-term pain is worth it. As an example, getting a $50k increase is common at the L5 level when negotiating well.
Read more
Facebook production engineer interview
Software engineeringJul 20, 2022
Meta production engineer interview (questions, prep, and process)
Complete guide to Meta (formerly Facebook) production engineer interviews. Learn the interview process, practice with example questions, and learn key preparation tips.
Read more
meta company logos
Software engineeringSep 26, 2024
How to crack the Meta Product Architecture interview
Prepare to ace your Meta product architecture interview with this comprehensive guide. Learn more about the interview and how Meta conducts them, a framework to organize your answers, plus resources to help you prepare.
Read more
Google interview questions
Software engineeringMay 11, 2023
Google interview questions and answers (SWE, PM, etc)
Complete guide to Google interview questions for software engineers, engineering managers, product managers, TPMs and data scientists. Contains 25 example answers, 200+ real Google questions, and links to detailed guides on how to answer.
Read more
coding interview prep
Software engineeringOct 10, 2023
Coding Interview Prep (7 steps to an offer at FAANG)
Coding interview prep made simpler: follow these seven steps and land an offer at Google, Meta, Amazon, etc. Know what to expect, learn an answer method, refresh your data structure and algorithm knowledge, and see lists of practice coding questions.
Read more
Two men coding in a sunny office
Software engineeringNov 22, 2022
49 Amazon coding interview questions (from REAL candidates)
Everything you need to know about Amazon coding interviews, including 49 real and recent sample questions, example answers, and an answer framework.
Read more
a laptop split screen, with code on one side and a video call participant on the other
Software engineeringJul 27, 2023
47 Coding interview examples with answers (in Python, Java, C++, Etc.)
The best coding interview examples / questions with video answers in common coding languages including Python, Java, C++, Javascript, and SQL.
Read more
Meta logo interview process
Software engineeringAug 28, 2024
Meta Interview Process & Timeline: 7 Steps To Getting An Offer
Complete guide to the seven steps of the Meta interview process, including what to expect for each step, preparation resources, and insights from our Meta coaches.
Read more