Practice
1. You are given a binary array and need to find the length of the longest contiguous subarray with an equal number of 0s and 1s. Which algorithmic approach guarantees an optimal O(n) time solution?
easy
Solution
Step 1: Understand problem constraints
The problem requires finding the longest contiguous subarray with equal 0s and 1s efficiently.Step 2: Identify algorithmic pattern
Using prefix sums transformed by treating 0 as -1, and a hash map to store earliest prefix sum indices, allows O(n) time detection of subarrays with zero sum difference.Final Answer:
Option B -> Option BQuick Check:
Prefix sum + hash map is classic for equal 0/1 subarray [OK]
Hint: Prefix sums + hash map track equal 0s and 1s efficiently [OK]
Common Mistakes:
- Thinking greedy can find longest equal 0/1 subarray
- Using DP that tracks counts separately is inefficient
- Brute force is correct but not optimal
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. Suppose the data structure must support duplicate elements (i.e., multiple identical values can be inserted). Which modification to the optimal Insert Delete GetRandom design correctly supports duplicates while maintaining average O(1) insert, remove, and getRandom?
hard
Solution
Step 1: Understand duplicate challenge
Duplicates mean one value maps to multiple indices; a single index in pos is insufficient.Step 2: Modify data structures
Use a hash map from value to a set of indices to track all positions; update sets on insert/remove; swap-delete still works by updating sets accordingly.Step 3: Verify O(1) operations
Set insert/remove are O(1) average; array swap-delete remains O(1); getRandom picks random index from array.Final Answer:
Option A -> Option AQuick Check:
Tracking multiple indices per value enables duplicates with O(1) ops [OK]
Hint: Map values to sets of indices to handle duplicates [OK]
Common Mistakes:
- Using counts only loses position info
- Ignoring duplicates breaks getRandom correctness
- Using linked list loses O(1) random access
5. Suppose the problem is modified so that characters in
s can be reused multiple times to map to characters in t (i.e., the mapping is many-to-one, not one-to-one). Which of the following approaches correctly adapts the isomorphic strings check to this new requirement?hard
Solution
Step 1: Understand the relaxed mapping constraint
Since multiple characters inscan map to the same character int, the reverse mapping fromttosis no longer one-to-one and need not be checked.Step 2: Adapt the algorithm
Using a single hash map fromstotsuffices to ensure eachscharacter maps consistently, ignoring reverse mapping.Step 3: Evaluate other options
Bidirectional maps are unnecessary and would incorrectly reject valid mappings; brute force is inefficient; sorting does not preserve character positions.Final Answer:
Option D -> Option DQuick Check:
Single-direction mapping fits many-to-one mapping requirement [OK]
Hint: Relaxed mapping removes need for reverse checks [OK]
Common Mistakes:
- Keeping bidirectional checks unnecessarily
- Using brute force causing inefficiency
- Sorting strings which breaks order