Quick 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.

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

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

Loading coding console...

Show the approach

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.