Hashing Interview Questions

A hash table stores key-value pairs in an array of buckets; the key's hash modulo the array size picks the bucket, so a lookup checks one bucket instead of scanning. That is O(1) on average, degrading toward O(n) when many keys share a bucket, which is why tables resize. See keys being hashed into buckets.

Walk the array once with a map from value to index: if target - number is already in the map you have the pair, otherwise store the number. O(n) time and space.

def two_sum(nums, target):
    seen = {}
    for i, x in enumerate(nums):
        need = target - x
        if need in seen:
            return [seen[need], i]
        seen[x] = i
    return []

print(two_sum([2, 7, 11, 15], 9))
print(two_sum([3, 3], 6))

Check before you insert, or [3] with target 6 pairs the 3 with itself.

A collision is two keys landing in the same bucket, unavoidable because there are more keys than buckets. Separate chaining (Java HashMap) keeps a list per bucket; open addressing (CPython dict) probes other slots and needs tombstones for deletes. Both stay O(1) on average while the load factor is bounded. Since Java 8 (JEP 180), OpenJDK's HashMap turns a bucket past 8 entries into a red-black tree once the table has at least 64 buckets.

1, 1.0 and True are equal and have the same hash, so the dict treats them as one key, and each assignment overwrites the value: one entry, "c". A hash table compares by hash and then ==, so equal objects must have equal hashes. The dict docs use this very example.

Lists are mutable, and a key whose hash changed would sit in a bucket it no longer points to, so Python raises TypeError with that message. Use a tuple: {(1, 2): "x"} works, and coordinate tuples are how grid problems mark visited cells.

Count the characters of both strings and compare the counts: O(n). Sorting both and comparing is O(n log n).

from collections import Counter

def is_anagram(a, b):
    return len(a) == len(b) and Counter(a) == Counter(b)

print(is_anagram("listen", "silent"))
print(is_anagram("rat", "car"))
print(sorted("listen") == sorted("silent"))

Follow-up: group anagrams? Use the sorted string, or a tuple of 26 counts, as a dict key. The Python dictionaries page covers Counter.

Count every character in one pass, then return the first character whose count is 1. O(n) time, and O(1) space for a fixed alphabet.

from collections import Counter

def first_unique(s):
    counts = Counter(s)
    for i, ch in enumerate(s):
        if counts[ch] == 1:
            return i, ch
    return -1, None

print(first_unique("swiss"))
print(first_unique("aabb"))

Answering the first time you see a character fails, because a later copy can make it repeat.

Put the numbers in a set. A number starts a run only if x - 1 is missing; from each start, count up while x + 1 is present. Each number is visited at most twice: O(n).

def longest_consecutive(nums):
    values = set(nums)
    best = 0
    for x in values:
        if x - 1 not in values:      # x starts a run
            length = 1
            while x + length in values:
                length += 1
            best = max(best, length)
    return best

print(longest_consecutive([100, 4, 200, 1, 3, 2]))

Without the x - 1 check, each run is counted from every member: O(n²).

Keep a running prefix sum and a map counting each prefix sum seen. A subarray ending here sums to k when an earlier prefix equals total - k, so add that count. O(n), and unlike a sliding window it handles negatives.

from collections import defaultdict

def subarray_sum(nums, k):
    counts = defaultdict(int)
    counts[0] = 1          # the empty prefix
    total = answer = 0
    for x in nums:
        total += x
        answer += counts[total - k]
        counts[total] += 1
    return answer

print(subarray_sum([1, 1, 1], 2))
print(subarray_sum([3, 4, -7, 3, 1, 3, 1, -4], 7))

Forgetting counts[0] = 1 misses subarrays that start at index 0.

Count with a hash map, then take the top k: a heap of size k gives O(n log k), and bucket sort by count gives O(n), because no count can exceed n.

from collections import Counter
import heapq

def top_k(nums, k):
    counts = Counter(nums)
    return heapq.nlargest(k, counts, key=counts.get)

def top_k_buckets(nums, k):
    counts = Counter(nums)
    buckets = [[] for _ in range(len(nums) + 1)]
    for x, c in counts.items():
        buckets[c].append(x)
    result = []
    for c in range(len(nums), 0, -1):
        result.extend(buckets[c])
        if len(result) >= k:
            return result[:k]
    return result

print(top_k([1, 1, 1, 2, 2, 3], 2))
print(top_k_buckets([1, 1, 1, 2, 2, 3], 2))

Both print [1, 2]. Counter(nums).most_common(k) does it in one call.