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:
-
Easy backtracking interview questions
- Medium backtracking interview questions
- Hard backtracking interview questions
- 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.
Question 1: Binary watch
- Text guide (Medium/Competitive Programming)
- Video guide (Owen Smith)
- Code example (xietao0221)
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
- Text guide (After Academy)
- Video guide (NeetCode)
- Video guide (Kevin Naughton Jr.)
- Code example (lei31)
Question 3: Generate parentheses
- Text guide (RedQuark)
- Video guide (Back to Back SWE)
- Code example (brobins9)
Question 4: Permutations
- Text guide (issac3)
- Video guide (NeetCode)
- Code example (OldCodingFarmer)
Question 5: Subsets
- Text guide (LeetCode)
- Video guide (Nideesh Terapalli)
- Video guide (Kevin Naughton Jr.)
- Code example (issac3)
Question 6: Word search
- Text guide (Programmerall)
- Video guide (NeetCode)
- Code example (OldCodingFarmer)
Question 7: Combination sum
- Text guide (AfterAcademy)
- Video guide (NeetCode)
- Code example (OldCodingFarmer)
Question 8: Word search II
- Text guide (Hary Krishnan)
- Video guide (NeetCode)
- Code example (OldCodingFarmer)
Question 9: Palindrome partitioning
- Text guide (xiaodoubao)
- Video guide (NeetCode)
- Code example (Titanwolf)
Question 10: Combination sum II
- Text guide (LeetCode)
- Video guide (NeetCode)
- Video guide (Kevin Naughton Jr.)
- Code example (lchen77)
Question 11: Permutations II
- Text guide (RedGreenCode)
- Video guide (NeetCode)
- Code example (UpTheHell)
Question 12: Subsets II
- Text guide (Medium/The clubhouse)
- Video guide (Nideesh Terapalli)
- Code example (prime_tang)
Question 13: Gray code
- Text guide (GeeksforGeeks)
- Code example (YuSi)
Question 14: Combinations
- Text guide (Dev.to/Codepineapple)
- Video guide (Xavier Elon)
- Video guide (NeetCode)
- Code example (fabrizio3)
Question 15: Path sum II
- Text guide (Zirui)
- Video guide (Deepti Talesra)
- Video guide (Naresh Gupta)
- Code example (jianchao-li)
Question 16: Combination sum III
- Text guide (Aaronice)
- Video guide (Naresh Gupta)
- Code example (jinwu)
Question 17: Matchsticks to square
- Text guide (Massivealgorithms)
- Video guide (NeetCode)
- Code example (YehudisK)
Question 18: Restore IP addresses
- Text guide (Dev.to/Akhil)
- Video guide (Restore IP Addresses)
- Code example (fiona_mao)
Question 19: Increasing subsequences
- Text guide (Zirui)
- Video guide (Happy Coding)
- Code example (chidong)
Question 20: Beautiful arrangement
- Text guide (LeetCode)
- Video guide (Naresh Gupta)
- Code example (shawngao)
Question 21: Letter case permutation
- Text guide (Tutorialcup)
- Video guide (Algorithms Made Easy)
- Code example (tarekd)
Question 22: All paths from source to target
- Text guide (GeeksForGeeks)
- Video guide (Michael Muinos)
- Code example (lee215)
Question 23: Partition to K equal sum subsets
- Text guide (Medium/Trick The Interviewer)
- Video guide (NeetCode)
- Video guide (Back to Back SWE)
- Code example (GraceMeng)
Question 24: Letter tile possibilities
- Text guide (Shareablecode)
- Video guide (Cogent Coder)
- Code example (LeetCode)
Question 25: Path with maximum gold
- Text guide (Tutorialspoint)
- Video guide (Michael Muinos)
- Code example (hiepit)
Question 26: Maximum length of a concatenated string with unique characters
- Text guide (Programmerall)
- Video guide (Kevin Naughton Jr.)
- Video guide (NeetCode)
- Code example (lee215)
Question 27: Split array into Fibonacci sequence
- Text guide (Fatalerrors)
- Video guide (happygirlzt)
- Code example (touchdown)
Question 28: Split a string into the max number of unique substrings
- Text guide (Another casual coder)
- Video guide (Naresh Gupta)
- Code example (kunqian)
Question 29: Construct the lexicographically largest valid sequence
- Text guide (kamyu104)
- Video guide (Happy Coding)
- Code example (db99)
Question 30: Iterator for combination
- Text guide (Mo4tech)
- Video guide (TECH DOSE)
- Code example (archit91)
Question 31: Splitting a string into descending consecutive values
- Text guide (walkccc)
- Video guide (NeetCode)
- Code example (vikrant_pc)
Question 32: Closest dessert cost
- Text guide (ProgrammerAll)
- Video guide (Cherry Coding)
- Code example (vikrant_pc)
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
- Text guide (Java questions)
- Video guide (babybear4812)
- Code example (Cheng_Zhang)
Question 34: Sudoku solver
- Text guide (After Academy)
- Video guide (Back To Back SWE)
- Code example (LeetCode)
Question 35: Stickers to spell word
- Text guide (linlaw)
- Video guide (NeetCode)
- Code example (zestypanda)
Question 36: Remove invalid parentheses
- Text guide (Codertrain)
- Video guide (WorkWithGoogler)
- Video guide (happygirlzt)
- Code example (dietpepsi)
Question 37: Expression add operators
- Text guide (Medium/Nitish Chandra)
- Video guide (Coding Decoded)
- Code example (hiepit)
Question 38: N-Queens
- Text guide (Dev.to/seanpgallivan)
- Video guide (NeetCode)
- Code example (prime_tang)
Question 39: Unique paths III
- Text guide (Medium/Anj)
- Video guide (Naresh Gupta)
- Code example (archit91)
Question 40: 24 Game
- Text guide (dume0011)
- Video guide (happygirlzt)
- Code example (zhang)
Question 41: N-Queens II
- Text guide (Dev.to/seanpgallivan)
- Video guide (code Explainer)
- Code example (AlexTheGreat)
Question 42: Verbal arithmetic puzzle
- Text guide (hiepit)
- Video guide (Algorithms Class)
- Code example (Wangyi)
Question 43: Longest subsequence repeated K times
- Text guide (walkccc)
- Video guide (Happy Coding)
- Code example (DBabichev)
Question 44: Number of squareful arrays
- Text guide (Medium/Nitish Chandra)
- Code example (lee215)
Question 45: Find minimum time to finish all jobs
- Text guide (Programmerall)
- Video guide (Happy Coding)
- Code example (lichuan199010)
Question 46: Maximum path quality of a graph
- Text guide (DBabichev)
- Video guide (Programming Live with Larry)
Question 47: Distribute repeating integers
- Text guide (Krammer Liu)
- Video guide (Happy Coding)
- Code example (alvin-777)
4. How to prepare for a coding interview
4.1 Refresh your knowledge
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. Check out our guides for detailed explanations and useful cheat sheets.
Algorithms explained:
- Depth-first search
- Breadth-first search
- Binary search
- Sorting
- Dynamic programming
- Greedy algorithm
- Backtracking
- Divide and conquer
Data structure guides:
4.2 Practice on your own
Once you’re confident in all of these, you’ll want to start working through lots of coding problems.
For backtracking you can obviously use the questions we’ve listed above. For the other algorithms you need to know, check out the rest of this series:
- Depth-first search interview questions
- Breadth-first search interview questions
- Binary search interview questions
- Sorting interview questions
- Dynamic programming interview questions
- Greedy algorithm interview questions
- Divide and conquer interview questions
We also recommend working through our list of 73 data structure interview questions.
One of the main challenges of coding interviews is that you have to communicate what you are doing as you are doing it. Talking through your solution out loud is therefore very helpful. This may sound strange to do on your own, but it will significantly improve the way you communicate your answers during an interview.
It's also a good idea to work on a piece of paper or google doc, given that in the real interview you'll have to code on a whiteboard or virtual equivalent.
4.3 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!