When engineers walk into a DSA mock interview, they are usually well prepared on arrays, trees, and graphs. The questions that trip them up most often come from topics that get less preparation time: recursion and backtracking, tries, union find, bit manipulation, and sorting algorithm internals.
These topics appear across FAANG and product company interviews at every level. They are not bonus topics. They are expected competencies that show up both as standalone problems and as components of harder problems built on top of them.
If you want to practice these in a real one-on-one mock interview with an engineer who will push you on follow-up questions, book a mock interview on Intervue.io.
The rest of this guide gives you the questions, the solutions, and what interviewers are evaluating when they ask them.
Recursion and Backtracking
Recursion is one of the most frequently tested patterns in DSA interviews and one of the most commonly misunderstood. Candidates who cannot write recursive solutions fluently, or who cannot explain the call stack clearly, lose significant points in interviews even when they know the algorithm conceptually.
What interviewers are actually testing with recursion questions
They are testing whether you can identify the base case and the recursive case separately and clearly. They are testing whether you can trace through the call stack on a small example without running code. And they are testing whether you can recognise when recursion is the right tool and when it adds unnecessary complexity.
Problem: Generate All Subsets of a Set (Power Set)
Difficulty: Medium. Asked at: Amazon, Google, Meta
Problem Statement
Given an integer array nums with no duplicates, return all possible subsets. The solution set must not contain duplicate subsets. The order of the output does not matter.
Input: nums = [1, 2, 3]
Output: [[], [1], [2], [3], [1,2], [1,3], [2,3], [1,2,3]]
Approach
At each position in the array, we make a binary choice: include the element or exclude it. This gives us 2^n subsets for an array of length n. Use backtracking: add the current element to the path, recurse, then remove it to explore the path without it.
Solution
python
def subsets(nums):
result = []
def backtrack(start, path):
result.append(list(path)) # every path is a valid subset
for i in range(start, len(nums)):
path.append(nums[i])
backtrack(i + 1, path)
path.pop() # undo the choice
backtrack(0, [])
return result
Trace Through [1, 2, 3]
backtrack(0, []) -> add []
backtrack(1, [1]) -> add [1]
backtrack(2, [1,2]) -> add [1,2]
backtrack(3, [1,2,3]) -> add [1,2,3]
backtrack(3, [1,3]) -> add [1,3]
backtrack(2, [2]) -> add [2]
backtrack(3, [2,3]) -> add [2,3]
backtrack(3, [3]) -> add [3]
Result: [[], [1], [1,2], [1,2,3], [1,3], [2], [2,3], [3]] (8 subsets = 2^3) ✓
Complexity
- Time: O(n x 2^n) - 2^n subsets, each of average length n/2
- Space: O(n) for the recursion stack
Problem: Permutations of an Array
Difficulty: Medium. Asked at: Amazon, Google, Meta, Apple
Problem Statement
Given an array of distinct integers, return all possible permutations.
Input: nums = [1, 2, 3]
Output: [[1,2,3],[1,3,2],[2,1,3],[2,3,1],[3,1,2],[3,2,1]]
Approach
Swap each element with the current position, recurse on the rest, then swap back to restore the original array. This generates all orderings in place.
Solution
python
def permute(nums):
result = []
def backtrack(start):
if start == len(nums):
result.append(list(nums))
return
for i in range(start, len(nums)):
nums[start], nums[i] = nums[i], nums[start] # swap in
backtrack(start + 1)
nums[start], nums[i] = nums[i], nums[start] # swap back
backtrack(0)
return result
Complexity
- Time: O(n x n!) - n! permutations each of length n
- Space: O(n) for the recursion stack
What interviewers follow up with: "What if the array has duplicates?" Sort the array first and skip an element if it is the same as the previous one at the same recursion level.
Tries
A trie (prefix tree) is a tree data structure where each node represents a character and paths from root to node represent prefixes. Tries are the right data structure whenever you need prefix-based lookup: autocomplete, spell checking, IP routing tables, and word search problems.
What interviewers test with trie questions
They test whether you can implement a trie from scratch. Many candidates know what a trie is but cannot build one under interview pressure. They also test whether you understand the space tradeoff: a trie uses more memory than a hash map for exact lookups but enables prefix search which a hash map cannot do efficiently.
Problem: Implement a Trie
Difficulty: Medium. Asked at: Google, Amazon, Meta
Problem Statement
Implement a trie with insert, search, and startsWith methods.
Trie trie = Trie()
trie.insert("apple")
trie.search("apple") # True
trie.search("app") # False
trie.startsWith("app") # True
trie.insert("app")
trie.search("app") # True
Approach
Each node holds a dictionary of children (one per character) and a boolean marking whether it is the end of a complete word. Insert walks the trie character by character, creating nodes that do not exist. Search walks and returns True only if the final node is marked as a word end. startsWith walks and returns True if the prefix exists, regardless of whether it ends a word.
Solution
python
class TrieNode:
def __init__(self):
self.children = {}
self.is_end = False
class Trie:
def __init__(self):
self.root = TrieNode()
def insert(self, word):
node = self.root
for char in word:
if char not in node.children:
node.children[char] = TrieNode()
node = node.children[char]
node.is_end = True
def search(self, word):
node = self.root
for char in word:
if char not in node.children:
return False
node = node.children[char]
return node.is_end
def startsWith(self, prefix):
node = self.root
for char in prefix:
if char not in node.children:
return False
node = node.children[char]
return True
Complexity
- Time: O(m) for each operation, where m is the length of the word or prefix
- Space: O(m x n) where n is the number of words inserted
Problem: Word Search II (Trie + Backtracking)
Difficulty: Hard. Asked at: Google, Amazon
Problem Statement
Given a board of characters and a list of words, return all words that can be found in the board. Words are formed by sequentially adjacent cells (horizontally or vertically). The same cell cannot be used more than once in a word.
Approach
Build a trie from all the words. Then run DFS from every cell on the board. At each step, check whether the current path prefix exists in the trie. If not, prune the search. If we reach a node marked as a word end, add it to the results.
This is more efficient than running a separate DFS for each word because the trie allows us to explore all words simultaneously in one DFS pass.
Solution
python
def find_words(board, words):
root = TrieNode()
for word in words:
node = root
for char in word:
if char not in node.children:
node.children[char] = TrieNode()
node = node.children[char]
node.is_end = True
rows, cols = len(board), len(board[0])
result = set()
def dfs(node, r, c, path):
if node.is_end:
result.add(path)
if r < 0 or r >= rows or c < 0 or c >= cols:
return
char = board[r][c]
if char not in node.children or char == '#':
return
board[r][c] = '#' # mark visited
for dr, dc in [(1,0),(-1,0),(0,1),(0,-1)]:
dfs(node.children[char], r + dr, c + dc, path + char)
board[r][c] = char # restore
for r in range(rows):
for c in range(cols):
dfs(root, r, c, "")
return list(result)
Complexity
- Time: O(m x n x 4^L) where m x n is the board size and L is the max word length
- Space: O(total characters in all words) for the trie
Union Find (Disjoint Set Union)
Union Find is a data structure that tracks which elements belong to the same connected component. It supports two operations: find (which component does this element belong to) and union (merge two components). With path compression and union by rank, both operations run in nearly O(1) amortised time.
What interviewers test with union find questions
They test whether you know when union find is the right tool. The answer is: whenever you need to dynamically track connected components and merge them efficiently. Graph connectivity problems, cycle detection in undirected graphs, and Kruskal's minimum spanning tree algorithm all use union find.
Problem: Number of Provinces
Difficulty: MediumAsked at: Amazon, Google
Problem Statement
There are n cities. You are given an n x n matrix isConnected where isConnected[i][j] = 1 if city i and city j are directly connected. A province is a group of directly or indirectly connected cities with no other cities outside the group. Return the number of provinces.
Input: isConnected = [[1,1,0],[1,1,0],[0,0,1]]
Output: 2
Solution with Union Find
python
def find_circle_num(isConnected):
n = len(isConnected)
parent = list(range(n))
rank = [0] * n
def find(x):
if parent[x] != x:
parent[x] = find(parent[x]) # path compression
return parent[x]
def union(x, y):
px, py = find(x), find(y)
if px == py:
return
if rank[px] < rank[py]:
px, py = py, px
parent[py] = px # union by rank
if rank[px] == rank[py]:
rank[px] += 1
for i in range(n):
for j in range(i + 1, n):
if isConnected[i][j] == 1:
union(i, j)
return sum(1 for i in range(n) if find(i) == i)
Complexity
- Time: O(n^2 x alpha(n)) where alpha is the inverse Ackermann function, effectively O(1)
- Space: O(n)
Bit Manipulation
Bit manipulation questions test whether you understand how numbers are represented in binary and how bitwise operators work. These questions appear across all levels, from entry-level screens to senior rounds, and they often feel like tricks until you know the patterns.
What interviewers are testing
They test whether you know the standard bit manipulation patterns: checking if a bit is set, setting or clearing a bit, checking if a number is a power of two, counting set bits, and XOR tricks for finding unique elements.
Problem: Single Number
Difficulty: Easy. Asked at: Amazon, Google, Meta
Problem Statement
Given a non-empty array of integers where every element appears twice except for one, find that single one. Must run in O(n) time and O(1) space.
Input: nums = [4, 1, 2, 1, 2]
Output: 4
Approach
XOR has two properties that make this trivial: any number XORed with itself is 0, and any number XORed with 0 is itself. XOR all elements together. Every pair cancels out, leaving only the single element.
Solution
python
def single_number(nums):
result = 0
for num in nums:
result ^= num
return result
Trace Through [4, 1, 2, 1, 2]
result = 0
result ^= 4 -> 4
result ^= 1 -> 5
result ^= 2 -> 7
result ^= 1 -> 6 (1^1=0, 4^2=6... let us verify: 0^4^1^2^1^2 = 4^(1^1)^(2^2) = 4^0^0 = 4)
result ^= 2 -> 4
Output: 4 ✓
Complexity
- Time: O(n)
- Space: O(1)
Problem: Number of 1 Bits (Hamming Weight)
Difficulty: Easy. Asked at: Amazon, Google, Apple
Problem Statement
Write a function that takes an unsigned integer and returns the number of set bits (1 bits) in its binary representation.
Input: n = 11 (binary: 1011)
Output: 3
Approach
Use the bit trick: n & (n - 1) clears the lowest set bit of n. Count how many times you can do this before n becomes 0.
Solution
python
def hamming_weight(n):
count = 0
while n:
n &= n - 1 # clear lowest set bit
count += 1
return count
Why n & (n-1) works: Subtracting 1 from n flips the lowest set bit and all bits below it. ANDing with n clears exactly those bits.
Complexity
- Time: O(k) where k is the number of set bits
- Space: O(1)
Problem: Reverse Bits
Difficulty: Easy. Asked at: Amazon, Apple
Problem Statement
Reverse the bits of a given 32-bit unsigned integer.
Input: n = 43261596 (binary: 00000010100101000001111010011100)
Output: 964176192 (binary: 00111001011110000010100101000000)
Approach
Process bit by bit. Extract the least significant bit of n, shift it into the correct position in the result, then shift n right by 1. Repeat for all 32 bits.
Solution
python
def reverse_bits(n):
result = 0
for _ in range(32):
result = (result << 1) | (n & 1) # shift result left, add LSB of n
n >>= 1 # shift n right
return result
Complexity
- Time: O(1) — always exactly 32 iterations
- Space: O(1)
Sorting Algorithm Internals
Interviewers at FAANG and product companies do not ask you to implement bubble sort. They ask questions that require you to understand why different sorting algorithms have different performance characteristics and when to choose each.
What interviewers test on sorting
They test whether you can reason about time and space complexity across sorting algorithms. They test whether you know that merge sort is stable and quicksort is not. They test whether you understand why Python's sort (Timsort) is O(n log n) in all cases while quicksort degrades to O(n^2) on already-sorted input with a naive pivot.
Problem: Sort Colors (Dutch National Flag)
Difficulty: Medium. Asked at: Amazon, Google, Meta
Problem Statement
Given an array with values 0, 1, and 2 representing red, white, and blue, sort them in place so all 0s come first, then 1s, then 2s. Must do it in one pass using constant extra space.
Input: nums = [2, 0, 2, 1, 1, 0]
Output: [0, 0, 1, 1, 2, 2]
Approach
Use three pointers: low (next position for 0), mid (current element), high (next position for 2). When mid sees a 0, swap with low and advance both. When mid sees a 2, swap with high and only advance high (the swapped element needs to be re-examined). When mid sees a 1, just advance mid.
Solution
python
def sort_colors(nums):
low, mid, high = 0, 0, len(nums) - 1
while mid <= high:
if nums[mid] == 0:
nums[low], nums[mid] = nums[mid], nums[low]
low += 1
mid += 1
elif nums[mid] == 2:
nums[mid], nums[high] = nums[high], nums[mid]
high -= 1 # do not advance mid: re-examine swapped element
else:
mid += 1
Complexity
- Time: O(n) — single pass
- Space: O(1) — in place
Sorting Algorithm Comparison: What Every Candidate Should Know
Merge Sort: O(n log n) in all cases. Stable (equal elements maintain their relative order). Requires O(n) extra space. The right choice when stability is required or when sorting linked lists (where random access is expensive).
Quick Sort: O(n log n) average, O(n^2) worst case on already-sorted input with a naive pivot. Not stable. O(log n) space for the recursion stack. The right choice for in-place sorting of arrays when average-case performance matters and worst-case can be mitigated with randomised pivot selection.
Heap Sort: O(n log n) in all cases. Not stable. O(1) extra space. Rarely used in practice because of poor cache performance, but appears in interviews as the answer to "sort in place with no extra space and guaranteed O(n log n)."
Counting Sort: O(n + k) where k is the range of input values. Not comparison-based. The right choice when the range of values is small and known. Stable.
Timsort (Python's built-in sort): O(n log n) worst case, O(n) best case on nearly-sorted input. Stable. Hybrid of merge sort and insertion sort. Always use Python's built-in sort in interviews unless you are asked specifically to implement a sorting algorithm.
What Interviewers Are Looking For Across These Topics
When you come into a mock interview on these topics, the questions that follow the solution matter as much as the solution itself.
For recursion: can you trace through the call stack on paper without running the code? Can you identify exactly where the path.pop() is needed and why removing it breaks the solution?
For tries: can you explain why you chose a trie over a hash set for this problem? Can you describe the memory layout and how children are stored?
For union find: can you explain what path compression does and why it speeds up repeated find operations? Can you draw the tree structure before and after a union operation?
For bit manipulation: can you explain why n & (n-1) clears the lowest set bit rather than some other bit? Can you reason through an XOR problem step by step without a calculator?
For sorting: can you reason about when quicksort degrades and what pivot strategy prevents it? Can you identify whether a sorting problem requires stability and choose accordingly?
FAQs
Do bit manipulation questions still appear in FAANG interviews? Yes, regularly. They appear as standalone easy problems in phone screens and as components of medium and hard problems in onsite rounds. Single Number, Hamming Weight, and missing number problems using XOR are among the most frequently reported.
Is union find required at SDE1 level? Union find problems appear at SDE2 level and above at FAANG companies. At SDE1 level, BFS and DFS solutions to connected component problems are more commonly expected. For product companies and IT services roles, union find is less commonly tested.
Should I implement a trie from scratch in a real interview? Yes. Interviewers at Google and Amazon expect candidates to be able to implement a TrieNode class with a children dictionary and an is_end flag from memory. Practice writing it until you can do it in under 5 minutes.
What is the most commonly misunderstood backtracking concept? The restore step. Candidates who understand the recursive logic often forget to undo the choice after returning from the recursive call, which causes paths to bleed into each other. The path.pop() or the swap-back in permutations must mirror exactly what was done before the recursive call.
How is Timsort different from merge sort? Timsort is a hybrid algorithm. It first identifies naturally occurring runs in the input (already-sorted or reverse-sorted sequences) and uses insertion sort on small runs. It then merges those runs using merge sort logic. This makes it highly efficient on real-world data, which is often partially sorted, while maintaining the O(n log n) worst-case guarantee.
Summary
The DSA topics that trip up the most candidates in mock interviews are not the ones they practiced least. They are the ones they practiced only in isolation, never under the conditions of a live interview with follow-up questions.
Recursion requires tracing the call stack out loud. Tries require implementing from memory. Union find requires explaining path compression clearly. Bit manipulation requires reasoning through binary arithmetic step by step. Sorting requires knowing not just which algorithm to name but why and when it is the right choice.
Book a mock interview on Intervue.io to practice these topics with a real engineer who will push you past the solution into the reasoning that interviewers actually evaluate.
Visit intervue.io
