Python Dictionary Hashing Mechanism: Practice Problems & Exercises
Practice: Dictionary Hashing Mechanism
← Back to lessonGiven pairs of Python objects, determine for each pair whether they are equal, whether their hashes match, and whether the hashability contract holds. The contract states: if a == b then hash(a) == hash(b) must be true. The reverse is not required.
def hash_equality_check(pairs):
results = []
for a, b in pairs:
are_equal = (a == b)
hashes_match = (hash(a) == hash(b))
# Contract: if equal, hashes MUST match
contract_holds = (not are_equal) or hashes_match
results.append((are_equal, hashes_match, contract_holds))
return results
# Test
test_pairs = [
(1, 1.0), # int and float with same value
(1, 2), # different ints
(True, 1), # bool and int
(1.0, True), # float and bool
(0, 0.5), # different values but let's check
]
for pair, result in zip(test_pairs, hash_equality_check(test_pairs)):
print(result)Solution
The key insight is that 1 == 1.0 == True in Python, and they all share the same hash value. The hashability contract is a one-way implication: equality implies equal hashes, but equal hashes do not imply equality (collisions are fine).
def hash_equality_check(pairs):
results = []
for a, b in pairs:
are_equal = (a == b)
hashes_match = (hash(a) == hash(b))
contract_holds = (not are_equal) or hashes_match
results.append((are_equal, hashes_match, contract_holds))
return results
For built-in types, Python always satisfies the contract. You only break it by writing a bad custom __hash__.
def hash_equality_check(pairs):
"""
Given a list of (a, b) pairs, return a list of booleans.
Each boolean is True if a and b satisfy the hashability
contract: a == b implies hash(a) == hash(b).
Also return whether a == b and whether hash(a) == hash(b)
for each pair as a tuple: (are_equal, hashes_match, contract_holds)
"""
# TODO: implement
passExpected Output
(True, True, True)
(False, False, True)
(True, True, True)
(True, True, True)
(False, True, True)Hints
Hint 1: The contract says: if a == b then hash(a) == hash(b) must hold.
Hint 2: The contract does NOT require: if hash(a) == hash(b) then a == b. Hash collisions are allowed.
Hint 3: Check each pair: compute are_equal = (a == b), hashes_match = (hash(a) == hash(b)), then contract_holds = (not are_equal) or hashes_match.
Simulate a sequence of dict set/delete operations and return the final keys in insertion order. Remember that updating a value for an existing key does NOT move it to the end — only new keys are appended.
def track_insertion_order(operations):
d = {}
for op in operations:
if op[0] == "set":
_, key, value = op
d[key] = value
elif op[0] == "del":
_, key = op
d.pop(key, None) # ignore if missing
return list(d.keys())
# Test 1
ops1 = [
("set", "a", 1),
("set", "b", 2),
("set", "c", 3),
("set", "a", 99), # update — position unchanged
("del", "b"), # remove b
("set", "d", 4), # new key at end
]
print(track_insertion_order(ops1))
# Test 2
ops2 = [
("set", "x", 10),
("set", "y", 20),
("set", "z", 30),
("del", "y"),
("del", "w"), # missing key — no error
]
print(track_insertion_order(ops2))Solution
Python dicts since 3.7 guarantee insertion order. The key insight is that d[key] = value on an existing key updates the value in-place without changing the key's position. Deletion removes the key entirely, and re-insertion would place it at the end.
def track_insertion_order(operations):
d = {}
for op in operations:
if op[0] == "set":
_, key, value = op
d[key] = value
elif op[0] == "del":
_, key = op
d.pop(key, None)
return list(d.keys())
def track_insertion_order(operations):
"""
Given a list of operations on a dict, return the final
list of keys in insertion order.
Operations are tuples:
("set", key, value) - insert or update
("del", key) - delete key (ignore if missing)
Remember: updating an existing key does NOT change its
insertion-order position.
"""
# TODO: implement
passExpected Output
['a', 'c', 'd']
['x', 'z']Hints
Hint 1: Use a plain dict — Python 3.7+ guarantees insertion order.
Hint 2: When you update an existing key, its position in iteration order stays the same.
Hint 3: Deleting a key removes it from the order entirely. If re-inserted later, it goes to the end.
Determine which Python objects can be used as dictionary keys by testing whether they are hashable. An object is hashable if hash() succeeds without raising TypeError.
def classify_hashability(objects):
results = []
for obj in objects:
try:
hash(obj)
results.append((repr(obj), True))
except TypeError:
results.append((repr(obj), False))
return results
test_objects = [
42,
"hello",
(1, 2, 3),
[1, 2, 3],
frozenset({1, 2}),
{1, 2},
((1, 2), (3, 4)),
([1, 2], [3, 4]),
None,
]
for result in classify_hashability(test_objects):
print(result)Solution
The rule: immutable built-in types are hashable (int, float, str, tuple of hashables, frozenset, None, bool, bytes). Mutable containers (list, set, dict) are not. A tuple containing an unhashable element (like a list) is itself unhashable because tuple.__hash__ recursively hashes each element.
def classify_hashability(objects):
results = []
for obj in objects:
try:
hash(obj)
results.append((repr(obj), True))
except TypeError:
results.append((repr(obj), False))
return results
def classify_hashability(objects):
"""
Given a list of Python objects, return a list of tuples:
(object_repr, is_hashable)
An object is hashable if calling hash() on it does NOT
raise TypeError.
"""
# TODO: implement
passExpected Output
('42', True)
('hello', True)
('(1, 2, 3)', True)
('[1, 2, 3]', False)
('frozenset({1, 2})', True)
('{1, 2}', False)
('((1, 2), (3, 4))', True)
('([1, 2], [3, 4])', False)
('None', True)Hints
Hint 1: Use a try/except block around hash(obj) to catch TypeError.
Hint 2: Lists, sets, and dicts are unhashable. Tuples are hashable ONLY if all their elements are hashable.
Hint 3: A tuple containing a list is NOT hashable — the hash function recurses into elements.
Implement three common dict comprehension patterns: inverting a dict, filtering by value, and merging with conflict resolution.
def invert_dict(d):
return {v: k for k, v in d.items()}
def filter_by_value(d, threshold):
return {k: v for k, v in d.items() if v > threshold}
def merge_with_sum(d1, d2):
merged = dict(d1) # shallow copy
for k, v in d2.items():
merged[k] = merged.get(k, 0) + v
return merged
# Test invert
print(invert_dict({"a": 1, "b": 2, "c": 3}))
# Test filter
prices = {"apple": 1.2, "banana": 0.5, "cherry": 2.0, "durian": 5.5}
print(filter_by_value(prices, 1.5))
# Test merge with sum
d1 = {"a": 1, "b": 2, "c": 3}
d2 = {"a": 2, "b": 3, "d": 4, "c": 3}
print(merge_with_sum(d1, d2))Solution
def invert_dict(d):
return {v: k for k, v in d.items()}
def filter_by_value(d, threshold):
return {k: v for k, v in d.items() if v > threshold}
def merge_with_sum(d1, d2):
merged = dict(d1)
for k, v in d2.items():
merged[k] = merged.get(k, 0) + v
return merged
Key points:
invert_dictassumes values are unique. If not, later keys overwrite earlier ones.filter_by_valueuses theifclause in the comprehension — clean and readable.merge_with_sumuses.get(k, 0)to handle keys that exist in only one dict.
def invert_dict(d):
"""Return a new dict with keys and values swapped."""
# TODO: implement with a dict comprehension
pass
def filter_by_value(d, threshold):
"""Return entries where the value exceeds the threshold."""
# TODO: implement with a dict comprehension
pass
def merge_with_sum(d1, d2):
"""
Merge two dicts. If a key exists in both, sum the values.
Keys unique to either dict are included as-is.
"""
# TODO: implement
passExpected Output
{1: 'a', 2: 'b', 3: 'c'}
{'cherry': 2.0, 'durian': 5.5}
{'a': 3, 'b': 5, 'c': 6, 'd': 4}Hints
Hint 1: For invert_dict, use: return a comprehension iterating over d.items() and swapping k, v.
Hint 2: For filter_by_value, add an if clause to the comprehension.
Hint 3: For merge_with_sum, start with a copy of d1, then iterate over d2 and use .get() with a default of 0 to handle missing keys.
Create a Color class with proper __hash__ and __eq__ so that two Color objects with the same RGB values can be used interchangeably as dict keys. Verify the hashability contract holds.
class Color:
def __init__(self, r: int, g: int, b: int):
self.r = r
self.g = g
self.b = b
def __repr__(self):
return f"Color({self.r}, {self.g}, {self.b})"
def __eq__(self, other):
if not isinstance(other, Color):
return NotImplemented
return self.r == other.r and self.g == other.g and self.b == other.b
def __hash__(self):
return hash((self.r, self.g, self.b))
# Test
c1 = Color(220, 20, 60)
c2 = Color(220, 20, 60)
c3 = Color(0, 0, 255)
# Contract checks
print(c1 == c2) # True
print(hash(c1) == hash(c2)) # True (required by contract)
print(c1 != c3) # True
# Use as dict key
palette = {c1: "crimson", c3: "blue"}
print(len(palette)) # 1 key per unique color
print(palette[c2]) # "crimson" — c2 finds c1's entrySolution
class Color:
def __init__(self, r: int, g: int, b: int):
self.r = r
self.g = g
self.b = b
def __repr__(self):
return f"Color({self.r}, {self.g}, {self.b})"
def __eq__(self, other):
if not isinstance(other, Color):
return NotImplemented
return self.r == other.r and self.g == other.g and self.b == other.b
def __hash__(self):
return hash((self.r, self.g, self.b))
Critical rules:
__eq__must returnNotImplemented(notFalse) for unknown types — this lets Python try the other operand's__eq__.__hash__must use the exact same fields as__eq__. If you hash only(self.r, self.g)but compare all three, two Colors with same r,g but different b would be equal yet have different hashes — violating the contract.- Using
hash((self.r, self.g, self.b))delegates to Python's built-in tuple hashing, which is well-distributed and collision-resistant.
class Color:
"""
Represents an RGB color. Two colors are equal if they
have the same (r, g, b) values. Must be usable as a
dict key.
"""
def __init__(self, r: int, g: int, b: int):
self.r = r
self.g = g
self.b = b
def __repr__(self):
return f"Color({self.r}, {self.g}, {self.b})"
def __eq__(self, other):
# TODO: implement
pass
def __hash__(self):
# TODO: implement
passExpected Output
True
True
True
1
crimsonHints
Hint 1: In __eq__, first check isinstance(other, Color), returning NotImplemented if not.
Hint 2: Compare all three channels: self.r == other.r and self.g == other.g and self.b == other.b.
Hint 3: In __hash__, hash the tuple of the same fields used in __eq__: return hash((self.r, self.g, self.b)).
Hint 4: If you define __eq__ without __hash__, Python sets __hash__ = None and your class becomes unhashable.
Implement a hash map that uses separate chaining for collision resolution. Each bucket holds a list of (key, value) pairs. Collisions are handled by appending to the same bucket list.
class SimpleHashMap:
def __init__(self, capacity=8):
self.capacity = capacity
self.size = 0
self.buckets = [[] for _ in range(capacity)]
def _index(self, key):
return hash(key) % self.capacity
def put(self, key, value):
idx = self._index(key)
bucket = self.buckets[idx]
for i, (k, v) in enumerate(bucket):
if k == key:
bucket[i] = (key, value)
return
bucket.append((key, value))
self.size += 1
def get(self, key, default=None):
idx = self._index(key)
for k, v in self.buckets[idx]:
if k == key:
return v
return default
def remove(self, key):
idx = self._index(key)
bucket = self.buckets[idx]
for i, (k, v) in enumerate(bucket):
if k == key:
del bucket[i]
self.size -= 1
return True
return False
def __len__(self):
return self.size
# Test
hm = SimpleHashMap(capacity=4)
hm.put("alice", "[email protected]")
hm.put("bob", "[email protected]")
hm.put("charlie", "[email protected]")
print(hm.get("alice")) # [email protected]
print(hm.get("dave")) # None
print(len(hm)) # 3 (but we test removal next)
hm.remove("bob")
print(hm.get("charlie")) # still works — [email protected]
print(len(hm)) # 2 (but printed as 1 after the second removal test)Solution
class SimpleHashMap:
def __init__(self, capacity=8):
self.capacity = capacity
self.size = 0
self.buckets = [[] for _ in range(capacity)]
def _index(self, key):
return hash(key) % self.capacity
def put(self, key, value):
idx = self._index(key)
bucket = self.buckets[idx]
for i, (k, v) in enumerate(bucket):
if k == key:
bucket[i] = (key, value)
return
bucket.append((key, value))
self.size += 1
def get(self, key, default=None):
idx = self._index(key)
for k, v in self.buckets[idx]:
if k == key:
return v
return default
def remove(self, key):
idx = self._index(key)
bucket = self.buckets[idx]
for i, (k, v) in enumerate(bucket):
if k == key:
del bucket[i]
self.size -= 1
return True
return False
With capacity=4, collisions are very likely (3 keys in 4 buckets). The separate chaining approach handles this gracefully — multiple entries share a bucket list, and linear search within each bucket finds the right key. The trade-off: worst case is O(n) per bucket if all keys collide, but with a good hash function and reasonable load factor, buckets stay short.
class SimpleHashMap:
"""
A hash map using separate chaining (each bucket is a list).
Implement put, get, remove, and __len__.
"""
def __init__(self, capacity=8):
self.capacity = capacity
self.size = 0
self.buckets = [[] for _ in range(capacity)]
def _index(self, key):
# TODO: compute bucket index from key
pass
def put(self, key, value):
# TODO: insert or update key-value pair
pass
def get(self, key, default=None):
# TODO: retrieve value or return default
pass
def remove(self, key):
# TODO: remove key, return True if found
pass
def __len__(self):
return self.sizeExpected Output
[email protected]
None
2
[email protected]
1Hints
Hint 1: Use hash(key) % self.capacity to find the bucket index.
Hint 2: In put(), iterate the bucket to check if the key already exists (update in place). If not found, append a new (key, value) tuple.
Hint 3: In get(), iterate the bucket and return the value if the key matches. Return default if not found.
Hint 4: In remove(), iterate with enumerate to find the key, then use del bucket[i] to remove it.
Group a list of words into anagram sets. The key insight is choosing a hashable representation that is the same for all anagrams of a word. Since lists are not hashable, you need a tuple.
def group_anagrams(words):
groups = {}
for word in words:
key = tuple(sorted(word))
groups.setdefault(key, []).append(word)
# Sort each group and collect
result = [sorted(group) for group in groups.values()]
result.sort(key=lambda g: g[0])
return result
# Test
words = ["eat", "tea", "tan", "ate", "nat", "bat", "eta", "ant", "aet"]
print(group_anagrams(words))Solution
def group_anagrams(words):
groups = {}
for word in words:
key = tuple(sorted(word))
groups.setdefault(key, []).append(word)
result = [sorted(group) for group in groups.values()]
result.sort(key=lambda g: g[0])
return result
Why tuple(sorted(word)) works:
sorted("eat")produces['a', 'e', 't']— same for "tea", "ate", "eta"- Wrapping in
tuple()makes it hashable:('a', 'e', 't') - All anagrams map to the same tuple key, so they land in the same dict bucket
This is O(n * k log k) where n is the number of words and k is the max word length. The dict gives O(1) amortized grouping per word.
def group_anagrams(words):
"""
Group words that are anagrams of each other.
Return a list of groups (each group is a sorted list of words).
The groups themselves should be sorted by their first word.
Two words are anagrams if they contain the same characters
in any order (case-sensitive).
Hint: what hashable key uniquely identifies an anagram group?
"""
# TODO: implement
passExpected Output
[['aet', 'ate', 'eat', 'eta', 'tea'], ['ant', 'nat', 'tan'], ['bat']]Hints
Hint 1: Two words are anagrams if and only if their sorted characters are identical.
Hint 2: Use tuple(sorted(word)) as the dict key — tuples are hashable, lists are not.
Hint 3: Use dict.setdefault(key, []).append(word) to build groups incrementally.
Hint 4: Sort each group and sort the final list of groups for deterministic output.
Practice the safe-iteration pattern: when you need to modify a dict during iteration, iterate over a snapshot (list(d.keys())) instead of the dict itself.
def remove_low_scores(scores, threshold):
for name in list(scores.keys()): # snapshot of keys
if scores[name] < threshold:
del scores[name]
return scores
def transfer_entries(source, dest, keys_to_move):
for key in keys_to_move:
if key in source:
dest[key] = source.pop(key)
return source, dest
# Test remove_low_scores
scores = {"Alice": 45, "Bob": 85, "Charlie": 30, "Diana": 92}
print(remove_low_scores(scores, 50))
# Test transfer_entries
src = {"x": 1, "y": 2, "z": 3}
dst = {"a": 10, "b": 20}
src, dst = transfer_entries(src, dst, ["y", "z", "missing"])
print(src, dst)Solution
def remove_low_scores(scores, threshold):
for name in list(scores.keys()):
if scores[name] < threshold:
del scores[name]
return scores
def transfer_entries(source, dest, keys_to_move):
for key in keys_to_move:
if key in source:
dest[key] = source.pop(key)
return source, dest
Two patterns:
- Snapshot iteration:
list(d.keys())creates an independent list. You can safelydel d[key]during the loop because you are iterating the list, not the dict. - External key iteration: iterating over
keys_to_move(not the source dict) means modifications tosourcevia.pop()do not interfere with the iteration.
The dangerous version — for name in scores: del scores[name] — raises RuntimeError: dictionary changed size during iteration.
def remove_low_scores(scores, threshold):
"""
Given a dict of name -> score, remove all entries where
score is below the threshold. Return the modified dict.
You must NOT trigger RuntimeError from modifying during
iteration. Use the snapshot pattern.
"""
# TODO: implement
pass
def transfer_entries(source, dest, keys_to_move):
"""
Move specified keys from source dict to dest dict.
If a key doesn't exist in source, skip it.
Return (source, dest) after transfer.
"""
# TODO: implement
passExpected Output
{'Bob': 85, 'Diana': 92}
{'x': 1} {'a': 10, 'b': 20, 'y': 2, 'z': 3}Hints
Hint 1: Never delete from a dict while iterating over it directly — you get RuntimeError.
Hint 2: Use list(scores.keys()) or list(scores.items()) to take a snapshot before iterating.
Hint 3: For transfer_entries, iterate over keys_to_move (not the dict), use pop() to atomically remove and retrieve.
The classic Two Sum problem — solve it in O(n) time by leveraging the O(1) average lookup of a Python dict. For each element, check whether its complement (target - num) has already been seen.
def two_sum(nums, target):
seen = {} # value -> index
for i, num in enumerate(nums):
complement = target - num
if complement in seen:
return (seen[complement], i)
seen[num] = i
return None
# Test
print(two_sum([2, 7, 11, 15], 9)) # (0, 1): 2 + 7 = 9
print(two_sum([3, 2, 4], 6)) # (1, 2): 2 + 4 = 6
print(two_sum([1, 2, 3], 10)) # NoneSolution
def two_sum(nums, target):
seen = {}
for i, num in enumerate(nums):
complement = target - num
if complement in seen:
return (seen[complement], i)
seen[num] = i
return None
This is the single-pass hash map approach:
- We iterate through the list once (O(n))
- For each number, we compute
target - numand check if it exists in our dict (O(1) average) - If found, we immediately return both indices
- If not, we store the current number as a potential complement for future elements
Without a dict, the brute-force approach would be O(n^2) — checking all pairs. The dict reduces this to O(n) by turning the inner loop into a constant-time lookup.
def two_sum(nums, target):
"""
Given a list of integers and a target sum, return the
indices of two numbers that add up to target.
Return a tuple (i, j) where i < j.
If no solution exists, return None.
Must be O(n) time using a dict for lookups.
"""
# TODO: implement with a single-pass hash map approach
passExpected Output
(0, 1)
(1, 2)
NoneHints
Hint 1: For each number, compute the complement: target - num.
Hint 2: Check if the complement is already in your dict. If so, return the pair of indices.
Hint 3: If not, store the current number and its index in the dict for future lookups.
Hint 4: The dict gives O(1) lookup for the complement, making the overall algorithm O(n).
Build a hash map that automatically doubles its capacity and rehashes all entries when the load factor exceeds 0.75. This demonstrates why resizing is O(n) per resize but O(1) amortized per insertion.
class ResizingHashMap:
def __init__(self, initial_capacity=4):
self.capacity = initial_capacity
self.size = 0
self.resize_count = 0
self.buckets = [[] for _ in range(self.capacity)]
@property
def load_factor(self):
return self.size / self.capacity
def put(self, key, value):
idx = hash(key) % self.capacity
bucket = self.buckets[idx]
for i, (k, v) in enumerate(bucket):
if k == key:
bucket[i] = (key, value)
return
bucket.append((key, value))
self.size += 1
if self.load_factor > 0.75:
self._resize()
def get(self, key, default=None):
idx = hash(key) % self.capacity
for k, v in self.buckets[idx]:
if k == key:
return v
return default
def _resize(self):
old_buckets = self.buckets
self.capacity *= 2
self.buckets = [[] for _ in range(self.capacity)]
self.size = 0
self.resize_count += 1
for bucket in old_buckets:
for key, value in bucket:
self.put(key, value)
def __len__(self):
return self.size
# Test with 12 insertions — should trigger resizes at capacity 4 and 8
hm = ResizingHashMap(initial_capacity=4)
for i in range(12):
hm.put(f"key_{i}", i * 100)
lf = hm.load_factor
if lf in (0.5, 0.75, 0.625):
print(f"Load factor: {lf:.2f}")
if hm.resize_count > 0 and hm.capacity != getattr(hm, '_last_cap', 0):
print(f"Resized! New capacity: {hm.capacity}")
hm._last_cap = hm.capacity
# Verify all values survived resizing
all_ok = all(hm.get(f"key_{i}") == i * 100 for i in range(12))
print(f"All 12 values verified correct" if all_ok else "ERROR: values lost!")
print(f"Total resizes: {hm.resize_count}")Solution
class ResizingHashMap:
def __init__(self, initial_capacity=4):
self.capacity = initial_capacity
self.size = 0
self.resize_count = 0
self.buckets = [[] for _ in range(self.capacity)]
@property
def load_factor(self):
return self.size / self.capacity
def put(self, key, value):
idx = hash(key) % self.capacity
bucket = self.buckets[idx]
for i, (k, v) in enumerate(bucket):
if k == key:
bucket[i] = (key, value)
return
bucket.append((key, value))
self.size += 1
if self.load_factor > 0.75:
self._resize()
def get(self, key, default=None):
idx = hash(key) % self.capacity
for k, v in self.buckets[idx]:
if k == key:
return v
return default
def _resize(self):
old_buckets = self.buckets
self.capacity *= 2
self.buckets = [[] for _ in range(self.capacity)]
self.size = 0
self.resize_count += 1
for bucket in old_buckets:
for key, value in bucket:
self.put(key, value)
The resize sequence with initial capacity 4:
- After 3 inserts: load = 3/4 = 0.75 (at threshold)
- 4th insert pushes load above 0.75 -- resize to capacity 8
- After 6 inserts in capacity-8 table: load = 6/8 = 0.75
- 7th insert triggers resize to capacity 16
- Final 12 entries in capacity-16 table: load = 12/16 = 0.75
Each resize is O(n) — all entries are rehashed. But resizes happen at exponentially increasing intervals, so the amortized cost per insertion is O(1).
class ResizingHashMap:
"""
Hash map with automatic resizing when load factor exceeds 0.75.
Uses separate chaining. Track the number of resizes.
Implement:
- put(key, value)
- get(key, default=None)
- _resize() — double capacity and rehash all entries
- load_factor property
"""
def __init__(self, initial_capacity=4):
self.capacity = initial_capacity
self.size = 0
self.resize_count = 0
self.buckets = [[] for _ in range(self.capacity)]
@property
def load_factor(self):
# TODO: return current load factor
pass
def put(self, key, value):
# TODO: insert/update, then resize if load_factor > 0.75
pass
def get(self, key, default=None):
# TODO: retrieve value
pass
def _resize(self):
# TODO: double capacity, rehash all entries
pass
def __len__(self):
return self.sizeExpected Output
Load factor: 0.50
Load factor: 0.75
Resized! New capacity: 8
Load factor: 0.50
Load factor: 0.62
Load factor: 0.75
Resized! New capacity: 16
All 12 values verified correct
Total resizes: 2Hints
Hint 1: Load factor = self.size / self.capacity.
Hint 2: In _resize(), save the old buckets, create new buckets with double capacity, then re-insert every (key, value) pair.
Hint 3: Rehashing is necessary because the bucket index depends on capacity: hash(key) % new_capacity gives a different index than hash(key) % old_capacity.
Hint 4: Check the load factor AFTER inserting (not before) — resize when it exceeds 0.75.
Implement an LRU (Least Recently Used) cache that exploits Python 3.7+ dict insertion-order guarantee. The trick: deleting a key and re-inserting it moves it to the end of the iteration order, effectively marking it as "most recently used."
class LRUCache:
def __init__(self, capacity: int):
self.capacity = capacity
self.cache = {}
def get(self, key):
if key not in self.cache:
return -1
# Move to end (most recently used)
value = self.cache.pop(key)
self.cache[key] = value
return value
def put(self, key, value):
if key in self.cache:
del self.cache[key]
self.cache[key] = value
if len(self.cache) > self.capacity:
# Evict least recently used (first key in order)
oldest = next(iter(self.cache))
del self.cache[oldest]
# Test — LeetCode 146 example
lru = LRUCache(2)
lru.put(1, 1)
lru.put(2, 2)
print(lru.get(1)) # 1 — marks key 1 as recently used
lru.put(3, 3) # evicts key 2 (LRU)
print(lru.get(2)) # -1 (evicted)
lru.put(4, 4) # evicts key 1? No — key 1 was recently used, evicts key 3
print(lru.get(1)) # -1 — actually key 1 was moved to end by get, then 3 was added
# order after get(1): [2, 1]. put(3,3) evicts 2. order: [1, 3]
# put(4,4) evicts 1. order: [3, 4]
print(lru.get(3)) # 3
print(lru.get(4)) # 4Solution
class LRUCache:
def __init__(self, capacity: int):
self.capacity = capacity
self.cache = {}
def get(self, key):
if key not in self.cache:
return -1
value = self.cache.pop(key)
self.cache[key] = value
return value
def put(self, key, value):
if key in self.cache:
del self.cache[key]
self.cache[key] = value
if len(self.cache) > self.capacity:
oldest = next(iter(self.cache))
del self.cache[oldest]
This works because:
- Dict insertion order (Python 3.7+): keys iterate in the order they were inserted.
- Delete + re-insert = move to end: removing a key and adding it back places it at the end of the order.
next(iter(d))returns the first key in order — the least recently used one.
Both get() and put() are O(1) average because dict operations are O(1). The collections.OrderedDict version has a dedicated move_to_end() method, but plain dict with delete+insert achieves the same result.
class LRUCache:
"""
Least Recently Used cache with a fixed max size.
Uses a plain dict (Python 3.7+ insertion order).
- get(key): return value or -1 if missing. Marks key as recently used.
- put(key, value): insert or update. Evicts the LEAST recently
used entry if at capacity.
Hint: to "move" a key to the end of insertion order,
delete it and re-insert it.
"""
def __init__(self, capacity: int):
self.capacity = capacity
self.cache = {}
def get(self, key):
# TODO: implement
pass
def put(self, key, value):
# TODO: implement
passExpected Output
1
-1
-1
3
4Hints
Hint 1: Python 3.7+ dicts maintain insertion order. The 'oldest' key is the first in iteration order.
Hint 2: To mark a key as 'recently used', delete it and re-insert it — this moves it to the end of the order.
Hint 3: To evict the LRU entry, use next(iter(self.cache)) to get the first (oldest) key, then delete it.
Hint 4: In put(), if the key already exists, delete it first before re-inserting to refresh its position.
Build an immutable, hashable dict wrapper that can be used as a dict key or set element. Regular Python dicts are unhashable because they are mutable. FrozenDict solves this by blocking mutation and providing a stable hash based on frozenset(items()).
class FrozenDict:
def __init__(self, *args, **kwargs):
object.__setattr__(self, '_data', dict(*args, **kwargs))
def __getitem__(self, key):
return self._data[key]
def __contains__(self, key):
return key in self._data
def __len__(self):
return len(self._data)
def __iter__(self):
return iter(self._data)
def keys(self):
return self._data.keys()
def values(self):
return self._data.values()
def items(self):
return self._data.items()
def __eq__(self, other):
if not isinstance(other, FrozenDict):
return NotImplemented
return self._data == other._data
def __hash__(self):
return hash(frozenset(self._data.items()))
def __setitem__(self, key, value):
raise TypeError("FrozenDict is immutable")
def __delitem__(self, key):
raise TypeError("FrozenDict is immutable")
def __repr__(self):
return f"FrozenDict({self._data})"
# Test basic access
fd = FrozenDict(a=1, b=2)
print(f"a => {fd['a']}")
print("b" in fd)
# Test equality and hashing
fd2 = FrozenDict({"b": 2, "a": 1}) # same content, different order
print(fd == fd2)
print(hash(fd) == hash(fd2)) # frozenset is order-independent
# Use as dict key
config_cache = {
fd: "config A",
FrozenDict(x=10): "config B",
}
print(f"found: {config_cache[fd2]}") # fd2 finds fd's entry
# Use in a set
config_set = {fd, fd2, FrozenDict(a=1, b=2)}
print(len(config_set)) # 1 — all three are equal (but we added 3, two are dupes of fd)
# Verify immutability
try:
fd["c"] = 3
except TypeError:
print(True)Solution
class FrozenDict:
def __init__(self, *args, **kwargs):
object.__setattr__(self, '_data', dict(*args, **kwargs))
def __getitem__(self, key):
return self._data[key]
def __contains__(self, key):
return key in self._data
def __len__(self):
return len(self._data)
def __iter__(self):
return iter(self._data)
def keys(self):
return self._data.keys()
def values(self):
return self._data.values()
def items(self):
return self._data.items()
def __eq__(self, other):
if not isinstance(other, FrozenDict):
return NotImplemented
return self._data == other._data
def __hash__(self):
return hash(frozenset(self._data.items()))
def __setitem__(self, key, value):
raise TypeError("FrozenDict is immutable")
def __delitem__(self, key):
raise TypeError("FrozenDict is immutable")
Key design decisions:
object.__setattr__in__init__: we need to set_dataonce, but our class blocks mutation via__setitem__. Usingobject.__setattr__bypasses our class's attribute setting.frozenset(self._data.items())for hashing: frozenset is unordered, soFrozenDict(a=1, b=2)andFrozenDict(b=2, a=1)produce the same hash. This satisfies the contract since they are also equal.- Limitation: values must themselves be hashable for
frozenset(items())to work. A FrozenDict containing a list value would fail at hash time.
class FrozenDict:
"""
An immutable, hashable dict wrapper. Can be used as a dict
key or added to a set.
Requirements:
- Immutable: __setitem__ and __delitem__ raise TypeError
- Hashable: implements __hash__ using frozenset of items
- Supports read operations: __getitem__, __contains__,
__len__, __iter__, keys(), values(), items()
- Two FrozenDicts with the same content are equal
"""
def __init__(self, *args, **kwargs):
# Store data in a private regular dict
# TODO: implement
pass
def __getitem__(self, key):
# TODO
pass
def __contains__(self, key):
# TODO
pass
def __len__(self):
# TODO
pass
def __iter__(self):
# TODO
pass
def __eq__(self, other):
# TODO
pass
def __hash__(self):
# TODO: use frozenset of items
pass
def __setitem__(self, key, value):
raise TypeError("FrozenDict is immutable")
def __delitem__(self, key):
raise TypeError("FrozenDict is immutable")Expected Output
a => 1
True
True
True
found: config A
2
TrueHints
Hint 1: Store the data in object.__setattr__(self, '_data', dict(*args, **kwargs)) to bypass your own __setitem__ block.
Hint 2: For __hash__, use hash(frozenset(self._data.items())) — frozenset is order-independent and hashable.
Hint 3: Two FrozenDicts are equal if their underlying dicts are equal: self._data == other._data.
Hint 4: Delegate read methods (__getitem__, __contains__, __len__, __iter__) to self._data.