Coding

Hash Maps & Sets Coding Questions

Hash maps and sets are the most universally applicable data structures in coding interviews. They convert O(n²) brute-force into O(n) and appear in virtually every coding interview.

Practice with AI Feedback — Free AI Mock Interview

Sample Questions & Strong Answers

Two Sum (hash map approach) — find indices of two numbers adding to target.

Single-pass hash map: for each number x, check if target−x is in map. If yes, return [map[target−x], i]. Else store map[x] = i. Time O(n), Space O(n). This is the gold-standard approach — faster than sorting+two-pointer when indices matter.

💡

Pro tip: Store the complement, not the number. Check before inserting to avoid using same element twice. Google, Amazon, Meta, Microsoft, Apple — universally asked.

Longest Consecutive Sequence — longest run of consecutive integers.

Add all numbers to a set. For each number x, only start counting if x−1 is not in set (x is a sequence start). Count up: x+1, x+2, ... until not in set. Track max length. Time O(n), Space O(n).

💡

Pro tip: The 'start only if x−1 not in set' check prevents redundant sequences and gives O(n) total. Without it, it's O(n²). Amazon, Meta, Google.

Top K Frequent Elements.

Count frequencies with a map. Bucket sort: create array of lists where index = frequency. Elements with frequency f go in bucket[f]. Iterate buckets from high to low, collect until k elements. Time O(n), Space O(n). Alternatively, use a min-heap of size k: O(n log k).

💡

Pro tip: Bucket sort achieves O(n) vs O(n log k) for heap. Bucket max index = n (max possible frequency). Amazon, Meta, Google.

Subarray Sum Equals K — count subarrays with sum equal to k.

Prefix sum + hash map. Store count of each prefix sum seen. For each index, check if (prefixSum − k) is in map — those subarrays end at current index. Time O(n), Space O(n). Never use O(n²) brute force.

💡

Pro tip: Key insight: if prefix[i] − prefix[j] = k, then subarray j+1..i sums to k. Initialize map with {0: 1} to handle subarrays starting at index 0. Amazon, Google, Meta.

First Missing Positive — find smallest positive integer not in array.

Use the array itself as a hash map (index i holds i+1). Cycle-sort: move each number x to index x−1 if 1≤x≤n. Then scan: first index where nums[i]≠i+1 → return i+1. If all correct, return n+1. Time O(n), Space O(1).

💡

Pro tip: O(1) space via index-as-key is the hard part. Simpler O(n) space: use a set, then iterate from 1 upward. Amazon, Google — hard.

Find All Duplicates in Array — integers 1 to n, some appear twice.

Mark-by-negation: for each number x, negate nums[|x|−1]. If already negative, |x| is a duplicate. Time O(n), Space O(1) (excluding output). Restore values by taking absolute value at end.

💡

Pro tip: Modifying the array as a visited marker works when values are in [1,n]. Clean O(1) space trick. Amazon, Google.

Word Pattern — check if pattern matches string word-for-word.

Two maps: pattern char → word and word → pattern char. For each pair (char, word): if either mapping conflicts with existing, return false. Insert both. Check lengths match first. Time O(n), Space O(k).

💡

Pro tip: Bidirectional mapping prevents 'a'→'dog' and 'b'→'dog' both being valid (bijection check). Amazon, Google.

Isomorphic Strings — check if s can be mapped to t character-by-character.

Same as Word Pattern with two maps: s[i]→t[i] and t[i]→s[i]. If any mapping is inconsistent, return false. Time O(n), Space O(1) (bounded by character set).

💡

Pro tip: One map is insufficient — need bijection (both directions). Amazon, Meta, Google.

Happy Number — sum of squares of digits eventually reaches 1 or loops forever.

Use a set to detect cycles: if sum is 1, return true. If sum seen before, return false. Or: use fast/slow pointer on the sequence — if they meet at 1, happy; if at any other number, sad. Time O(log n), Space O(1) with Floyd's.

💡

Pro tip: The Floyd's cycle detection approach eliminates the set entirely. All non-happy numbers eventually cycle through 4→16→37→58→89→145→42→20→4. Amazon, Google, Apple.

Ransom Note — can you build the ransom note from the magazine?

Count character frequencies from magazine (hash map or 26-element array). For each character in ransomNote, decrement its count; if count goes below 0, return false. Time O(m+n), Space O(1).

💡

Pro tip: Array of size 26 beats a hash map for lowercase-only input (smaller constant). Amazon, Google — easy warm-up.

Intersection of Two Arrays II — return all common elements including duplicates.

Count frequencies of smaller array in a map. For each element in larger array: if its count in map > 0, add to result and decrement count. Sort both arrays and use two pointers for O(1) space. Time O(m+n), Space O(min(m,n)).

💡

Pro tip: Clarify: should result be sorted? Is input sorted? If input is sorted, two-pointer O(1) space is optimal. Apple, Amazon, Microsoft.

Longest Palindrome from Characters — given a string, build the longest palindrome.

Count character frequencies. Each even-frequency char contributes its full count. Each odd-frequency char contributes count−1. If any odd-frequency exists, add 1 (for center). Hash set: if char already in set, it forms a pair (remove from set, add 2 to length). Time O(n), Space O(1).

💡

Pro tip: The center position adds 1 if any character has an odd count. Amazon, Google, Meta.

Expert tips

When you need O(1) lookup, your first instinct should be a hash map or set — it's the right tool for most O(n) solutions.

Prefix sum + hash map is a powerful combination for subarray problems (sum, product, length).

For bounded character sets (lowercase letters), a 26-element array beats a hash map in constant factor.

Two-map bidirectional matching (bijection) appears in isomorphism, word pattern, and bijection-check problems.

Hash Maps & Sets Coding Questions FAQ

Use a set when you only need to know if an element exists (O(1) membership test). Use a map when you need to store additional data per key (frequency, index, first occurrence). Sets are maps without values — prefer sets when you don't need the extra data.

Mention that hash maps have O(1) average case but O(n) worst case due to collisions. In practice, good hash functions make this rare. Java's HashMap uses chaining; Python's dict uses open addressing with a smart probing strategy. If an interviewer asks, explain the difference between amortized O(1) and worst-case O(n).

Prefix sum (or cumulative sum) array: prefix[i] = sum of nums[0..i−1]. Range sum query (l, r) = prefix[r+1] − prefix[l] in O(1). Combined with a hash map, this solves: subarrays summing to k, number of subarrays with given sum modulo, and binary prefix XOR problems. Initialize map with {0: 1} to handle subarrays starting at index 0.

For arbitrary keys: use a hash map. For lowercase letters: use array[26] (index 0 = 'a'). For digits: use array[10]. Counter in Python and HashMap in Java handle most cases. For top-K frequency: combine with a min-heap (O(n log k)) or bucket sort (O(n) when max frequency ≤ n).

Practice Hash Maps & Sets Coding Questions with real-time AI.

Stop reading sample answers and start practicing. Get personalized feedback on structure, delivery, and depth — every time.

Start Free Practice AI Mock Interview

Free plan available · No credit card needed · Cancel anytime