Hash map: how to spot it
We'll cover the following
Trade memory for speed. Remember what you have seen so you never have to search for it again. It turns many nested loops into one pass.
How the question sounds
- Find a pair or partner and the array is unsorted
- Count how many times something appears
- Group items by a shared key (anagrams, same first letter)
- Subarray sum equals k: store running sums in the map
- Brute force is two nested loops and you want one pass
The two shapes
Where it shows up in GenAI work
Prompt and embedding caches, deduplicating training or retrieval data, and inverted indexes for keyword search are hash maps. Counting token frequencies is the same pattern.
Is it hash map?
Decide yes or no before you open each answer.
Check yourselfGiven an unsorted array and a target, return the indices of two numbers that add up to it.
Yes. Look up the partner you need in a map of seen values.
Check yourselfGroup a list of words so anagrams end up together.
Yes. Sort each word to make a key and collect words under that key.
Check yourselfFind the first letter in a string that appears only once.
Yes. Count letters first, then scan for a count of 1.
Check yourselfFind the longest substring with no repeating characters.
No. A set helps, but the real structure is a moving range, which is a sliding window.
Check yourselfFind a target in a sorted array in O(log n).
No. Sorted data and log n means binary search.
Check yourselfCheck that brackets in a string are balanced.
No. The most recent opener must close first, which is a stack.
Problems in this pattern
- Two Sum · Easy · Look up a partner
- Subarray sum equals k · Medium · Prefix sums
- Longest consecutive run · Medium · Set lookup
- First unique character · Easy · Counting
Summary: say it in the interview
- Lookup: Store each item as you go. For the next one, ask the map whether the thing you need already exists.
- Counting: Store how many times each key appeared. Use counts for duplicates, frequency and uniqueness questions.