Quick Overview

This question evaluates competency in implementing an in-memory key-value store with persistence, covering concepts such as serialization, durability, data structure management, and basic I/O handling.

Implement persistent key-value store

Company: OpenAI

Role: Software Engineer

Category: Coding & Algorithms

Difficulty: medium

Interview Round: Technical Screen

##### Question Design and implement an in-memory key-value store supporting set(key, value), get(key), shutdown() that flushes all data as bytes to a medium, and restore() that reloads the data from the medium.

Quick Answer: This question evaluates competency in implementing an in-memory key-value store with persistence, covering concepts such as serialization, durability, data structure management, and basic I/O handling.

Implement a persistent in-memory key-value store and simulate it over a sequence of operations. The store supports four commands: - ('set', key, value): store or update a string value for a string key in memory. - ('get', key): read the current in-memory value for the key, or None if the key does not exist. - ('shutdown',): write the entire current store to a byte medium, then clear the in-memory store. - ('restore',): rebuild the in-memory store from the most recent byte snapshot. If no snapshot exists yet, the store becomes empty. Keys and values may contain any characters, including separators like ':' or '|', and may even be empty strings. Because of that, a safe byte encoding is required; delimiter-based serialization is not reliable. For this problem, write a function that processes all operations in order and returns the results of every 'get' operation.

Constraints

  • 0 <= len(operations) <= 100000
  • Keys and values are strings and may be empty
  • The total UTF-8 byte length of all keys and values involved in the processed snapshots is at most 10^6
  • Average O(1) lookup/update is expected for set/get

Examples

Input: [('set', 'a', '1'), ('set', 'b', '2'), ('get', 'a'), ('shutdown',), ('get', 'a'), ('restore',), ('get', 'b'), ('get', 'a')]

Expected Output: ['1', None, '2', '1']

Explanation: After shutdown the in-memory store is cleared, so 'a' is missing until restore reloads the saved snapshot.

Input: [('set', 'x', 'old'), ('set', 'x', 'new'), ('shutdown',), ('restore',), ('get', 'x'), ('set', 'y', '3'), ('shutdown',), ('get', 'y'), ('restore',), ('get', 'y'), ('get', 'x')]

Expected Output: ['new', None, '3', 'new']

Explanation: The second set overwrites 'x'. The second shutdown saves a new snapshot containing both 'x' and 'y'.

Hints

  1. A plain delimiter like ':' is unsafe because keys or values can contain it. Prefix each encoded string with its byte length instead.
  2. Treat shutdown as writing a full snapshot and clearing memory. restore should replace the current in-memory map with the last saved snapshot, not merge with it.

Loading coding console...