Implement in-memory KV store with serialization

Quick Overview

This question evaluates skills in designing and implementing an in-memory key-value store with serialization, testing data structure design, API design (set/get/serialize/deserialize), serialization format selection, type fidelity for common Python types, and robust error handling.

Company: OpenAI

Role: Software Engineer

Category: Coding & Algorithms

Difficulty: medium

Interview Round: Technical Screen

Implement an in-memory key-value store in Python that supports setting and retrieving values and can serialize and deserialize the entire store. Define a clear API (e.g., set(key, value), get(key), serialize(), deserialize(blob)). Choose a serialization format (e.g., JSON or pickle), explain your choice, and ensure type fidelity for common Python types (ints, floats, strings, lists, dicts). Handle missing keys and malformed or incompatible serialized input gracefully. Provide basic tests to demonstrate that data round-trips correctly.

Overview: This question evaluates skills in designing and implementing an in-memory key-value store with serialization, testing data structure design, API design (set/get/serialize/deserialize), serialization format selection, type fidelity for common Python types, and robust error handling.

Implement a function `solution(operations)` that simulates a small **in-memory key-value store** with a typed, JSON-backed serialization API. The store supports four operations: `set`, `get`, `serialize`, and `deserialize`. JSON is used as the serialization format because it is human-readable, portable, and safer than `pickle`. To preserve type fidelity across a serialize/deserialize round-trip, the store only accepts values built from a restricted set of types. ## What to implement `operations` is a list of operations to apply **in order**, starting from an empty store. Each operation is a sequence (e.g. a tuple) whose **first element is the command name** and whose remaining elements are that command's arguments. Return a **list with exactly one result per operation**, in the same order. ## Supported values A value is **supported** if it is one of the following (checked recursively): - an `int` - a **finite** `float` (i.e. not `NaN`, `inf`, or `-inf`) - a `str` - a `list` whose every element is supported - a `dict` whose **every key is a `str`** and whose every value is supported `bool` and `None` are **not** supported values (note that in Python `True`/`False` are `int` instances, so they must be rejected explicitly). ## Operations **`('set', key, value)`** - If `key` is a `str` **and** `value` is supported, store the value under `key` (overwriting any existing entry) and append `True`. - Otherwise append `False` and leave the store **unchanged**. **`('get', key)`** - Append the value currently stored under `key`, or `None` if the key is not present. **`('serialize',)`** - Append a **compact JSON string** of the entire store, with **keys sorted lexicographically** and no extra whitespace (use `,` and `:` as separators). Non-finite floats are never produced. The serialization of an empty store is `"{}"`. **`('deserialize', blob)`** - `blob` must be a `str` containing JSON that parses to an **object representing the whole store**. - If `blob` is a string, parses successfully as JSON, the parsed result is a `dict`, **and** that dict is supported, then **replace the entire store** with it and append `True`. - Otherwise (non-string `blob`, malformed JSON, a parsed value that is not a `dict`, or a dict containing unsupported values) append `False` and leave the store **unchanged**. ## Edge cases - Any operation whose command is unrecognized, whose argument count is wrong, or that is empty appends `False` — **except** a `get` with the wrong argument count, which appends `None`. - An empty `operations` list returns an empty list. ## Constraints - `0 <= len(operations) <= 10^4` - Store keys and all nested dict keys must be strings. - Supported stored values are `int`, finite `float`, `str`, `list`, and `dict`, with recursive nesting allowed. - The total size of all values and serialized blobs processed is at most `2 * 10^5`. ## Example ``` operations = [ ('set', 'count', 5), ('set', 'info', {'name': 'Ada', 'scores': [1, 2.5]}), ('serialize',), ('deserialize', '{"count":5,"info":{"name":"Ada","scores":[1,2.5]}}'), ('get', 'info'), ] # returns: # [True, # True, # '{"count":5,"info":{"name":"Ada","scores":[1,2.5]}}', # True, # {'name': 'Ada', 'scores': [1, 2.5]}] ```

Constraints

0 <= len(operations) <= 10^4
Store keys and all nested dict keys must be strings
Supported stored values are int, finite float, str, list, and dict with recursive nesting
The total size of all values and serialized blobs processed is at most 2 * 10^5

Examples

Input: [('set', 'count', 5), ('set', 'info', {'name': 'Ada', 'scores': [1, 2.5]}), ('serialize',), ('deserialize', '{"count":5,"info":{"name":"Ada","scores":[1,2.5]}}'), ('get', 'info')]

Expected Output: [True, True, '{"count":5,"info":{"name":"Ada","scores":[1,2.5]}}', True, {'name': 'Ada', 'scores': [1, 2.5]}]

Explanation: Two values are stored, the whole store is serialized to deterministic JSON, deserialized back, and the nested object is retrieved unchanged.

Input: [('set', 'x', [1, 2, 3]), ('get', 'missing'), ('deserialize', '{"x":[1,2,3]'), ('get', 'x')]

Expected Output: [True, None, False, [1, 2, 3]]

Explanation: Getting a missing key returns None. The malformed JSON blob fails to deserialize, so the previous store remains intact.

Hints

Use a normal dictionary for the live store, and write one recursive helper that validates whether a value can be safely serialized without losing type information.
Make serialization deterministic by sorting keys and removing extra whitespace, so exact string comparisons in tests are stable.

Approach

The solution simulates a typed key-value store by interpreting a list of operations, appending one result per operation.

Core data structure. A plain Python dict named store holds the data. The whole solution hinges on one validation helper:

is_supported(value) recursively checks that a value is one of the allowed types. The ordering matters:

bool and None are rejected first (note True/False are int subclasses in Python, so they must be excluded before the int check).
int and str are always accepted.
float is accepted only when math.isfinite (blocks NaN/inf, which JSON can't round-trip safely).
list recurses into every element; dict requires every key to be a str and every value to pass is_supported.

Operation dispatch. For each op, the first element is the command. Each branch also length-checks the tuple defensively:

set -> requires a str key and a supported value; stores and returns True, else False (store unchanged).
get -> returns store.get(key), yielding None for a missing key.
serialize -> json.dumps(store, sort_keys=True, separators=(',',':'), allow_nan=False) produces a compact, key-sorted, deterministic blob.
deserialize -> rejects non-strings, try/except guards malformed JSON, then accepts only when the parsed result is a dict that passes is_supported. On success it replaces store wholesale; otherwise leaves it untouched.

Why it's correct. Validation is enforced on both ingress paths (set and deserialize), so the store always holds only round-trippable values. Malformed input is caught by try/except and the dict-type check, guaranteeing the "store unchanged on failure" contract.

Time complexity:

O(S), where S is the total size (element/character count) of all values and JSON blobs processed across operations. Each `is_supported` validation, `json.dumps`, and `json.loads` touches each element/character a constant number of times.

Space complexity:

O(S) — the store plus any parsed JSON object hold up to S elements, and `is_supported` recursion depth is bounded by the nesting depth of the value (at most O(S)).