4. Dictionaries

A dictionary is a mapping from keys to values.

Quick Reference: Dictionary methods

Method	Purpose	Returns	Complexity	Notes
`get(key, default=None)`	Safely read value	Value or default	O(1) average	No `KeyError` if missing
`keys()`	View of all keys	`dict_keys` view	O(1)	Dynamic view, not a list
`values()`	View of all values	`dict_values` view	O(1)	Dynamic view
`items()`	View of key-value pairs	`dict_items` view	O(1)	Very common for iteration
`pop(key[, default])`	Remove and return value for key	Value	O(1) average	Raises `KeyError` if missing and no default
`popitem()`	Remove and return last inserted pair	`(key, value)` tuple	O(1) average	LIFO in modern Python
`update(other)`	Merge in values from another mapping / iterable	`None`	O(k)	Overwrites existing keys
`setdefault(key[, default])`	Get value, insert default if missing	Value	O(1) average	Useful for grouping/counting
`clear()`	Remove all items	`None`	O(n)	Keeps same dict object
`copy()`	Shallow copy	New dict	O(n)	Nested mutables are still shared
`fromkeys(iterable, value=None)`	Create new dict with given keys	New dict	O(n)	All keys share same value object

Quick Reference: Common dictionary operations

Operation	Purpose	Returns	Complexity	Notes
`d[key]`	Get value by key	Value	O(1) average	Raises `KeyError` if missing
`d[key] = value`	Insert or update key	`None`	O(1) average	Overwrites if key exists
`del d[key]`	Delete key-value pair	`None`	O(1) average	Deletes only
`len(d)`	Number of items	`int`	O(1)	Very common
`key in d`	Membership check by key	`bool`	O(1) average	Checks keys, not values
`value in d.values()`	Membership check by value	`bool`	O(n)	Values require scan
`for key in d`	Iterate keys	Iterator behavior	O(n) total	Default iteration is over keys
`for key, value in d.items()`	Iterate key-value pairs	Iterator behavior	O(n) total	Most common iteration pattern
`dict(iterable_or_mapping)`	Create dict from mapping / pairs	New dict	O(n)	Common conversion
`{k: v for ...}`	Dictionary comprehension	New dict	O(n)	Very common in interviews
`d1	d2`	Merge dictionaries	New dict	O(n + m)
`d1	= d2`	Merge into existing dict	`None`	O(m)
`{d1, d2}`	Merge via unpacking	New dict	O(n + m)	Common in older code
`sorted(d)`	Sorted list of keys	New list	O(n log n)	Dict iteration is by key
`sorted(d.items(), key=...)`	Sort items with custom rule	New list	O(n log n)	Common interview pattern
`reversed(d)`	Reverse insertion-order keys	Iterator	O(n) total	Modern Python

Example

user = {
    "name": "Ruben",
    "age": 30
}

Here:

"name" is the key
"Ruben" is the value

Why dictionaries are powerful

The main reason dictionaries are so important is fast lookup.

user["name"]   # "Ruben"

Average lookup complexity:

O(1)

This is one of the most common interview questions.

Dictionaries are used constantly in:

API payloads
JSON data
frequency counting
grouping
caching
lookup tables
object mappings by ID

1.4.2 How lookup works conceptually

Python dictionaries use hashing.

Mental model

key -> hash -> bucket -> value

Example

prices = {
    "apple": 2,
    "banana": 1
}

When you do:

prices["apple"]

Python:

hashes "apple"
finds the bucket
retrieves the value

This is why lookup is usually constant time.

A strong verbal answer should mention hash table / hash map.

1.4.3 Important dictionary methods

These are the core methods you need to understand.

`get()`

Safe access to dictionary values — returns None if key missing (instead of raising KeyError).

user = {"name": "Alice", "age": 30}
user.get("name")      # "Alice"
user.get("email")     # None
user.get("email", "unknown")  # "unknown"

This is one of the most important dictionary methods for avoiding crashes.

Complexity: O(1)

Interview context: Essential for avoiding KeyError. Very common in production code.

`keys()` / `values()` / `items()`

Get keys, values, or key-value pairs.

user = {"name": "Alice", "age": 30}
user.keys()      # dict_keys(['name', 'age'])
user.values()    # dict_values(['Alice', 30])
user.items()     # dict_items([('name', 'Alice'), ('age', 30)])

Most Pythonic iteration pattern:

for key, value in user.items():
    print(key, value)

This is much preferred over user.keys() when you need both.

Complexity: O(1) to get the view, O(n) to iterate.

`pop()`

Remove a key and return its value.

value = user.pop("age")
print(value)   # 30
print(user)    # {"name": "Alice"}

Raises KeyError if key doesn't exist:

user.pop("email")  # KeyError

Safe version with default:

user.pop("email", None)  # Returns None if missing

Complexity: O(1)

Interview use: Useful when you need to extract and process values.

`setdefault()`

Get a value, or set it to a default if missing. Very useful for grouping and frequency counting.

user = {"name": "Alice"}
user.setdefault("age", 0)    # Returns 0, adds "age": 0 to dict
user.setdefault("name", "Unknown")  # Returns "Alice" (already exists)

Very useful for frequency counting:

counts = {}
words = ["apple", "banana", "apple"]

for word in words:
    counts[word] = counts.get(word, 0) + 1  # Alternative to setdefault
    # Or: counts.setdefault(word, 0) += 1

Extremely useful for grouping:

people_by_city = {}
for person in people:
    city = person["city"]
    people_by_city.setdefault(city, []).append(person)

Complexity: O(1)

Interview context: Shows up constantly in grouping problems.

`update()`

Merge another dictionary into this one.

user = {"name": "Alice"}
user.update({"age": 30, "city": "NYC"})
print(user)  # {"name": "Alice", "age": 30, "city": "NYC"}

Overwrites existing keys:

user = {"name": "Alice", "age": 25}
user.update({"age": 30})
print(user)  # {"name": "Alice", "age": 30}

Complexity: O(k) where k = items being added.

`clear()`

Remove all items from dictionary.

user = {"name": "Alice", "age": 30}
user.clear()
print(user)  # {}

Complexity: O(n)

Membership with `in`

Check if a key exists (checks keys, not values).

"name" in user        # True
"email" in user       # False
"Alice" in user       # False (checks keys, not values)

This is the preferred way over get() when you just need a boolean.

Complexity: O(1)

1.4.4 Dictionary comprehensions

One of the most important Pythonic features.

Basic syntax

squares = {x: x * x for x in range(5)}

Result

{0: 0, 1: 1, 2: 4, 3: 9, 4: 16}

This is the dictionary equivalent of list comprehensions.

Mental model

Equivalent to:

squares = {}

for x in range(5):
    squares[x] = x * x

A strong interview answer should understand both forms.

Conditional dictionary comprehension

evens = {x: x * x for x in range(10) if x % 2 == 0}

Result

{0: 0, 2: 4, 4: 16, 6: 36, 8: 64}

Very useful for transforming or filtering data in one line.

1.4.5 Important dictionary patterns

These patterns appear in almost every interview:

Frequency counting: counts[key] = counts.get(key, 0) + 1
Grouping: grouped.setdefault(key, []).append(item)
Lookup by ID: by_id = {item.id: item for item in items}
Safe access: value = d.get(key, default)
Transformation: new_d = {k: transform(v) for k, v in d.items()}

Verbal interview questions

Answer these out loud:

Why is dictionary lookup usually O(1)?
Why use get() instead of direct indexing?
Explain items()
Explain dictionary comprehension
When would you use a dictionary over a list?

Coding drills

Drill 1: word frequency

def count_words(words: list[str]) -> dict[str, int]:
    ...

Drill 2: group by city

def group_by_city(people: list[dict]) -> dict[str, list]:
    ...

Drill 3: invert mapping

def invert(d: dict[str, int]) -> dict[int, str]:
    ...

Example

{"a": 1, "b": 2} -> {1: "a", 2: "b"}

1.4.6 Common interview problems

Dictionaries solve many interview problems elegantly.

Problem 1: Two Sum

Question: Given a list of integers and a target, find two numbers that sum to the target. Return their indices.

def twoSum(nums: list[int], target: int) -> list[int]:
    # nums = [2, 7, 11, 15], target = 9
    # Return [0, 1]  (2 + 7 = 9)
    ...

Key insight: Use dictionary to store number→index mapping. For each number, look up if (target - number) exists.

num_map = {}
for i, num in enumerate(nums):
    complement = target - num
    if complement in num_map:
        return [num_map[complement], i]
    num_map[num] = i
return []

Complexity: O(n) time, O(n) space. Much better than brute force O(n²).

Problem 2: Valid Anagram

Question: Given two strings, determine if they are anagrams (same characters, different order).

def isAnagram(s: str, t: str) -> bool:
    # s = "anagram", t = "nagaram" → True
    # s = "rat", t = "car" → False
    ...

Key insight: Count character frequencies. If both strings have same frequency map, they're anagrams.

from collections import Counter
return Counter(s) == Counter(t)

Complexity: O(n) time, O(1) space (only 26 letters).

Problem 3: Group Anagrams

Question: Given a list of strings, group anagrams together.

def groupAnagrams(strs: list[str]) -> list[list[str]]:
    # strs = ["eat", "tea", "ate", "nat", "tan", "bat"]
    # Return [["eat", "tea", "ate"], ["nat", "tan"], ["bat"]]
    ...

Key insight: Use sorted string as key—anagrams have the same sorted key.

groups = {}
for word in strs:
    key = ''.join(sorted(word))  # "eat", "tea", "ate" all → "aet"
    groups.setdefault(key, []).append(word)
return list(groups.values())

Complexity: O(n * k log k) where n = words, k = avg word length.

Problem 4: Top K Frequent Elements

Question: Count word frequencies, find the k most frequent.

def topKFrequent(words: list[str], k: int) -> list[str]:
    # words = ["apple", "banana", "apple", "cherry", "banana", "apple"]
    # k = 2
    # Return ["apple", "banana"]  (apple: 3, banana: 2)
    ...

Key insight: Use Counter to count frequencies, then get top k.

from collections import Counter
counts = Counter(words)
return [word for word, _ in counts.most_common(k)]

Complexity: O(n + m log k) where m = unique words.

Problem 5: Majority Element

Question: Find the element that appears more than n/2 times.

def majorityElement(nums: list[int]) -> int:
    # nums = [3, 2, 3, 1, 3]
    # Return 3 (appears 3 times, more than 5/2)
    ...

Key insight: Count frequencies, return element with max count.

counts = {}
for num in nums:
    counts[num] = counts.get(num, 0) + 1
return max(counts, key=counts.get)

Complexity: O(n) time, O(n) space.

Problem 6: Ransom Note

Question: Can you create a ransom note from magazine letters (each letter used at most once)?

def canConstruct(ransomNote: str, magazine: str) -> bool:
    # ransomNote = "a", magazine = "abc" → True
    # ransomNote = "aa", magazine = "abc" → False
    ...

Key insight: Count available letters in magazine, verify each ransom letter is available.

available = {}
for char in magazine:
    available[char] = available.get(char, 0) + 1

for char in ransomNote:
    if available.get(char, 0) == 0:
        return False
    available[char] -= 1

return True

Complexity: O(n + m) where n = ransom length, m = magazine length.

Problem 7: Longest Consecutive Sequence

Question: Find the length of the longest consecutive elements sequence.

def longestConsecutive(nums: list[int]) -> int:
    # nums = [100, 4, 200, 1, 3, 2]
    # Return 4  (sequence is [1, 2, 3, 4])
    ...

Key insight: Use set for O(1) lookup. For each number, check if it's start of a sequence.

num_set = set(nums)
longest = 0

for num in num_set:
    if num - 1 not in num_set:  # Start of sequence
        length = 1
        while num + length in num_set:
            length += 1
        longest = max(longest, length)

return longest

Complexity: O(n) amortized (each number visited at most twice).

Problem 8: First Unique Character

Question: Find the index of the first character that appears only once.

def firstUniqChar(s: str) -> int:
    # s = "leetcode" → 0 ('l' appears once)
    # s = "loveleetcode" → 2 ('v' is first unique)
    # s = "aabb" → -1
    ...

Key insight: Count frequencies, then find first with count = 1.

counts = {}
for char in s:
    counts[char] = counts.get(char, 0) + 1

for i, char in enumerate(s):
    if counts[char] == 1:
        return i

return -1

Complexity: O(n) time, O(1) space (only 26 letters).

Problem 9: Happy Number

Question: Does repeatedly summing squares of digits eventually reach 1, or enter a cycle?

def isHappy(n: int) -> bool:
    # n = 7 → True (7 → 49 → 97 → 130 → 10 → 1)
    # n = 2 → False (enters cycle)
    ...

Key insight: Use set to detect cycles.

def get_next(n):
    total = 0
    while n > 0:
        digit = n % 10
        total += digit ** 2
        n //= 10
    return total

seen = set()
while n != 1 and n not in seen:
    seen.add(n)
    n = get_next(n)

return n == 1

Complexity: O(k) where k = iterations before reaching 1 or cycle.

Problem 10: Isomorphic Strings

Question: Are two strings isomorphic? (Characters can be replaced to make them equal.)

def isIsomorphic(s: str, t: str) -> bool:
    # s = "egg", t = "add" → True (e→a, g→d)
    # s = "badc", t = "baba" → False
    ...

Key insight: Map characters bidirectionally. Each char in s maps to exactly one in t, and vice versa.

s_to_t = {}
t_to_s = {}

for c1, c2 in zip(s, t):
    if c1 in s_to_t and s_to_t[c1] != c2:
        return False
    if c2 in t_to_s and t_to_s[c2] != c1:
        return False
    s_to_t[c1] = c2
    t_to_s[c2] = c1

return True

Complexity: O(n) time, O(1) space (at most 26 characters).

Dictionaries

4. Dictionaries

Quick Reference: Dictionary methods

Quick Reference: Common dictionary operations

Example

Why dictionaries are powerful

1.4.2 How lookup works conceptually

Mental model

Example

1.4.3 Important dictionary methods

get()

keys() / values() / items()

pop()

setdefault()

update()

clear()

Membership with in

1.4.4 Dictionary comprehensions

Basic syntax

Result

Mental model

Conditional dictionary comprehension

Result

1.4.5 Important dictionary patterns

Verbal interview questions

Coding drills

Drill 1: word frequency

Drill 2: group by city

Drill 3: invert mapping

Example

1.4.6 Common interview problems

Problem 1: Two Sum

Problem 2: Valid Anagram

Problem 3: Group Anagrams

Problem 4: Top K Frequent Elements

Problem 5: Majority Element

Problem 6: Ransom Note

Problem 7: Longest Consecutive Sequence

Problem 8: First Unique Character

Problem 9: Happy Number

Problem 10: Isomorphic Strings

`get()`

`keys()` / `values()` / `items()`

`pop()`

`setdefault()`

`update()`

`clear()`

Membership with `in`