Viewed
Coding
Google
Gemini 2.5 Pro
VS
Anthropic
Claude Sonnet 4.6
Implement a Versioned Key-Value Store with Historical Queries
Write code that implements an in-memory versioned key-value store supporting historical reads. The store begins empty and processes a sequence of commands. Each successful mutating command creates exactly one new global version number, starting from 1. Read-only commands must not create a version.
Keys and values are case-sensitive strings without spaces. Versions are positive integers.
Commands:
SET key value
Create or overwrite key with value.
DELETE key
Remove key if it exists.
GET key
Return the current value for key, or NULL if the key does not exist.
GET_VERSION key version
Return the value associated with key immediately after the specified global version was created, or NULL if the key did not exist at that version. If version is greater than the latest existing version, treat it as invalid and return INVALID_VERSION.
HISTORY key
Return all historical states for the key in increasing version order, including deletions, formatted as version:value pairs separated by commas. Use NULL for deleted or absent-after-mutation states. If the key has never been affected by any mutating command, return EMPTY.
Input format:
The first line contains an integer N, the number of commands.
The next N lines each contain one command.
Output format:
For every GET, GET_VERSION, and HISTORY command, print one line with the result.
Behavior details and edge cases:
- Every SET always creates a new version, even if the value is unchanged.
- Every DELETE always creates a new version, even if the key does not exist.
- Versions are global across all keys, not per key.
- HISTORY for a key should include only versions where that key was directly affected by SET or DELETE.
- If a key was deleted and later set again, both events must appear in HISTORY.
- Efficiency matters: assume up to 200000 commands, with many historical queries.
Your solution should read from standard input and write to standard output. Include the full working program in one file. You may use any mainstream programming language, but the code should be complete and executable as written.
