Category C · 5 Problems

Dict & Counting Patterns

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 19 Coding Problem Easy
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.
Example
two_sum([2, 7, 11, 15], target=9) → (0, 1) two_sum([3, 2, 4], target=6) → (1, 2) two_sum([3, 3], target=6) → (0, 1)
dict: value → indexcomplement = target - n O(1) lookupsingle pass
Solution
from typing import List, Tuple, Optional def two_sum(nums: List[int], target: int) -> Optional[Tuple[int, int]]: seen = {} # value → index of where we saw it for i, n in enumerate(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 twice return None # 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 20 Coding Problem Easy
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.
Example
first_unique("leetcode") → "l" first_unique("aabb") → None first_unique("loveleetcode") → "v"
Countertwo-pass: count then scan preserve insertion order
Solution
from collections import Counter from typing import Optional def first_unique(s: str) -> Optional[str]: counts = Counter(s) # O(n): count every character # O(n): scan left-to-right to find FIRST unique for ch in s: if counts[ch] == 1: return ch return None
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 21 Coding Problem Hard
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 def count_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 = 0 for 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] += 1 return 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 22 Coding Problem Medium
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"
re.findallCounter multi-key sort: (-freq, word)str.lower()
Solution
import re from collections import Counter from typing import List def top_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 23 Coding Problem Medium
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.
Example
pairs_with_diff([1,5,3,4,2], k=2) → [(1,3),(2,4),(3,5)] pairs_with_diff([1,1,2,2,3], k=1) → [(1,2),(2,3)] # no duplicates pairs_with_diff([1,2,3], k=5) → []
set for O(1) lookupn+k in num_set dedup via set of pairssorted() output
Solution
from typing import List, Tuple def pairs_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)) return sorted(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.
← Category B: Strings Category D: Lists & Sequences →