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

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

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.

Implement Hash Map Operations

Hints

1. The finite key bound can itself supply a collision-free bucket index.
2. Use the reserved -1 value to represent an empty slot.

Approach

The bounded nonnegative key domain permits an identity hash function with direct addressing. Allocate one integer slot for every possible key and initialize every slot to -1, the reserved missing sentinel. PUT writes the value, GET reads the slot, and REMOVE restores -1. This uses no built-in map or dictionary and avoids collisions because each allowed key has its own slot.

• Time complexity: O(1,000,001 + m) time for initialization and m operations; every operation itself is O(1).
• Space complexity: O(1,000,001 + g), including the direct-address table and g returned GET results.