A surprising number of interview problems reduce to two questions: “have I seen this before?” and “how many times?”. Without extra memory, answering either means scanning what you’ve already processed, and doing that for every element gives you O(n²). A hash map (or its keys-only sibling, a hash set) answers both in average constant time, so the whole pass drops to O(n).
That trade, memory for time, is the single most common optimisation in coding interviews. The skill isn’t knowing that hash maps exist. It’s choosing the right key, the right value and the right order of operations.
Membership: Two Sum and the order of operations
Two Sum asks for the indexes of two numbers that add up to a target. The brute force checks every pair. The hash map version walks once and, for each number x, asks whether its complement target - x has already appeared:
def two_sum(nums, target):
index_of = {} # value -> index where we saw it
for i, x in enumerate(nums):
need = target - x
if need in index_of: # look up first...
return [index_of[need], i]
index_of[x] = i # ...then record this value
return []
print(two_sum([2, 7, 11, 15], 9), two_sum([3, 2, 4], 6), two_sum([3, 3], 6))[0, 1] [1, 2] [0, 1]The value stored is the index, because that’s what the problem wants back. The order inside the loop is the detail interviewers watch for. Swap the two steps so you insert first and look up second, and an element can be matched with itself:
insert first: [0, 0]For [3, 2, 4] with target 6, the first element 3 goes into the map, then the lookup for 6 - 3 = 3 finds it, and you return the same index twice. Looking up before inserting means the map only ever contains elements before the current one, which is exactly the set of valid partners. The same version also handles [3, 3] correctly, because the second 3 finds the first one already stored.
Time is O(n) on average, space O(n) for the map. If the input were sorted you could do it in O(1) space with two pointers, which is a good follow-up to mention.
Counting: anagrams and frequency tables
Two strings are anagrams if every character appears the same number of times in both. One clean way: count the first string, then spend those counts on the second.
def is_anagram(s, t):
if len(s) != len(t):
return False
counts = {}
for ch in s:
counts[ch] = counts.get(ch, 0) + 1
for ch in t:
if counts.get(ch, 0) == 0: # t has a letter s ran out of
return False
counts[ch] -= 1
return True
print(is_anagram("listen", "silent"), is_anagram("rat", "car"), is_anagram("aab", "abb"))True False FalseThe third case is the one that catches set-based shortcuts. "aab" and "abb" contain the same set of letters, {a, b}, but not the same counts. If a problem talks about how many times something appears, you need a map to counts, not a set.
Python’s collections.Counter does the counting for you and adds conveniences like most_common:
from collections import Counter
print(Counter("mississippi").most_common(2))[('i', 4), ('s', 4)]When the key space is small and known, such as lowercase English letters, a fixed array of 26 integers indexed by ord(ch) - ord('a') does the same job with less overhead and is technically O(1) space. Mention it if the interviewer pushes on memory; a map is fine otherwise, and it also handles Unicode without changes. Valid Anagram is the problem to practise this on.
JavaScript: count with a Map, not an object
In JavaScript, using a plain object as a counter works until a key collides with something the object inherits. Count the words in "the constructor called the toString method":
const words = "the constructor called the toString method".split(" ");
const counts = {};
for (const w of words) counts[w] = (counts[w] || 0) + 1;
console.log(counts);
const m = new Map();
for (const w of words) m.set(w, (m.get(w) ?? 0) + 1);
console.log(m);{
the: 2,
constructor: 'function Object() { [native code] }1',
called: 1,
toString: 'function toString() { [native code] }1',
method: 1
}
Map(5) {
'the' => 2,
'constructor' => 1,
'called' => 1,
'toString' => 1,
'method' => 1
}counts["constructor"] isn’t undefined on a fresh object: it’s the inherited Object function. So counts[w] || 0 returns the function, adding 1 turns it into a string, and the count is garbage. A Map has no inherited keys, accepts any value as a key (not just strings), and keeps insertion order. Object.create(null) also avoids the problem, but Map is the clearer choice in an interview.
Choosing the key
Grouping problems are really key-design problems. Group Anagrams asks you to bucket words that are anagrams of each other. Two words belong together when their sorted letters match, so the sorted letters are the key. In Python, though, the obvious first attempt fails:
groups = {}
for w in ["eat", "tea", "tan"]:
groups.setdefault(sorted(w), []).append(w)TypeError: cannot use 'list' as a dict key (unhashable type: 'list')sorted returns a list, and lists are mutable, so they can’t be hashed. If a key could change after insertion, the map would file it under the wrong bucket. Convert it to an immutable form first:
def group_anagrams(words):
groups = {}
for w in words:
key = "".join(sorted(w)) # or tuple(sorted(w)); lists can't be keys
groups.setdefault(key, []).append(w)
return list(groups.values())
print(group_anagrams(["eat", "tea", "tan", "ate", "nat", "bat"]))[['eat', 'tea', 'ate'], ['tan', 'nat'], ['bat']]Sorting each word costs O(k log k) for a word of length k, so the total is O(n · k log k). A key built from letter counts (a tuple of 26 numbers) avoids the sort and makes it O(n · k). Either is acceptable; knowing why the count key is faster is what earns credit.
The same “what makes two things equal for this problem?” question applies everywhere. Case-insensitive grouping wants w.lower() in the key. Grouping points by row wants the y coordinate. Counting subarrays with a given sum wants running totals as keys, which is the idea behind Subarray Sum Equals K and is covered properly in the prefix sums note.
What a hash map actually costs
“O(1) lookup” is an average-case claim. It assumes a hash function that spreads keys evenly. If many keys land in the same bucket, lookups degrade, and in the theoretical worst case a single operation is O(n). Some languages defend against deliberate collisions: Python randomises string hashes per process, and Java’s HashMap turns long collision chains into balanced trees. Saying “expected O(1)” in an interview shows you know the caveat without dwelling on it.
The other cost is memory. A map of n entries is O(n) space, and each entry carries far more overhead than an array slot. If the interviewer says memory is tight, the usual alternatives are sorting first (O(n log n) time, little extra space) or a fixed-size array when keys are small integers.
Interview practice: longest consecutive sequence
Given an unsorted array of integers, return the length of the longest run of consecutive values, in O(n) time. For [100, 4, 200, 1, 3, 2] the answer is 4 (the run 1, 2, 3, 4). Sorting would work but costs O(n log n). How do you hit linear time?
Answer
Put every number in a set so membership checks are O(1). Then only start counting from numbers that begin a run, meaning x - 1 isn’t in the set. From each start, walk upward while x + 1, x + 2, … are present.
def longest_consecutive(nums):
present = set(nums)
best = 0
for x in present:
if x - 1 in present:
continue # not the start of a run
length = 1
while x + length in present:
length += 1
best = max(best, length)
return best
print(longest_consecutive([100, 4, 200, 1, 3, 2]),
longest_consecutive([0, 3, 7, 2, 5, 8, 4, 6, 0, 1]),
longest_consecutive([]))4 9 0The nested while makes it look quadratic, and that’s the reasoning the interviewer wants to hear you work through. Each number is visited by the inner loop at most once overall, because the walk only begins at the start of a run and each run has exactly one start. So the inner loop runs n times in total across the whole outer loop, and the algorithm is O(n) time with O(n) space for the set. Without the x - 1 check, you’d walk the same run from every member of it, and a run of a million numbers would cost about half a trillion steps. Iterating over the set rather than the original list also skips duplicates like the repeated 0. Try it on Longest Consecutive Sequence, then Top K Frequent Elements, which starts with a frequency map.