Practice
1. Consider the following code snippet implementing the optimal approach for longest consecutive sequence. What is the value of
max_len returned when the input is [1, 9, 3, 10, 2]?easy
Solution
Step 1: Identify sequence starts
Numbers are {1,2,3,9,10}. Sequence starts are numbers where num-1 not in set: 1 and 9.Step 2: Count consecutive lengths
From 1: sequence is 1,2,3 -> length 3. From 9: sequence is 9,10 -> length 2. Max length is 3.Final Answer:
Option C -> Option CQuick Check:
Longest consecutive sequence is [1,2,3] length 3 [OK]
Hint: Only count sequences starting at numbers without predecessor [OK]
Common Mistakes:
- Counting sequences from every number causing duplicates
- Off-by-one errors in length counting
- Confusing max length with total unique numbers
2. You are given an integer array and a number
k. You need to find the length of the longest contiguous subarray whose sum is divisible by k. Which of the following approaches guarantees an optimal solution in O(n) time?easy
Solution
Step 1: Understand the problem constraints
We want the longest subarray with sum divisible byk. Checking all subarrays with nested loops isO(n^2)and inefficient.Step 2: Recognize prefix sum + remainder pattern
Using prefix sums modulok, if two prefix sums have the same remainder, the subarray between them is divisible byk. Storing earliest indices of remainders in a hash map allowsO(n)solution.Final Answer:
Option D -> Option DQuick Check:
Prefix sums + hash map is classic for subarray sum modulo problems [OK]
Hint: Prefix sums + remainder hash map -> O(n) solution [OK]
Common Mistakes:
- Thinking sliding window works for modulo sums
- Assuming DP is needed for this problem
- Believing brute force is acceptable for large inputs
3. The following code attempts to check if two strings are isomorphic:
def isIsomorphic(s: str, t: str) -> bool:
if len(s) != len(t):
return False
s_to_t = {}
for c1, c2 in zip(s, t):
if c1 in s_to_t:
if s_to_t[c1] != c2:
return False
else:
s_to_t[c1] = c2
return True
medium
Solution
Step 1: Identify missing reverse mapping check
The code only maps fromstotbut does not verify if multiple characters insmap to the same character int.Step 2: Understand consequences
This allows incorrect cases likes="ab"andt="aa"to return True incorrectly.Final Answer:
Option B -> Option BQuick Check:
Bidirectional mapping is required to ensure one-to-one mapping [OK]
Hint: Check both s->t and t->s mappings [OK]
Common Mistakes:
- Assuming single-direction mapping suffices
- Ignoring length check
- Misusing zip causing errors
4. What is the time complexity of the optimal prefix sum + hash map solution for counting subarrays summing to
k in an array of length n?medium
Solution
Step 1: Identify loops and operations
The algorithm iterates over the array once (O(n)) and performs constant-time hash map operations on average.Step 2: Analyze hash map operations
Hash map lookups and inserts are O(1) average, so total time is O(n).Final Answer:
Option A -> Option AQuick Check:
Single pass with O(1) map ops -> O(n) time [OK]
Hint: Hash map average O(1) lookups keep complexity linear [OK]
Common Mistakes:
- Assuming hash map lookups are O(log n)
- Confusing prefix sums with nested loops
- Counting nested loops inside prefix sums
5. What is the average time complexity of the hash map based Two Sum solution that iterates over the array once and checks for complements in the hash map?
medium
Solution
Step 1: Analyze time complexity of hash map lookups
Hash map lookups and insertions are O(1) average time, so iterating once over n elements is O(n).Step 2: Distinguish average vs worst case
Worst case hash collisions can degrade to O(n), but average case is O(1), making total O(n) average time.Final Answer:
Option A -> Option AQuick Check:
Single pass with O(1) average lookups yields O(n) average time [OK]
Hint: Hash map lookups average O(1), total O(n) time [OK]
Common Mistakes:
- Confusing worst-case hash map lookup with average case
- Assuming sorting is required
- Ignoring extra space usage