The hash map is the most important data structure in interview coding. These problems show five of its most common interview applications.
Problems: 5
Difficulty: Easy – Hard
Key libs: collections.Counter · defaultdict · set
The core insight: Whenever you need to check "have I seen this before?" or "how many times did X appear?",
the answer is almost always a dict or set. This turns O(n²) brute-force into O(n).
P 19Coding ProblemEasy
Two Sum
Given a list of integers and a target, return the indices of the two numbers that sum to the target.
Assume exactly one solution exists. You may not use the same element twice.
Must run in O(n) time.
dict: value → indexcomplement = target - nO(1) lookupsingle pass
Solution
from typing import List, Tuple, Optional
deftwo_sum(nums: List[int], target: int) -> Optional[Tuple[int, int]]:
seen = {} # value → index of where we saw itfor i, n inenumerate(nums):
complement = target - n
if complement in seen:
return (seen[complement], i)
seen[n] = i # store AFTER checking so we don't use same index twicereturnNone# no solution found
The key trick: For each number n, ask "does the number I need (target - n) already exist in the dict?"
If yes — done. If no — store n and move on.
Note: store after checking so you don't accidentally match a number with itself (e.g., [3], target=6 should return None, not (0,0)).
Time: O(n). Space: O(n).
P 20Coding ProblemEasy
First Non-Repeating Character
Find the first character in a string that appears exactly once.
Return the character, or None if all characters repeat.
Must run in O(n) time.
Countertwo-pass: count then scanpreserve insertion order
Solution
from collections import Counter
from typing import Optional
deffirst_unique(s: str) -> Optional[str]:
counts = Counter(s) # O(n): count every character# O(n): scan left-to-right to find FIRST uniquefor ch in s:
if counts[ch] == 1:
return ch
returnNone
Why two passes? We need global frequency info before we can judge any character.
Pass 1: build a Counter in one line — all frequencies known.
Pass 2: scan the original string (to maintain order) and return the first character with count 1.
Total: O(n) time, O(k) space where k is the number of unique characters (≤ 26 for lowercase alpha).
P 21Coding ProblemHard
Subarray Sum Equals K
Count the number of contiguous subarrays that sum to exactly k.
Must run in O(n) time — the brute-force O(n²) won't be accepted.
Array can contain negative numbers.
Example
count_subarrays([1, 1, 1], k=2) → 2 # [1,1] appears at index 0-1 and 1-2
count_subarrays([1, 2, 3], k=3) → 2 # [3] and [1,2]
count_subarrays([1,-1,1,-1], k=0) → 4
prefix sumsdefaultdict(int)complement lookup: prefix - krunning sum
Solution
from collections import defaultdict
from typing import List
defcount_subarrays(nums: List[int], k: int) -> int:
# prefix_counts[s] = how many times we've seen prefix sum s
prefix_counts: dict = defaultdict(int)
prefix_counts[0] = 1# empty prefix sums to 0
total = 0
running_sum = 0for n in nums:
running_sum += n
# If (running_sum - k) was seen before, the subarray between# that earlier index and now sums to exactly k
total += prefix_counts[running_sum - k]
prefix_counts[running_sum] += 1return total
The insight: A subarray nums[i..j] sums to k if and only if
prefix[j] - prefix[i-1] == k, i.e., prefix[j] - k == prefix[i-1].
So at each position j, we ask: "how many previous prefix sums equal running_sum - k?"
Each occurrence is a valid subarray ending at j.
The prefix_counts[0] = 1 seed handles subarrays starting at index 0.
Time: O(n). Space: O(n).
P 22Coding ProblemMedium
Top-K Frequent Words
Given a string of text, return the K most frequent words.
If two words have the same frequency, sort them alphabetically.
Words are case-insensitive; ignore punctuation.
Example
text = "the sky is blue the sky is beautiful"
top_k_words(text, k=3) → ["sky", "the", "is"]
# "sky"=2, "the"=2, "is"=2, "blue"=1, "beautiful"=1
# All tied at 2, so sort alphabetically: "is" < "sky" < "the"
import re
from collections import Counter
from typing import List
deftop_k_words(text: str, k: int) -> List[str]:
words = re.findall(r"\b[a-z]+\b", text.lower())
counts = Counter(words)
# Sort by: frequency descending (-count), then alphabetically ascending
ranked = sorted(counts.items(), key=lambda x: (-x[1], x[0]))
return [word for word, _ in ranked[:k]]
Key ideas: The multi-key sort tuple (-count, word) is the interview-standard way to handle "sort by X desc, then by Y asc".
Negating the count reverses the sort order without needing reverse=True (which would also reverse the alphabetical sort).
re.findall(r"\b[a-z]+\b", text.lower()) handles punctuation and capitalisation in one line.
P 23Coding ProblemMedium
Find All Pairs with Difference K
Given a list of integers and a positive integer k, find all unique pairs (a, b)
where b - a == k and a < b. Return pairs sorted as a list of tuples.
set for O(1) lookupn+k in num_setdedup via set of pairssorted() output
Solution
from typing import List, Tuple
defpairs_with_diff(nums: List[int], k: int) -> List[Tuple[int, int]]:
num_set = set(nums)
result: set = set()
for n in num_set:
# Check if n + k exists; by convention a < b so pair is (n, n+k)if n + k in num_set:
result.add((n, n + k))
returnsorted(result)
Key ideas: Iterate over the set of numbers (not the original list) to avoid processing duplicates.
For each number n, check if n + k exists in the set — O(1) lookup.
Using a set for result also deduplicates pairs automatically.
Time: O(n). Space: O(n).
Note: iterating over num_set instead of nums is the key insight that avoids duplicate pairs from duplicate values in the input.