Implement a hash table with put/get
Company: Paradromics
Role: Software Engineer
Category: Coding & Algorithms
Difficulty: medium
Interview Round: Technical Screen
## Problem
Implement a simplified hash table (hash map) data structure from scratch.
### Required API
Design a class `HashTable` with:
- `HashTable(int numBuckets)` (constructor): initialize internal storage with a fixed number of buckets.
- `void put(K key, V value)`: insert a key/value pair. If the key already exists, overwrite its value.
- `V get(K key)`: return the value for `key`, or a sentinel (e.g., `null` / `-1`) if the key is not present.
**Note:** `delete/remove` is *not* required.
### Assumptions / Constraints
- You may assume keys are non-null.
- You must handle hash collisions correctly.
- Target average time complexity: `O(1)` for `put` and `get` (amortized/expected).
- You may not use a built-in hash map/dictionary.
### Follow-up discussion (conceptual)
1. What makes a hash function “good,” and how does key distribution affect performance?
2. How does the choice of `numBuckets` (and the load factor) impact collisions and runtime?
3. Compare common collision-resolution strategies:
- Separate chaining (buckets)
- Open addressing (e.g., linear/quadratic probing, double hashing)
4. If using open addressing, describe how probing (“hopping”) works and what pitfalls it introduces (e.g., clustering, tombstones).
Quick Answer: This question evaluates implementation and design skills for hash-based data structures, testing competency in data structures, hashing, collision handling, and achieving expected O(1) put/get performance in the Coding & Algorithms domain.
Implement fixed-bucket separate chaining for put/get operations without using a built-in dictionary for storage. Return get outputs.
Constraints
- Inputs are Python literals matching the function signature.
- Return a deterministic exact-match value.
Examples
Input: (2, [["put","a",1],["put","b",2],["get","a"],["get","c"]])
Expected Output: [1, None]
Explanation: Put and get values with missing returning None.
Input: (1, [["put","a",1],["put","b",2],["get","a"],["get","b"],["put","a",3],["get","a"]])
Expected Output: [1, 2, 3]
Explanation: A single bucket forces collision handling and update.
Hints
- Use a list for each bucket.
- Scan a bucket to update or find a key.