Hash map, array and prefix sum interview questions
14 coding interview questions on hash maps, arrays and prefix sums, each with the correct answer and a full explanation.
Hash maps and arrays
One pass Two Sum stores value to index in a dict. Which loop body is correct on every input, including nums = [3, 4], target = 6, which has no valid pair?
for i, x in enumerate(nums):
# body
Show answer
Answer
Check target - x in seen, then set seen[x] = i
Checking before inserting guarantees an element never pairs with itself. Inserting first finds 3 when x = 3 and returns [0, 0]. The even parity rule is arbitrary and breaks normal inputs. Sorting loses the original indices and adds O(n log n) for nothing.
Group anagrams over n lowercase words of max length k. Which key gives O(n k) total time?
Show answer
Answer
A tuple of 26 letter counts
A count tuple is built in O(k) and identifies the letter multiset exactly. Sorting each word costs O(k log k), correct but slower. A character code sum collides ("ad" and "bc"). A set drops multiplicity, so "aab" and "abb" collide.
Return true if any value appears at least twice in nums, n up to 105, values any 32 bit integer. Which approach is O(n) expected time?
Show answer
Answer
Insert into a hash set and stop on the first repeat
A hash set gives O(1) expected insert and lookup. Sorting works but is O(n log n). A boolean array indexed by value needs 232 slots and fails on negatives. Comparing every pair is O(n2).
Longest Consecutive Sequence (length of the longest run of consecutive integers in an unsorted array) must run in O(n). You put all values in a set. Which rule keeps the total work O(n)?
Show answer
Answer
Only start counting from x when x - 1 is not in the set
Starting only at run beginnings means each value is visited by one count walk, so the total is O(n). Starting from every x is O(n2) on one long run. Sorting is O(n log n). Starting where x + 1 is missing marks run ends, so counting upward from there finds nothing; the rule must match the direction you walk.
Top K Frequent Elements (return the k most frequent values in nums), n up to 105, any k. Which method is O(n) time?
Show answer
Answer
Count with a dict, then bucket values by frequency in a list of size n + 1
Frequencies are bounded by n, so bucketing by frequency is O(n). Sorting is O(n log n). A size k heap is O(n log k), good but not O(n) for large k. Calling max k times is O(n k).
Check whether t is an anagram of s where both may contain any Unicode characters. Which is correct and O(n)?
Show answer
Answer
Compare Counter(s) == Counter(t)
Counter keys by any character and compares multiplicities. A 26 slot array assumes lowercase ASCII and breaks on other characters. Sets ignore counts. Ord sums collide for different strings.
Your Two Sum uses a Python dict. The interviewer asks: if an adversary picks keys whose hashes all collide, what is the worst case cost of one lookup?
Show answer
Answer
O(n)
Average is O(1), but if many keys collide the probe sequence can touch O(n) entries, which the Python wiki lists as the amortized worst case. O(1) is the average, not the worst. O(log n) is a balanced tree, which dict is not. O(n log n) has no basis for one lookup.
You want to memoize on a list argument in Python. Which key works as a dict key?
Show answer
Answer
tuple(lst)
Tuples of hashable items are hashable. A list is mutable and raises TypeError. A set is unhashable and also drops order and duplicates. Wrapping in a list is still a list.
Isomorphic strings: s = "badc", t = "baba". A solution maps each char of s to t with one dict and returns True. What did it miss?
Show answer
Answer
It never checks the reverse mapping, so two s chars map to the same t char
Isomorphism needs a bijection. The forward map b to b, a to a, d to b, c to a is consistent, but b and d both map to b, so the answer is False and a reverse dict (or a set of used targets) is required. Equal lengths say nothing about structure. Sorting destroys positions. True is wrong because t reuses b for two different s letters.
Ransom note: can note be built from the letters in magazine, each letter used once? Give the approach and complexity.
Show answer
Answer
Count magazine letters with a Counter, then decrement for each note letter and fail when a count goes below zero. O(m + n) time, O(alphabet) space. Pitfall: checking membership only, not counts, accepts "aa" from "a".
Subarray Sum Equals K (count subarrays that sum to k) with a prefix count map. Why initialize counts = {0: 1}?
Show answer
Answer
So subarrays that start at index 0 are counted
A prefix equal to k means the whole prefix is a valid subarray, which needs an empty prefix of sum 0 counted once. A KeyError is avoided by get, not by seeding. k can be 0. defaultdict defaults missing keys to 0, which still misses the empty prefix.
Many range sum queries on a fixed array. With P[0] = 0 and P[i + 1] = P[i] + a[i], what is sum(a[l..r]) inclusive?
Show answer
Answer
P[r + 1] - P[l]
P[r + 1] covers a[0..r] and P[l] covers a[0..l-1]. P[r] minus P[l] drops a[r]. P[r] minus P[l - 1] uses the other indexing convention and fails at l = 0. P[r + 1] minus P[l + 1] drops a[l].
Contiguous Array: longest subarray with equal 0s and 1s. What do you store in the hash map?
Show answer
Answer
First index where each running balance (+1 for 1, -1 for 0) appears
Equal balances at i and j mean the subarray between is balanced, and the earliest i gives the longest. Storing the last index shortens results. Counts answer how many, not how long. Indices of zeros alone ignore ones.
