Build a Hash-Table Key-Value Store Without Built-in Dictionaries or Sets

In a 45-minute technical screen for a software engineer role, which the candidate had been told would be a debugging session, the interviewer instead asked for an implementation from scratch: implement a key-value store without using the language's built-in dictionary (hash map) or set types. The source reports only that one-line task and the interviewer's follow-up points, so the interface below is the standard implied one and the method names are illustrative. Write a class that supports: - `put(key, value)`: store `value` under `key`, overwriting any value already stored for that key; - `get(key)`: return the value stored under `key`; - `remove(key)`: delete `key` and its value. The follow-up discussion focused on collisions, meaning two different keys that map to the same position in your underlying storage. The interviewer made these expectations clear: - The store should be written as a class, starting from the class definition, rather than as loose functions over shared data. - Collisions must be resolved inside the store. Raising an exception on a collision and leaving callers to deal with it was judged a poor design. Raising an error when a caller asks for a key that does not exist was acceptable. - Operations are expected to run in O(1) time. When separate chaining was proposed, the interviewer objected that it would not be O(1), so be ready to state precisely whether your claim is about the average, amortized or worst case, and to defend it. ```hint Start from a plain array Work out what raw storage you are still allowed to use, and how a key of any type becomes a position in it. ``` ```hint Where the second key goes When a key's position is already held by a different key, decide where that key goes instead so that a later lookup can retrace the same path, then check what that path looks like after a removal. ``` ### Constraints and Clarifications - Built-in dictionaries, sets, and any library map or set type built on them are off limits. A plain array, such as a Python list created with a fixed length, is assumed to be allowed as raw storage. - Keys are compared by equality. The value stored under a key can be anything. ### Clarifying Questions - What types can keys be, and may I call the language's built-in hash function, or must I write a hash function myself? - Is the number of keys known in advance, or must the store grow as keys are added? - When you say O(1), do you mean the expected time per operation, the amortized time including resizing, or the worst case? - May each slot of the array hold a nested list of entries, or should every slot hold at most one entry? - What should `get` and `remove` do for a missing key: raise an error, or return a sentinel value? - Will the store be used from more than one thread? ### What a Strong Answer Covers - A class with a clear interface and defined behavior for overwrites and missing keys - How keys are mapped to slots, and a collision-resolution strategy kept entirely inside the class - Deletion semantics and how they interact with the collision strategy - Load factor management and resizing, with the amortized cost explained - Precise average-case and worst-case complexity claims, and a reasoned comparison with the alternative strategy - Tests that force collisions, overwrites, removals and growth ### Follow-up Questions - The interviewer says separate chaining is not O(1). How do you respond, and what does your own strategy guarantee in the worst case? - An attacker chooses keys that all land in the same slot. What happens to your store, and how would you defend against it? - What would it take to guarantee that `get` inspects at most a constant number of slots, even in the worst case? - How would you make the store safe for concurrent readers and writers?