Hashing interview questions with worked solutions
Last updated 2026-11-19
Hashing turns a search that would cost O(n) into an expected O(1) lookup. In interviews it is the first tool to reach for when a brute force solution compares every pair, or when you need to count, group or deduplicate items. The trade is memory: you pay O(n) space for the speed.
These ten problems move from membership checks to designing the data structure itself. Many are building blocks for other topics: the prefix-sum trick in prefix sum questions is hashing again, and the top k elements questions start from a frequency map. The DSA coding round guide shows where these fit in a test.
| Problems | 10, easy to hard |
|---|---|
| Languages | Python and Java |
| Key tools | HashMap, HashSet, frequency count, meet in the middle |
How to recognise a hashing problem
Look for "have we seen this before", "count occurrences", "group by", "first duplicate" or a pair that must satisfy an equation. If one half of the equation can be computed from the current element, store the other half in a map as you go.
- Store value to index for pair problems.
- Store a canonical key such as sorted letters for grouping.
- Use a set when you only need membership.
- Store a running quantity (a prefix sum) when the question is about subarrays.
Pitfalls
Hash collisions are rare in practice but real: Java HashMap converts long chains to trees, so worst-case lookup is O(log n), while an adversarial input to a naive hash table can cost O(n). Mutable keys, such as lists in Python, cannot be dictionary keys; convert to a tuple first.
Hashing interview questions with worked solutions: questions with worked answers
1 Two Sum: return the indices of two numbers that add up to a target.
easyWalk the array once. For each x, check whether target - x is already in the map; if so, return its index and the current one. Otherwise store x with its index. Checking before inserting stops an element pairing with itself. Time O(n), space O(n).. Edge cases: no pair (return an empty result), duplicates such as [3,3] with target 6, negative numbers.
pythondef two_sum(a, target): seen = {} for i, x in enumerate(a): if target - x in seen: return [seen[target - x], i] seen[x] = i return []javaimport java.util.*; class Solution { static int[] twoSum(int[] a, int target) { Map<Integer, Integer> seen = new HashMap<>(); for (int i = 0; i < a.length; i++) { Integer j = seen.get(target - a[i]); if (j != null) return new int[]{j, i}; seen.put(a[i], i); } return new int[0]; } }2 Does an array contain a duplicate?
easyAdd each element to a set; if it is already present, return true. The Python one-liner compares len(set(a)) with len(a). If memory is tight and mutation is allowed, sorting first gives O(n log n) time and O(1) extra space. Time O(n), space O(n).. Edge cases: empty array (false), one element, large arrays where early exit helps.
pythondef contains_duplicate(a): seen = set() for x in a: if x in seen: return True seen.add(x) return Falsejavaimport java.util.*; class Solution { static boolean containsDuplicate(int[] a) { Set<Integer> seen = new HashSet<>(); for (int x : a) if (!seen.add(x)) return true; return false; } }3 Ransom note: can the note be built from the letters of a magazine?
easyCount the magazine letters, then spend one for every note letter. If a count would go below zero, the note cannot be made. It is the same idea as an anagram check but one-directional. Time O(n + m), space O(k).. Edge cases: empty note (true), note longer than magazine, repeated letters.
pythonfrom collections import Counter def can_construct(note, magazine): c = Counter(magazine) for ch in note: if c[ch] <= 0: return False c[ch] -= 1 return Truejavaimport java.util.*; class Solution { static boolean canConstruct(String note, String magazine) { int[] c = new int[128]; for (char ch : magazine.toCharArray()) c[ch]++; for (char ch : note.toCharArray()) if (--c[ch] < 0) return false; return true; } }4 Intersection of two arrays, where each shared value appears as often as in both arrays.
mediumBuild a frequency map of the first array, then walk the second and emit an element whenever its remaining count is positive, decrementing it. This respects multiplicities, unlike a plain set intersection. Time O(n + m), space O(min(n, m)) if you map the shorter array.. Edge cases: no common values, one array empty, many duplicates.
pythonfrom collections import Counter def intersect(a, b): c = Counter(a) out = [] for x in b: if c[x] > 0: out.append(x) c[x] -= 1 return outjavaimport java.util.*; class Solution { static int[] intersect(int[] a, int[] b) { Map<Integer, Integer> c = new HashMap<>(); for (int x : a) c.merge(x, 1, Integer::sum); List<Integer> out = new ArrayList<>(); for (int x : b) { if (c.getOrDefault(x, 0) > 0) { out.add(x); c.merge(x, -1, Integer::sum); } } return out.stream().mapToInt(Integer::intValue).toArray(); } }5 Isomorphic strings: can characters of s be replaced to get t, with a one-to-one mapping?
mediumKeep two maps, s to t and t to s. For each pair of characters, the stored mapping must agree in both directions. One map alone fails on "ab" and "aa", because both letters would map to a. Time O(n), space O(k).. Edge cases: different lengths, same characters repeated, mapping that is consistent one way only.
pythondef is_isomorphic(s, t): if len(s) != len(t): return False m1, m2 = {}, {} for a, b in zip(s, t): if m1.setdefault(a, b) != b or m2.setdefault(b, a) != a: return False return Truejavaimport java.util.*; class Solution { static boolean isIsomorphic(String s, String t) { if (s.length() != t.length()) return false; Map<Character, Character> m1 = new HashMap<>(), m2 = new HashMap<>(); for (int i = 0; i < s.length(); i++) { char a = s.charAt(i), b = t.charAt(i); Character x = m1.get(a), y = m2.get(b); if ((x != null && x != b) || (y != null && y != a)) return false; m1.put(a, b); m2.put(b, a); } return true; } }6 Group anagrams together.
mediumAnagrams share a canonical form, so use the sorted letters as the map key and append each word to its bucket. For long words and a lowercase alphabet, a 26-count tuple as the key avoids the sort and gives O(n*k). Time O(n * k log k) for n words of length k, space O(n * k).. Edge cases: empty strings group together, single-word input, words that differ only in case if case matters.
pythonfrom collections import defaultdict def group_anagrams(words): d = defaultdict(list) for w in words: d["".join(sorted(w))].append(w) return list(d.values())javaimport java.util.*; class Solution { static List<List<String>> groupAnagrams(String[] words) { Map<String, List<String>> d = new HashMap<>(); for (String w : words) { char[] ca = w.toCharArray(); Arrays.sort(ca); d.computeIfAbsent(new String(ca), k -> new ArrayList<>()).add(w); } return new ArrayList<>(d.values()); } }7 Longest consecutive sequence in an unsorted array, in O(n).
mediumPut all numbers in a set. Only start counting from a number x where x - 1 is not in the set, since that is the start of a run, then walk x+1, x+2 while present. Each number is visited at most twice overall, so the nested loop is still linear. Time O(n), space O(n).. Edge cases: empty array (0), duplicates, negative numbers, one long run.
pythondef longest_consecutive(a): s = set(a) best = 0 for x in s: if x - 1 not in s: y = x while y + 1 in s: y += 1 best = max(best, y - x + 1) return bestjavaimport java.util.*; class Solution { static int longestConsecutive(int[] a) { Set<Integer> s = new HashSet<>(); for (int x : a) s.add(x); int best = 0; for (int x : s) { if (!s.contains(x - 1)) { int y = x; while (s.contains(y + 1)) y++; best = Math.max(best, y - x + 1); } } return best; } }8 4Sum II: count tuples (i, j, k, l) with A[i] + B[j] + C[k] + D[l] = 0.
hardMeet in the middle. Store every sum A[i] + B[j] with its count, then for every pair from C and D add the count of the negated sum. This turns O(n^4) into O(n^2). Time O(n^2), space O(n^2).. Edge cases: empty arrays, many repeated sums (count can be large, use long if sizes are big), no valid tuple.
pythonfrom collections import Counter def four_sum_count(A, B, C, D): ab = Counter(a + b for a in A for b in B) return sum(ab[-(c + d)] for c in C for d in D)javaimport java.util.*; class Solution { static int fourSumCount(int[] A, int[] B, int[] C, int[] D) { Map<Integer, Integer> ab = new HashMap<>(); for (int a : A) for (int b : B) ab.merge(a + b, 1, Integer::sum); int count = 0; for (int c : C) for (int d : D) count += ab.getOrDefault(-(c + d), 0); return count; } }9 Design a HashMap from scratch (put, get, remove) with separate chaining.
hardUse a fixed array of buckets, here 1009 (a prime to spread keys). The bucket index is key % size. Each bucket holds a small list of key-value pairs; put replaces an existing key or appends, get scans the bucket, remove deletes from it. Real implementations also resize when the load factor passes about 0.75. Time average O(1) per operation, worst case O(n) in one bucket; space O(n).. Edge cases: overwriting an existing key, removing a missing key, key 0.
pythonclass MyHashMap: def __init__(self): self.size = 1009 self.b = [[] for _ in range(self.size)] def put(self, key, value): bucket = self.b[key % self.size] for p in bucket: if p[0] == key: p[1] = value return bucket.append([key, value]) def get(self, key): for k, v in self.b[key % self.size]: if k == key: return v return -1 def remove(self, key): bucket = self.b[key % self.size] bucket[:] = [p for p in bucket if p[0] != key]javaimport java.util.*; class MyHashMap { private static final int SIZE = 1009; private final List<int[]>[] b = new List[SIZE]; MyHashMap() { for (int i = 0; i < SIZE; i++) b[i] = new LinkedList<>(); } void put(int key, int value) { for (int[] p : b[key % SIZE]) { if (p[0] == key) { p[1] = value; return; } } b[key % SIZE].add(new int[]{key, value}); } int get(int key) { for (int[] p : b[key % SIZE]) if (p[0] == key) return p[1]; return -1; } void remove(int key) { b[key % SIZE].removeIf(p -> p[0] == key); } }10 Design an LRU cache with O(1) get and put.
hardYou need hash lookup plus an ordering by recent use. Python OrderedDict and Java LinkedHashMap with access order keep both: on get, move the key to the end; on put, insert or move to the end and evict the oldest entry when the size exceeds capacity. Interviewers often ask you to build the same thing with a hash map and a doubly linked list. Time O(1) per operation, space O(capacity).. Edge cases: capacity 1, updating an existing key must not evict, get of a missing key returns -1.
pythonfrom collections import OrderedDict class LRUCache: def __init__(self, capacity): self.cap = capacity self.d = OrderedDict() def get(self, key): if key not in self.d: return -1 self.d.move_to_end(key) return self.d[key] def put(self, key, value): self.d[key] = value self.d.move_to_end(key) if len(self.d) > self.cap: self.d.popitem(last=False)javaimport java.util.*; class LRUCache { private final LinkedHashMap<Integer, Integer> m; LRUCache(final int cap) { m = new LinkedHashMap<>(16, 0.75f, true) { protected boolean removeEldestEntry(Map.Entry<Integer, Integer> e) { return size() > cap; } }; } int get(int key) { return m.getOrDefault(key, -1); } void put(int key, int value) { m.put(key, value); } }
Frequently asked questions
When should I use a HashSet instead of a HashMap?
Use a set when you only need to know whether a value exists, such as detecting duplicates or the longest consecutive run. Use a map when you need to attach data, such as an index or a count.
What is the worst-case time of a hash lookup?
Expected O(1), but O(n) if many keys collide in one bucket. Java trees long chains so it becomes O(log n). Say "expected O(1)" in interviews.
Can I use a list as a dictionary key in Python?
No, lists are mutable and unhashable. Use a tuple, a string or a frozenset instead.
How is hashing different from sorting for duplicates?
Hashing is O(n) time but needs O(n) space. Sorting is O(n log n) and can be done in place. Mention both and choose by the constraint.
Is the Two Sum solution valid for sorted input too?
Yes, but a sorted array lets you use two pointers with O(1) space. See two pointers questions.
Related guides
- Array interview questions with worked solutions
- String interview questions with worked solutions
- Prefix sum interview questions with worked solutions
- Top K elements interview questions with worked solutions
- Two pointers interview questions with worked solutions
- Linked list interview questions with worked solutions
More in DSA Interview Questions
- Heap and Priority Queue Interview Questions
- Interval DP Interview Questions
- Interval interview questions with worked solutions
- Kadane algorithm interview questions with worked solutions
- KMP and string matching interview questions with solutions
- Knapsack DP Interview Questions
- Linked list interview questions with worked solutions
- Longest Common Subsequence (LCS) Interview Questions
- Longest Increasing Subsequence (LIS) Interview Questions
- LRU Cache and Design Data Structure Interview Questions
- Math and number theory interview questions with solutions
- Matrix interview questions with worked solutions