Dictionaries and Sets Checkpoint
A review of this module. Skip it if you feel confident; the next module does not need it.
Fix the mistakes
The slips that cost marks in this module. Spot each one, then check the fix.
Hash tables (dictionaries and sets) are the most important data structures in technical interview rounds.
Frequency map (word/element counter)
Frequency map is a dictionary that stores how many times each item appears in a sequence. The item is the key and its count is the value. It is built in one pass over the data.
Count the occurrences of items in a sequence using dict.get().
words = ["apple", "banana", "apple", "cherry", "apple"]counts = {}for w in words: counts[w] = counts.get(w, 0) + 1print(counts)Example 1 · Orders per customer
orders = ["Asha", "Ravi", "Asha", "Meena", "Asha", "Ravi"]counts = {}for customer in orders: counts[customer] = counts.get(customer, 0) + 1print(counts)print(counts["Asha"]){'Asha': 3, 'Ravi': 2, 'Meena': 1}
3What this code does
counts.get(customer, 0)gives 0 the first time a name appears, so there is no KeyError.- Each pass adds 1 to that customer's count.
- One loop over 6 orders gives all the counts.
Produces {'apple': 3, 'banana': 1, 'cherry': 1} in O(N) linear time.
Two Sum problem in O(N) time
Two Sum is a classic problem: in a list of numbers, find two that add up to a target. Keeping the numbers already seen in a dictionary lets you solve it in one pass instead of two nested loops.
Find two numbers in an array that add up to a target using a dictionary to remember seen values.
nums = [2, 7, 11, 15]target = 9seen = {}for i, num in enumerate(nums): diff = target - num if diff in seen: print(f"Indices: {seen[diff]}, {i}") break seen[num] = iExample 2 · Finding shared records
dataset_a = [10, 20, 30, 40]dataset_b = [30, 40, 50, 60]
# Find common recordscommon = set(dataset_a) & set(dataset_b)print("Shared IDs:", sorted(common))Shared IDs: [30, 40]
What this code does
- Converts lists to sets and computes intersection with
&. - Outputs shared records:
[30, 40].
Example 3 · Finding a pair that adds up
prices = [12, 7, 25, 3, 18]target = 21seen = {}for i, price in enumerate(prices): need = target - price if need in seen: print(f"Pair found at {seen[need]} and {i}") break seen[price] = iPair found at 3 and 4
What this code does
seenremembers each price and the index where it was found.- At index 4 the price is 18, so
needis 3, and 3 was seen at index 3. - Prices 3 and 18 add up to 21, found in a single pass.
Because $9 - 7 = 2$ was already seen at index 0, it outputs indices 0 and 1 in O(N) time.
Finish up
Mark complete & continue
Next: Must-do problems: Dictionaries and Sets