Katkat
Back

Process Operations for an In-Memory Key-Value Store

RbcroyalbankMachine Learning Engineer · Technical Screen
MediumMachine Learning EngineerTechnical ScreenCoding & Algorithms

Last updated

This problem tests proficiency with hash map operations and handling data retrieval edge cases within an in-memory data store.

Problem Statement

Design an in-memory Key-Value store that supports basic operations via a command stream. You are given a list of operations, where each operation is represented as a list of strings: ["SET", "key", "value"], ["GET", "key"], or ["DELETE", "key"].

Requirements:

  • SET key value: Store the value associated with the key. If the key already exists, overwrite the previous value.
  • GET key: Return the value associated with the key. If the key does not exist, return the string "null".
  • DELETE key: Remove the key and its associated value from the store. If the key does not exist, do nothing.

Implement the function process_operations(operations) that takes a list of operations and returns a list of results for all GET operations encountered.

Constraints:

  • Number of operations: up to 10^5.
  • Keys and values are non-empty strings.
  • Average time complexity per operation should be O(1).

Examples:

# Example 1
ops = [["SET", "a", "1"], ["GET", "a"], ["DELETE", "a"], ["GET", "a"]]
# Output: ["1", "null"]

# Example 2
ops = [["SET", "x", "10"], ["SET", "x", "20"], ["GET", "x"]]
# Output: ["20"]

Edge Cases:

  • GET on a key that was just deleted.
  • DELETE on a key that never existed.
  • SET operations on existing keys with different values.

Hints

Hint 1

Use a hash map (dictionary in Python) to store the key-value pairs for O(1) average lookup and insertion.

Hint 2

For the GET operation, ensure you check for the key's existence in the map before returning the value.

Hint 3

Iterate through the list of operations once, updating the state of your hash map and appending results to a list whenever a GET command is executed.

Follow-up questions

  • How would you modify your implementation to support a 'GET_ALL' command that returns all current keys in lexicographical order?
  • If this store needs to support millions of operations per second in a multi-threaded environment, what synchronization primitives would you use to ensure thread safety?
  • How would you extend this system to include an 'EXPIRE key seconds' command, where the key is automatically deleted after the specified time?