Practice
1. Given the following code snippet, what is the final output of
letterCombinations('23')?
from collections import deque
def letterCombinations(digits):
if not digits:
return []
digit_map = {'2': 'abc', '3': 'def', '4': 'ghi', '5': 'jkl',
'6': 'mno', '7': 'pqrs', '8': 'tuv', '9': 'wxyz'}
queue = deque([''])
for digit in digits:
letters = digit_map[digit]
for _ in range(len(queue)):
prev = queue.popleft()
for char in letters:
queue.append(prev + char)
return list(queue)
print(letterCombinations('23'))
easy
Solution
Step 1: Trace queue after processing digit '2'
Initial queue: [''] Letters for '2': 'abc' After processing: ['a', 'b', 'c']Step 2: Trace queue after processing digit '3'
Letters for '3': 'def' For each prefix in ['a', 'b', 'c'], append each letter: 'a' + 'd','e','f' -> 'ad','ae','af' 'b' + 'd','e','f' -> 'bd','be','bf' 'c' + 'd','e','f' -> 'cd','ce','cf' Final queue: ['ad','ae','af','bd','be','bf','cd','ce','cf']Final Answer:
Option C -> Option CQuick Check:
Output matches expected letter combinations for '23' [OK]
Hint: Queue expands combinations breadth-first per digit [OK]
Common Mistakes:
- Mixing order of combinations
- Confusing concatenation order
2. You need to generate all possible orderings of a list of unique integers. Which algorithmic approach guarantees that all permutations are generated without duplicates and with optimal time complexity?
easy
Solution
Step 1: Understand the problem requires all permutations
Generating all permutations means enumerating every possible ordering of the input elements without duplicates.Step 2: Identify the approach that systematically explores all orderings
Backtracking with a used array or in-place swapping explores all permutations by recursively building sequences or swapping elements, ensuring no duplicates and covering all possibilities.Final Answer:
Option A -> Option AQuick Check:
Backtracking is the standard method for generating all permutations [OK]
Hint: Backtracking systematically explores all permutations [OK]
Common Mistakes:
- Thinking greedy or sorting can generate all permutations without duplicates
3. What is the time complexity of the optimal backtracking solution that generates all valid parentheses sequences for input n?
medium
Solution
Step 1: Identify number of valid sequences
The number of valid parentheses sequences is the nth Catalan number, approximately 4^n / (n^{3/2}).Step 2: Analyze backtracking time
Backtracking generates all valid sequences, so time is proportional to number of sequences times sequence length, which is O(4^n / n^{3/2} * n) = O(4^n / n^{1/2}).Final Answer:
Option D -> Option DQuick Check:
Matches known Catalan number growth for valid parentheses [OK]
Hint: Catalan number growth dominates complexity [OK]
Common Mistakes:
- Confusing brute force with backtracking complexity
- Assuming factorial complexity
4. What is the time complexity of the bitmask backtracking solution for counting all N-Queens solutions on an
nxn board?medium
Solution
Step 1: Identify branching factor per row
Each row places one queen in a column not attacked by previous queens, reducing choices roughly by one each time.Step 2: Calculate total recursive calls
Thus, total calls approximate n x (n-1) x (n-2) x ... = n! permutations.Final Answer:
Option D -> Option DQuick Check:
Backtracking prunes invalid columns, yielding O(n!) complexity [OK]
Hint: N-Queens backtracking explores permutations -> O(n!) [OK]
Common Mistakes:
- Confusing bitmask ops with exponential subsets
- Assuming polynomial due to pruning
5. Suppose you want to modify the palindrome partitioning algorithm to allow reuse of substrings in partitions (i.e., substrings can appear multiple times in different partitions). Which change to the algorithm is necessary to correctly handle this variant without losing valid partitions or causing duplicates?
hard
Solution
Step 1: Understand reuse requirement
Reusing substrings means substrings can appear multiple times in different partitions, so path management must allow multiple uses.Step 2: Identify necessary algorithm change
Memoizing palindrome checks improves efficiency by avoiding repeated palindrome computations, while backtracking logic remains unchanged to generate all valid partitions.Final Answer:
Option A -> Option AQuick Check:
Memoization optimizes palindrome checks without affecting partition generation correctness [OK]
Hint: Memoize palindrome checks to optimize without changing backtracking [OK]
Common Mistakes:
- Assuming popping affects substring reuse
- Using visited sets that block valid reuse
- Resetting path incorrectly losing partitions