47 backtracking interview questions [easy, medium, hard]

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.

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

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.

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.

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.

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.

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:

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.

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.

5. Backtracking cheat sheet

You can download the cheat sheet here.

5.1 Related algorithms and techniques

• Recursion

• Soduko solving

• Local searching

• Ariadne’s thread

• Constraint programming

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

• Depth-first search
• Breadth-first search
• Binary search
• Sorting
• Dynamic programming
• Greedy algorithm
• Divide and conquer

Data structure guides

• Arrays
• Strings
• Linked lists
• Stacks and Queues
• Trees
• Graphs
• Maps
• Heap

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.

Any questions about backtracking interview questions?

If you have any questions about backtracking or coding interviews in general, don't hesitate to ask them in the comments below. All questions are good questions, so go ahead!