Implement Hash Map Operations
Company: TikTok
Role: Backend Software Engineer
Category: Coding & Algorithms
Difficulty: medium
Interview Round: Onsite
# Implement Hash Map Operations
Implement `process_hash_map(operations)` without using a built-in hash-map or dictionary type for storage.
Each operation is one of these strings:
- `"PUT key value"`: insert `key` with `value`, or replace the existing value.
- `"GET key"`: append the current value for `key` to the result, or append `-1` when the key is absent.
- `"REMOVE key"`: remove `key` if present; otherwise do nothing.
Return all `GET` results in operation order. The explicit operation grammar is a pedagogical assumption for the source's named hash-map design task.
## Function Contract
`process_hash_map(operations: list[str]) -> list[int]`
## Constraints
- `0 <= len(operations) <= 200000`
- `0 <= key <= 1000000`
- `0 <= value <= 10^9`
- `-1` is reserved to represent a missing key and is never supplied as a value.
- Every operation follows one of the three formats above.
## Examples
### Example 1
```text
Input: ["PUT 1 8", "PUT 2 5", "GET 1", "GET 3", "PUT 2 9", "GET 2"]
Output: [8, -1, 9]
```
The second put for key `2` replaces its earlier value.
### Example 2
```text
Input: ["PUT 4 0", "REMOVE 4", "GET 4", "REMOVE 4", "PUT 4 7", "GET 4"]
Output: [-1, 7]
```
Removing a missing key is a no-op, and a later insertion of the same key succeeds.
Overview: Build a hash map behind a deterministic operation stream with insertion, replacement, lookup, removal, and missing-key behavior. The specification avoids built-in map storage and fixes return ordering and value bounds for a future portable console implementation.
Read the full TikTok Backend Software Engineer interview experience this question came from
Implement process_hash_map(operations) without using a built-in hash-map or dictionary type for storage. Every string operation is exactly "PUT key value", "GET key", or "REMOVE key". PUT inserts or replaces; GET appends the current value or -1 if absent; REMOVE deletes a present key and otherwise does nothing. Return all GET results in operation order. The operation grammar is the source's explicit pedagogical assumption.
Constraints
- 0 <= operations.length <= 200,000
- Every operation is exactly "PUT key value", "GET key", or "REMOVE key".
- 0 <= key <= 1,000,000
- 0 <= value <= 10^9
- -1 is reserved for a missing key and is never supplied as a value.
- No built-in hash-map or dictionary type may be used for storage.
Examples
Input: (['PUT 1 8', 'PUT 2 5', 'GET 1', 'GET 3', 'PUT 2 9', 'GET 2'],)
Expected Output: [8, -1, 9]
Explanation: The first source example checks insertion, a miss, and replacement.
Input: (['PUT 4 0', 'REMOVE 4', 'GET 4', 'REMOVE 4', 'PUT 4 7', 'GET 4'],)
Expected Output: [-1, 7]
Explanation: The second source example checks removal, a missing removal, and reinsertion.
Hints
- The finite key bound can itself supply a collision-free bucket index.
- Use the reserved -1 value to represent an empty slot.