Hashing and Maps — Complete Guide for FAANG Interviews (Problems 161-205)

Problem Statement#

Hash tables convert nested-loop O(n^2) brute force into linear O(n) lookups. This guide indexes 45 hashmap and hashset problems used at Google, Amazon, Meta, Microsoft, and Apple, organized by recurring patterns.

Coverage:

• 45 LeetCode problems numbered 161-205
• 8 reusable hashmap interview patterns
• Python and JavaScript reference templates
• Direct links to per-problem walkthroughs

Pattern:    Complement Map -> Two Sum, 4Sum II
Pattern:    Frequency Map  -> Group Anagrams, Top K Frequent
Pattern:    Prefix + Map   -> Subarray Sum Equals K

Pattern:    Two-Way Map    -> Isomorphic Strings, Word Pattern
Pattern:    Cycle HashSet  -> Happy Number
Pattern:    LRU/LFU        -> HashMap + Doubly Linked List

Why This Problem Matters#

Hash tables are the highest-leverage data structure in FAANG coding interviews. Roughly one in three medium-tier hashmap interview questions reduces to a complement-lookup, frequency-count, or prefix-sum-hash pattern, and recruiters explicitly tag them as "must-pass" rounds at Google, Amazon, and Meta phone screens. Understanding when to reach for a HashMap, HashSet, or OrderedDict separates strong candidates from those who default to nested loops.

The hash table FAANG curriculum centers on O(1) lookup as a primitive. Two Sum trains complement lookup. Subarray Sum Equals K trains prefix-sum hashing. LRU Cache trains hash plus doubly linked list. Once you internalize these primitives, the medium and hard variants compose them with sliding windows, bitmasks, or BST traversal.

This guide is the navigation hub for the hashing-maps section. Each entry links to a stand-alone walkthrough with constraints, dry runs, optimal code in Python and JavaScript, and FAANG-specific follow-up discussion.

The Core Insight#

A hash map gives O(1) average-case insert and lookup by mapping keys to bucket indices. Three insights make hash maps a coding-interview superpower:

1. Lookup replaces search. Storing seen values lets you query "have I seen the complement?" in O(1) instead of scanning O(n).
2. Keys can be derived. Sorted strings, frequency tuples, prefix sums, and bitmasks all work as keys, encoding richer state than raw values.
3. Pairs as values. Mapping a key to an index, a node, or a list of positions unlocks group-by, sliding-window, and cache-eviction patterns.

Visual Dry Run#

Solution (Optimal)#

from collections import Counter, defaultdict, OrderedDict
 
def two_sum(nums, target):
    seen = {}
    for i, x in enumerate(nums):
        if target - x in seen:
            return [seen[target - x], i]
        seen[x] = i
 
def subarray_sum_k(nums, k):
    prefix_count = defaultdict(int)
    prefix_count[0] = 1
    total = prefix = 0
    for n in nums:
        prefix += n
        total += prefix_count[prefix - k]
        prefix_count[prefix] += 1
    return total
 
class LRUCache:
    def __init__(self, capacity):
        self.cap = capacity
        self.cache = OrderedDict()
    def get(self, key):
        if key not in self.cache:
            return -1
        self.cache.move_to_end(key)
        return self.cache[key]
    def put(self, key, value):
        if key in self.cache:
            self.cache.move_to_end(key)
        self.cache[key] = value
        if len(self.cache) > self.cap:
            self.cache.popitem(last=False)

function twoSum(nums, target) {
    const seen = new Map();
    for (let i = 0; i < nums.length; i++) {
        const need = target - nums[i];
        if (seen.has(need)) return [seen.get(need), i];
        seen.set(nums[i], i);
    }
}
 
function subarraySum(nums, k) {
    const prefixCount = new Map([[0, 1]]);
    let total = 0, prefix = 0;
    for (const n of nums) {
        prefix += n;
        total += prefixCount.get(prefix - k) || 0;
        prefixCount.set(prefix, (prefixCount.get(prefix) || 0) + 1);
    }
    return total;
}

Time: O(n) average per problem because each hash op is amortized O(1). Space: O(n) typical because hash maps store up to n distinct keys.

Problem Index#

Easy (161 to 170)#

Medium (171 to 200)#

Common Mistakes#

• Using a HashSet when an index or count is required. Sets answer presence, not identity.
• Mutating list or dict keys after insertion, which corrupts hash buckets in Python and JavaScript.
• Forgetting that prefix-sum maps must seed with {0: 1} before iteration.
• Using object as a Map in JavaScript when keys can be objects or large integers; prefer Map.
• Assuming worst-case O(1). Adversarial inputs can degrade to O(n) per op without randomized hashing.

Interview Tips#

• State the brute-force first, then articulate which lookup turns it linear.
• Name the pattern out loud (complement, frequency, prefix). Interviewers grade pattern recognition.
• Reach for defaultdict(int), Counter, and OrderedDict in Python; Map and Set in JavaScript.
• Discuss collisions and hash quality only when asked. Volunteering it can derail a round.

Follow-up Questions#

• How would you make the solution thread-safe? (Hint: per-bucket locks or ConcurrentHashMap.)
• What if keys are mutable objects? (Hint: hash by identity or freeze before insertion.)
• How would you bound memory? (Hint: LRU eviction, count-min sketch, or Bloom filter.)
• How would you scale beyond a single machine? (Hint: consistent hashing, sharded maps.)
• When does sorting beat hashing in practice? (Hint: small n, contiguous keys, cache locality.)

Key Takeaways#

• Hash tables provide O(1) average insert and lookup, the core primitive of fast interview solutions.
• Eight patterns cover most FAANG hashmap interview questions: complement, frequency, prefix-sum, two-way, cycle, index, LRU, LFU.
• Pre-seed prefix-sum maps with {0: 1} to count subarrays starting from index zero.
• Use sorted-string or frequency-tuple keys to group equivalence classes in O(n*k).
• LRU Cache is HashMap plus doubly linked list; LFU Cache is HashMap plus frequency buckets.
• Hash table worst-case is O(n) per op; randomized hashing makes adversarial inputs unlikely in practice.
• Frequency-array of size 26 beats HashMap constant factors for lowercase ASCII string problems.