Practice
1. Given the following Python code snippet implementing the optimized trie approach, what is the output of
maximizeXor(nums, queries) for nums = [0,1,2] and queries = [[3,1],[1,2]]?
class TrieNode:
def __init__(self):
self.children = [null, null]
class Trie:
def __init__(self):
self.root = TrieNode()
def insert(self, num):
node = self.root
for i in range(31, -1, -1):
bit = (num >> i) & 1
if not node.children[bit]:
node.children[bit] = TrieNode()
node = node.children[bit]
def maxXor(self, num):
node = self.root
if not node.children[0] and not node.children[1]:
return -1
max_xor = 0
for i in range(31, -1, -1):
bit = (num >> i) & 1
toggled_bit = 1 - bit
if node.children[toggled_bit]:
max_xor |= (1 << i)
node = node.children[toggled_bit]
else:
node = node.children[bit]
return max_xor
def maximizeXor(nums, queries):
nums.sort()
queries = sorted([(x, m, i) for i, (x, m) in enumerate(queries)], key=lambda x: x[1])
res = [-1] * len(queries)
trie = Trie()
idx = 0
n = len(nums)
for x, m, i in queries:
while idx < n and nums[idx] <= m:
trie.insert(nums[idx])
idx += 1
res[i] = trie.maxXor(x)
return res
print(maximizeXor(nums, queries))easy
Solution
Step 1: Process first query (3,1)
Only nums ≤ 1 are [0,1]. Insert 0 and 1 into trie. maxXor(3) with {0,1} is max(3^0=3,3^1=2)=3.Step 2: Process second query (1,2)
Now nums ≤ 2 are [0,1,2]. Insert 2. maxXor(1) with {0,1,2} is max(1^0=1,1^1=0,1^2=3)=3.Final Answer:
Option B -> Option BQuick Check:
Results match expected XOR values [OK]
Hint: Insert nums ≤ m incrementally, then maxXor query [OK]
Common Mistakes:
- Forgetting to sort queries and nums
- Not inserting all eligible nums before query
- Returning -1 when trie is empty incorrectly
2. You are given a list of buildings represented as triplets (left, right, height). The goal is to output the skyline formed by these buildings as a list of key points where the height changes. Which algorithmic approach guarantees an optimal solution with time complexity O(n log n) for this problem?
easy
Solution
Step 1: Understand problem constraints
The problem requires merging multiple building outlines efficiently, which suggests a divide and conquer strategy to combine partial skylines.Step 2: Compare approaches
Greedy and brute force approaches are either incorrect or inefficient (O(n * maxRight)). Dynamic programming does not naturally fit this problem. Divide and conquer achieves O(n log n) by recursively merging skylines.Final Answer:
Option A -> Option AQuick Check:
Divide and conquer merges partial results efficiently [OK]
Hint: Divide and conquer merges partial skylines efficiently [OK]
Common Mistakes:
- Believing greedy approach works optimally
- Thinking DP applies naturally here
- Assuming brute force is efficient enough
3. Examine the following modified code snippet for the Alien Dictionary problem. Which line contains a subtle bug that can cause incorrect results on certain inputs?
medium
Solution
Step 1: Identify missing prefix invalid case check
Code lacks check for case where longer word precedes its prefix (e.g., "abc" before "ab"), which is invalid.Step 2: Understand consequences of missing this check
Without this, function may return incorrect order or fail to detect invalid input.Final Answer:
Option B -> Option BQuick Check:
Prefix invalid case is critical for correctness [OK]
Hint: Look for missing validation of prefix ordering [OK]
Common Mistakes:
- Ignoring prefix invalid case
- Adding duplicate edges
- Incorrect in-degree updates
4. Suppose the histogram bars can be reused multiple times to form rectangles (i.e., you can select the same bar multiple times consecutively). Which modification to the single pass stack-based algorithm correctly handles this variant?
hard
Solution
Step 1: Understand reuse implication
Allowing reuse means rectangles can extend beyond contiguous bars, breaking the assumption that each bar is used once in a contiguous segment.Step 2: Why stack approach fails
The stack-based method relies on contiguous bars and their indices; it cannot track multiple uses of the same bar or non-contiguous reuse.Step 3: Correct approach
A dynamic programming approach that explicitly counts repeated bars or uses a different state representation is needed to handle reuse correctly.Final Answer:
Option B -> Option BQuick Check:
Stack method assumes single use; DP needed for reuse [OK]
Hint: Reuse breaks contiguous assumption; DP needed [OK]
Common Mistakes:
- Thinking original stack method handles reuse
- Trying to fix width formula only
- Removing sentinel bar to fix reuse
5. Suppose the problem is modified so that words can be reused multiple times in pairs (i.e., pairs (i, j) where i == j are allowed). Which modification to the Trie-based solution correctly handles this variant without double counting pairs?
hard
Solution
Step 1: Understand reuse allowance
Allowing i == j pairs means removing the 'node.index != index' check to include self-pairs.Step 2: Avoid double counting
Removing the check causes duplicates; filtering duplicates after collecting results ensures correctness.Step 3: Evaluate other options
Keeping the check disallows self-pairs; storing multiple indices per node is unnecessary and complex.Final Answer:
Option A -> Option AQuick Check:
Removing check plus duplicate filtering correctly handles reuse [OK]
Hint: Allow self-pairs by removing check, then deduplicate results [OK]
Common Mistakes:
- Removing check without deduplication
- Keeping check and missing self-pairs
- Overcomplicating Trie nodes