Interview Guide: Hash Tables Problems and Solutions

Understanding Hash Tables in Technical Interviews

A hash table (also known as a hash map, dictionary, or associative array depending on the language) is one of the most fundamental and powerful data structures you'll encounter in technical interviews. At its core, a hash table stores key-value pairs and provides average O(1) time complexity for insertions, deletions, and lookups. This near-constant-time access makes it the go-to solution for a vast array of interview problems, from simple frequency counting to complex caching mechanisms.

Under the hood, a hash table uses a hash function to convert a key into an integer index within an underlying array. When two keys produce the same index (a collision), modern implementations handle this through techniques like chaining (storing a linked list at each bucket) or open addressing (probing for the next available slot). While you rarely need to implement the low-level mechanics from scratch, understanding collisions and resizing helps you reason about edge cases and worst-case performance.

Hash Table Terminology by Language

• Python: dict — built-in dictionary type
• JavaScript: Map (modern) or plain {} objects
• Java: HashMap, Hashtable (legacy, thread-safe)
• C++: std::unordered_map
• C#: Dictionary
• Go: map built-in type
• Ruby: Hash

Why Hash Tables Matter in Interviews

Interviewers love hash table problems for several reasons. First, they test your ability to recognize when O(1) lookup can transform a brute-force O(n²) solution into an elegant O(n) one. Second, hash table problems often have multiple valid approaches, letting the interviewer probe your understanding of time-space tradeoffs. Third, they appear across every difficulty level — from warm-up questions to complex system design follow-ups involving caching and indexing.

According to data from LeetCode and interviewing.io, hash table problems consistently rank among the top five most frequently asked categories at companies like Google, Meta, Amazon, and Microsoft. Mastering hash table patterns can single-handedly unlock solutions for roughly 15-20% of all coding interview problems.

When to Reach for a Hash Table

Consider a hash table whenever you encounter these problem signals:

• You need to count frequencies of elements (characters, numbers, words)
• You need to detect duplicates or find unique elements
• You need to map relationships between two sets of data
• You need constant-time lookups to avoid nested loops
• You're building a cache with fast eviction policies
• You need to store previously seen values while iterating (memoization)

Core Operations and Time Complexity

Before diving into problems, internalize these complexity characteristics. The numbers in parentheses represent worst-case scenarios when many keys collide (degenerating into a linked list traversal).

Key insight for interviews: Always mention the worst-case O(n) possibility and explain that with a good hash function and load factor management, real-world implementations achieve O(1) amortized. This demonstrates depth without overcomplicating your answer.

Common Interview Problems and Solutions

Below are detailed walkthroughs of the most frequently asked hash table problems. Each includes the problem statement, the intuition behind the hash-based approach, and a complete, runnable code solution.

Problem 1: Two Sum

Difficulty: Easy | Companies: Google, Amazon, Meta, Apple, Microsoft

Problem: Given an array of integers nums and an integer target, return the indices of the two numbers that add up to target. You may assume exactly one solution exists and you may not use the same element twice.

Hash Table Approach: Instead of checking every pair (O(n²)), maintain a map of seen values to their indices. For each element, compute its complement (target - current_value) and check if that complement already exists in the map. If so, return both indices immediately. This achieves O(n) time and O(n) space.

def two_sum(nums, target):
    """
    Returns indices of the two numbers that sum to target.
    Time: O(n), Space: O(n)
    """
    seen = {}  # value -> index
    
    for i, num in enumerate(nums):
        complement = target - num
        
        if complement in seen:
            return [seen[complement], i]
        
        seen[num] = i
    
    return []  # No solution found (shouldn't happen per problem constraints)


# Example usage
nums = [2, 7, 11, 15]
target = 9
result = two_sum(nums, target)
print(f"Indices: {result}")  # Output: [0, 1] because nums[0]+nums[1] = 2+7 = 9
print(f"Values: {nums[result[0]]} + {nums[result[1]]} = {target}")

Interview Follow-up: What if the array is sorted? Then you could use two pointers (O(n) time, O(1) space), but the hash approach works regardless of sort order. Always discuss the tradeoff: hash tables give you O(n) time at the cost of O(n) space, while two pointers give O(n log n) time (due to sorting) but O(1) space.

Problem 2: First Non-Repeating Character

Difficulty: Easy | Companies: Bloomberg, Goldman Sachs, Amazon

Problem: Given a string s, find the first character that appears exactly once and return its index. If no such character exists, return -1.

Hash Table Approach: Use a two-pass solution. First pass: count frequencies of each character using a dictionary. Second pass: iterate through the original string and return the index of the first character whose frequency count is 1. This is O(n) time and O(k) space where k is the size of the character set.

def first_unique_char(s):
    """
    Returns the index of the first non-repeating character.
    Time: O(n), Space: O(1) since alphabet is bounded (26 or 256)
    """
    # First pass: count frequencies
    freq = {}
    for char in s:
        freq[char] = freq.get(char, 0) + 1
    
    # Second pass: find the first character with count == 1
    for i, char in enumerate(s):
        if freq[char] == 1:
            return i
    
    return -1


# Example usage
print(first_unique_char("loveleetcode"))  # Output: 2  ('v' is first unique)
print(first_unique_char("aabb"))          # Output: -1 (no unique characters)
print(first_unique_char("stream"))        # Output: 0  ('s' is first unique)

Why two passes? You cannot determine uniqueness in a single pass because a character that appears unique early on might repeat later in the string. The frequency map gives you global knowledge before making decisions.

Problem 3: Group Anagrams

Difficulty: Medium | Companies: Amazon, Google, Uber, Square

Problem: Given an array of strings, group the anagrams together. Anagrams are words formed by rearranging the same letters (e.g., "eat", "tea", "ate"). Return the groups as a list of lists.

Hash Table Approach: The key insight is that anagrams produce identical sorted strings or identical character count signatures. Use a sorted version of each word (or a character frequency tuple) as the dictionary key. Collect all original words under that key. Time complexity is O(n * k log k) for the sorting approach, where n is the number of strings and k is the average string length.

def group_anagrams(strs):
    """
    Groups anagrams together using sorted strings as keys.
    Time: O(n * k log k) where k is max string length
    Space: O(n * k) to store all strings
    """
    groups = {}  # sorted_key -> list of original words
    
    for word in strs:
        # Create a canonical key by sorting characters
        key = ''.join(sorted(word))
        
        if key not in groups:
            groups[key] = []
        groups[key].append(word)
    
    return list(groups.values())


# Alternative: character count tuple as key (O(n*k) time, avoids sorting)
def group_anagrams_fast(strs):
    """
    Uses character frequency tuples as keys for O(n*k) time.
    Works best when strings are long and the alphabet is small.
    """
    groups = {}
    
    for word in strs:
        # Build a frequency count (26 slots for lowercase English)
        count = [0] * 26
        for char in word:
            count[ord(char) - ord('a')] += 1
        
        # Tuples of integers are hashable in Python
        key = tuple(count)
        
        if key not in groups:
            groups[key] = []
        groups[key].append(word)
    
    return list(groups.values())


# Example usage
words = ["eat", "tea", "tan", "ate", "nat", "bat"]
print(group_anagrams(words))
# Output (order may vary): [["eat","tea","ate"], ["tan","nat"], ["bat"]]
print(group_anagrams_fast(words))

Interview Tip: Always mention both approaches. The sorted-key version is simpler to code under pressure, but acknowledging the character-count optimization shows deeper algorithmic thinking. If the interviewer asks about Unicode or large alphabets, discuss how the counting approach scales.

Problem 4: Contains Duplicate & Contains Duplicate II

Difficulty: Easy / Medium | Companies: Amazon, Bloomberg, Airbnb

Problem: Contains Duplicate: Return true if any value appears at least twice in the array. Contains Duplicate II: Return true if there are two distinct indices i and j such that nums[i] == nums[j] and the absolute difference between i and j is at most k.

Hash Table Approach: For the basic version, add elements to a set and check for membership in O(1) per element. For the k-distance variant, maintain a map from value to its most recent index. When you encounter a value already in the map, check if the distance constraint is satisfied.

def contains_duplicate(nums):
    """
    Returns True if any value appears at least twice.
    Time: O(n), Space: O(n)
    """
    seen = set()
    for num in nums:
        if num in seen:
            return True
        seen.add(num)
    return False


def contains_nearby_duplicate(nums, k):
    """
    Returns True if duplicates exist within distance k.
    Time: O(n), Space: O(n)
    """
    last_seen = {}  # value -> most recent index
    
    for i, num in enumerate(nums):
        if num in last_seen:
            if i - last_seen[num] <= k:
                return True
        # Update the most recent index for this value
        last_seen[num] = i
    
    return False


# Example usage
print(contains_duplicate([1, 2, 3, 1]))          # True
print(contains_duplicate([1, 2, 3, 4]))          # False
print(contains_nearby_duplicate([1, 2, 3, 1], 3))  # True (indices 0 and 3, diff=3)
print(contains_nearby_duplicate([1, 2, 3, 1], 2))  # False (diff=3 exceeds k=2)

Space optimization: For the k-distance variant, you can also use a sliding window with a set of size k, evicting old elements as the window moves. Mention this if the interviewer pushes for O(k) space instead of O(n).

Problem 5: Intersection of Two Arrays

Difficulty: Easy | Companies: Facebook, LinkedIn, Two Sigma

Problem: Given two arrays, return their intersection as an array. Each element in the result should appear as many times as it appears in both arrays (i.e., the minimum count in each).

Hash Table Approach: Build a frequency map for the smaller array to save space, then iterate through the larger array and collect matches while decrementing the count to handle multiplicity correctly.

from collections import Counter

def intersect(nums1, nums2):
    """
    Returns intersection with multiplicity.
    Time: O(n + m), Space: O(min(n, m))
    """
    # Ensure nums1 is the smaller array for space efficiency
    if len(nums1) > len(nums2):
        nums1, nums2 = nums2, nums1
    
    # Build frequency map for the smaller array
    counts = Counter(nums1)
    
    result = []
    for num in nums2:
        if counts.get(num, 0) > 0:
            result.append(num)
            counts[num] -= 1
    
    return result


# Example usage
print(intersect([1, 2, 2, 1], [2, 2]))       # Output: [2, 2]
print(intersect([4, 9, 5], [9, 4, 9, 8, 4])) # Output: [4, 9] (order may vary)

Follow-up questions: What if the arrays are already sorted? Then you can use two pointers with O(1) extra space. What if one array is much larger than the other and cannot fit in memory? Discuss external sorting or map-reduce approaches. These follow-ups test your ability to adapt solutions to real-world constraints.

Problem 6: Valid Anagram

Difficulty: Easy | Companies: Google, Microsoft, Spotify

Problem: Given two strings s and t, return true if t is an anagram of s (both strings contain the same characters with the same frequencies).

Hash Table Approach: Count characters in s, then decrement counts while iterating through t. If any count goes negative or if the final counts aren't all zero, they're not anagrams. This handles Unicode characters naturally.

def is_anagram(s, t):
    """
    Returns True if t is an anagram of s.
    Time: O(n), Space: O(k) where k is size of character set
    """
    if len(s) != len(t):
        return False
    
    counts = {}
    
    # Increment for characters in s
    for char in s:
        counts[char] = counts.get(char, 0) + 1
    
    # Decrement for characters in t
    for char in t:
        if char not in counts:
            return False  # Character not in s at all
        counts[char] -= 1
        if counts[char] < 0:
            return False  # More occurrences in t than in s
    
    # All counts should be zero
    return all(v == 0 for v in counts.values())


# Alternative using Counter (concise but same logic)
from collections import Counter

def is_anagram_counter(s, t):
    return Counter(s) == Counter(t)


# Example usage
print(is_anagram("anagram", "nagaram"))  # True
print(is_anagram("rat", "car"))          # False
print(is_anagram("aacc", "ccac"))        # False (different frequencies)

Problem 7: Subarray Sum Equals K

Difficulty: Medium | Companies: Google, Amazon, Facebook, Bloomberg

Problem: Given an array of integers nums and an integer k, return the total number of continuous subarrays whose sum equals k.

Hash Table Approach: This is a classic prefix-sum problem. Maintain a running sum and a map that stores how many times each prefix sum has occurred. At each step, check if current_sum - k exists in the map — each occurrence represents a subarray ending at the current index that sums to k. This achieves O(n) time, a dramatic improvement over the O(n²) brute-force approach.

def subarray_sum(nums, k):
    """
    Returns the count of contiguous subarrays that sum to k.
    Time: O(n), Space: O(n)
    """
    prefix_counts = {0: 1}  # prefix_sum -> frequency (0 appears once for empty subarray)
    current_sum = 0
    total_count = 0
    
    for num in nums:
        current_sum += num
        
        # We want: current_sum - prefix_sum = k  =>  prefix_sum = current_sum - k
        complement = current_sum - k
        
        if complement in prefix_counts:
            total_count += prefix_counts[complement]
        
        # Update the frequency of the current prefix sum
        prefix_counts[current_sum] = prefix_counts.get(current_sum, 0) + 1
    
    return total_count


# Example usage
print(subarray_sum([1, 1, 1], 2))       # Output: 2 (subarrays [1,1] at indices 0-1 and 1-2)
print(subarray_sum([1, 2, 3], 3))       # Output: 2 ([1,2] and [3])
print(subarray_sum([-1, -1, 1], 0))     # Output: 1 (subarray [-1, 1] sums to 0)
print(subarray_sum([1, -1, 0], 0))      # Output: 3 ([1,-1], [0], [1,-1,0])

Critical detail: Initializing the map with {0: 1} handles the case where a subarray starting from index 0 sums exactly to k. Forgetting this initialization is one of the most common mistakes interviewers see — explicitly mentioning it shows careful attention to edge cases.

Problem 8: Longest Consecutive Sequence

Difficulty: Medium | Companies: Google, Amazon, Microsoft, LinkedIn

Problem: Given an unsorted array of integers, return the length of the longest consecutive elements sequence. The algorithm must run in O(n) time.

Hash Table Approach: Insert all numbers into a set. Then, for each number that could be the start of a sequence (i.e., num - 1 is not in the set), count upward checking for consecutive numbers. Each element is visited at most twice, giving O(n) total time.

def longest_consecutive(nums):
    """
    Returns the length of the longest consecutive sequence.
    Time: O(n), Space: O(n)
    """
    if not nums:
        return 0
    
    num_set = set(nums)
    longest = 0
    
    for num in num_set:
        # Only start counting if 'num' is the beginning of a sequence
        if num - 1 not in num_set:
            current_num = num
            current_streak = 1
            
            while current_num + 1 in num_set:
                current_num += 1
                current_streak += 1
            
            longest = max(longest, current_streak)
    
    return longest


# Example usage
print(longest_consecutive([100, 4, 200, 1, 3, 2]))  # Output: 4 (sequence: 1,2,3,4)
print(longest_consecutive([0, 3, 7, 2, 5, 8, 4, 6, 0, 1]))  # Output: 9 (0 through 8)
print(longest_consecutive([9, 1, -3, 2, -2, -1, 3, -4]))  # Output: 8 (-4 through 3)

Why check num - 1 not in num_set? This guarantees each sequence is counted exactly once from its smallest element. Without this optimization, the inner while loop could cause O(n²) behavior in the worst case.

Problem 9: LRU Cache (Advanced)

Difficulty: Medium/Hard | Companies: Amazon, Google, Meta, Microsoft, Twitter

Problem: Design a data structure for a Least Recently Used (LRU) cache with get(key) and put(key, value) operations, both in O(1) time. When the cache reaches capacity, evict the least recently used item.

Hash Table Approach: Combine a hash map (for O(1) lookups) with a doubly linked list (for O(1) eviction and reordering). The map stores keys pointing to linked list nodes. Each node holds the key and value. On access, move the node to the head (most recently used). On eviction, remove the tail node (least recently used). This is arguably the most important advanced hash table problem — it tests your ability to compose data structures.

class ListNode:
    """Doubly linked list node for LRU cache."""
    def __init__(self, key=None, value=None):
        self.key = key
        self.value = value
        self.prev = None
        self.next = None


class LRUCache:
    """
    Least Recently Used cache with O(1) get and put operations.
    Combines a hash map with a doubly linked list.
    """
    
    def __init__(self, capacity: int):
        self.capacity = capacity
        self.cache = {}  # key -> ListNode
        
        # Dummy head and tail nodes simplify edge cases
        self.head = ListNode()  # Most recently used end
        self.tail = ListNode()  # Least recently used end
        self.head.next = self.tail
        self.tail.prev = self.head
    
    def _remove_node(self, node):
        """Remove a node from the linked list."""
        node.prev.next = node.next
        node.next.prev = node.prev
    
    def _add_to_head(self, node):
        """Insert node at the head (most recently used position)."""
        node.prev = self.head
        node.next = self.head.next
        self.head.next.prev = node
        self.head.next = node
    
    def _move_to_head(self, node):
        """Move an existing node to the head (mark as recently used)."""
        self._remove_node(node)
        self._add_to_head(node)
    
    def get(self, key: int) -> int:
        """Retrieve value by key. Returns -1 if key doesn't exist."""
        if key not in self.cache:
            return -1
        
        node = self.cache[key]
        self._move_to_head(node)  # Mark as recently used
        return node.value
    
    def put(self, key: int, value: int):
        """Insert or update a key-value pair. Evicts LRU if at capacity."""
        if key in self.cache:
            # Update existing key
            node = self.cache[key]
            node.value = value
            self._move_to_head(node)
        else:
            # Create new node
            new_node = ListNode(key, value)
            self.cache[key] = new_node
            self._add_to_head(new_node)
            
            if len(self.cache) > self.capacity:
                # Evict the least recently used (node before tail)
                lru_node = self.tail.prev
                del self.cache[lru_node.key]
                self._remove_node(lru_node)


# Example usage
cache = LRUCache(2)
cache.put(1, 1)          # Cache: {1=1}
cache.put(2, 2)          # Cache: {1=1, 2=2}
print(cache.get(1))      # Returns 1, Cache: {2=2, 1=1} (1 is now MRU)
cache.put(3, 3)          # Evicts key 2 (LRU), Cache: {1=1, 3=3}
print(cache.get(2))      # Returns -1 (evicted)
cache.put(4, 4)          # Evicts key 1, Cache: {3=3, 4=4}
print(cache.get(1))      # Returns -1
print(cache.get(3))      # Returns 3
print(cache.get(4))      # Returns 4

Interview tip for LRU Cache: Walk through the design step by step. Start by saying "we need O(1) lookup so we use a hash map, and O(1) eviction so we need a linked list." Draw the combined data structure on the whiteboard. The dummy head/tail pattern eliminates null-checking edge cases — mentioning this explicitly signals maturity with linked list implementations.

Problem 10: Find All Duplicates in an Array

Difficulty: Medium | Companies: Amazon, Google, Apple

Problem: Given an array of integers where 1 ≤ nums[i] ≤ n and n is the length of the array, some elements appear twice and others appear once. Find all elements that appear twice in O(n) time and O(1) extra space (excluding the output).

Hash Table Approach (with in-place trick): While a standard hash set solves this in O(n) time and O(n) space, the follow-up constraint of O(1) space requires exploiting the problem's bounds. Treat the array itself as a hash table by using index mapping: for each value, negate the element at its corresponding index. If you encounter an already-negated value, you've found a duplicate.

def find_duplicates(nums):
    """
    Returns all elements that appear twice.
    Uses in-place negation marking for O(1) extra space.
    Time: O(n), Space: O(1) excluding output
    """
    duplicates = []
    
    for num in nums:
        index = abs(num) - 1  # Map value to 0-based index
        
        if nums[index] < 0:
            # Already marked negative — this is a duplicate
            duplicates.append(abs(num))
        else:
            # Mark as seen by negating
            nums[index] = -nums[index]
    
    return duplicates


# Example usage
print(find_duplicates([4, 3, 2, 7, 8, 2, 3, 1]))  # Output: [2, 3]
print(find_duplicates([1, 1, 2]))                   # Output: [1]
print(find_duplicates([1]))                         # Output: []

Why this works: The constraint 1 ≤ nums[i] ≤ n means every value maps perfectly to an index (value - 1). By negating the value at that index, we create a presence flag without extra memory. This pattern appears in many "find duplicates in constrained range" problems and is worth recognizing instantly.

Best Practices and Interview Tips

1. Start with the Brute Force, Then Optimize

Even when you immediately see the hash table solution, briefly mention the brute-force approach and its complexity. This demonstrates structured thinking and gives you a fallback if you blank on the optimal solution. For Two Sum, say: "The naive approach checks every pair in O(n²). We can improve this to O(n) by using a hash map to store seen values."

2. Verbalize the Space-Time Tradeoff

Hash table solutions almost always trade space for time. Explicitly state: "We're using O(n) additional space to achieve O(n) time complexity, whereas the brute-force approach uses O(1) extra space but O(n²) time." Interviewers want to hear that you understand this tradeoff consciously.

3. Choose Appropriate Key Types

Not everything can be a dictionary key. In Python, only hashable (immutable) types work: strings, integers, tuples of immutables. Lists and dictionaries cannot be keys. In Java, override hashCode() and equals() consistently for custom objects. In JavaScript, Map allows any type as key while plain objects coerce keys to strings.

4. Handle Default Values Gracefully

Every language offers idioms for default values when a key doesn't exist. Learn them — they prevent verbose if-else chains and show fluency.

# Python: dict.get() with default
count = freq.get(char, 0) + 1

# Python: collections.defaultdict
from collections import defaultdict
groups = defaultdict(list)
groups[key].append(word)

# Python: collections.Counter for frequency counting
from collections import Counter
counts = Counter(nums)

# JavaScript: Map with || operator
const count = (map.get(char) || 0) + 1;

# Java: getOrDefault
map.put(num, map.getOrDefault(num, 0) + 1);

# C++: operator[] inserts default if missing
map[char]++;

5. Watch Out for Collision Worst Cases

Acknowledge that hash collisions can degrade operations to O(n). In Python and Java, modern implementations use randomized hash seeds to prevent adversarial collision attacks, but mentioning this shows depth. If asked "what's the worst case?", explain that if all keys hash to the same bucket, the table degenerates into a linked list.

6. Consider Using a Set When Values Don't Matter

If you only need to track presence (not counts or mappings), use a Set rather than a Map with dummy values. This communicates intent clearly and is slightly more memory-efficient.

# Use a set for presence-only checks
seen = set()
for num in nums:
    if num in seen:
        return True
    seen.add(num)

# Rather than a map with dummy booleans
seen = {}
for num in nums:
    if num in seen:
        return True
    seen[num] = True

7. Iterate Safely — Avoid Modifying During Iteration

Modifying a hash table while iterating over it can cause unexpected behavior in most languages. If you need to remove entries based on a condition, collect keys to remove in a separate list first, or use iterators that support safe removal.

# Python: collect keys to delete separately
keys_to_remove = [k for k, v in cache.items() if expired(v)]
for key in keys_to_remove:
    del cache[key]

# Python: use dict comprehension for a new dict
cache = {k: v for k, v in cache.items() if not expired(v)}

# Java: use Iterator.remove()
Iterator> it = map.entrySet().iterator();
while (it.hasNext()) {
    Map.Entry entry = it.next();
    if (expired(entry.getValue())) {
        it.remove();  // Safe removal during iteration
    }
}

8. Test Edge Cases Thoroughly

Before declaring your solution complete, mentally test these scenarios:

• Empty input: Empty array, empty string, null (if applicable)
• Single element: Does your algorithm handle arrays/strings of length 1?
<