Implement a Key-Value Map from Scratch Without Built-in Dictionaries

Implement a map (a key-value store) from scratch, without using the language's built-in dictionary, hash map or tree map types. It must support: - `put(key, value)`: insert the key, or replace its value if the key is already present; - `get(key)`: return the value stored for the key; - `remove(key)`: delete the key if it is present; - `size()`: return the number of keys stored. Before coding, lay out the implementation options and their trade-offs and agree on one with the interviewer; then implement it and extend it through the follow-up questions. ```python class MyMap: def put(self, key, value) -> None: ... def get(self, key): ... def remove(self, key) -> bool: ... def size(self) -> int: ... ``` ```hint Two keys, one slot However you place keys, two different keys will sometimes want the same place. Decide how a lookup and a removal still find exactly the right key afterwards. ``` ```hint Keep the average cost flat Decide when the structure should grow and what growing costs, then check that the average cost of an insert stays constant over a long run of inserts. ``` ### Constraints and Clarifications - The method names and signatures above are illustrative; agree on them with the interviewer. - Arrays (lists) are allowed; built-in dictionaries, sets and maps are not. ### Clarifying Questions - What types can keys be (integers, strings, any hashable object), and can a key be null? - What should `get` do for a missing key: return a default, or raise an error? - Is ordered iteration needed (sorted by key, or in insertion order), or only lookups? - May you use the language's built-in hash function for keys, or should you write one? - Roughly how many keys will the map hold, and does memory matter more than speed? - Will several threads use the map at the same time? ### What a Strong Answer Covers - Lays out the options (separate chaining, open addressing, a balanced search tree) with their costs and when each fits, and picks one for stated reasons - Correct put, get, remove and size, including updating an existing key without changing the size and removing a missing key - Collision handling, mapping a hash to a slot, and a load-factor-triggered resize that rehashes every key, with the amortized analysis - Worst-case behaviour when keys collide, and how real implementations bound it - Tests for collisions, updates, removals and the resize boundary ### Follow-up Questions - With open addressing and linear probing, why can't `remove` simply empty the slot? What do you do instead? - Add iteration in insertion order, or in sorted key order. What changes, and what does each cost? - Make the map safe for many concurrent readers and writers. What happens during a resize? - An attacker chooses the keys and makes them all collide. What happens to performance, and how do you defend against it?