Implement a dictionary without built-in Dictionary
Company: Snapchat
Role: Software Engineer
Category: Coding & Algorithms
Difficulty: hard
Interview Round: Onsite
Implement a key-value map type (a “dictionary” / hash map) **from scratch**, without using the language’s built-in dictionary/map as the underlying storage.
## Requirements
- Support at least:
- `put(key, value)`
- `get(key) -> value | null`
- `remove(key)`
- Keys are hashable.
- Handle hash collisions correctly.
- Discuss or implement resizing/rehashing to keep operations efficient.
## Constraints / Goals
- Aim for `O(1)` average time per operation.
- You may use arrays/lists as the underlying storage, but not a built-in associative container.
## Follow-ups
- Compare separate chaining vs open addressing.
- How would you design this as a generic type (e.g., in Swift: `Key: Hashable`)?
Quick Answer: This question evaluates understanding of hash tables and low-level data-structure implementation, including hashing, collision resolution, resizing/rehashing, and performance guarantees for put/get/remove operations.
Simulate put/get/remove operations for a key-value map. Return outputs, with None for mutating operations and missing gets.
Constraints
- Inputs are Python literals matching the function signature.
- Return a deterministic exact-match value.
Examples
Input: ([['put','a',1],['put','b',2],['get','a'],['remove','a'],['get','a']],)
Expected Output: [None, None, 1, None, None]
Explanation: Basic map operations.
Input: ([['get','x'],['put','x',3],['put','x',4],['get','x']],)
Expected Output: [None, None, None, 4]
Explanation: Update existing key.
Hints
- Use deterministic tie-breaking for prompts with multiple valid outputs.
- For design-style APIs, simulate operations with explicit inputs.