In-Memory Database with TTL and Historical Lookup

Level 4 - Current level
Instructions
Your task is to implement a simplified version of an in-memory database. All operations that should be supported by this database are described below.
Solving this task consists of several levels. Subsequent levels are opened when the current level is correctly solved. You always have access to the data for the current and all previous levels.
You are not required to provide the most efficient implementation. Any code that passes the unit tests is sufficient.
You can execute a single test case by running the following command in the terminal:
bash run_single_test.sh "<test_case_name>"
Requirements
Your task is to implement a simplified version of an in-memory database. Plan your design according to the level specifications below:
Level 1: In-memory database should support basic operations to manipulate records, fields, and values within fields.
Level 2: In-memory database should support displaying a record's fields based on a filter.
Levels 1 through 3 operations
For this exercise, the earlier levels use the following complete operation family. The database stores integer values in records identified by a string key; every record contains string field names.
set(timestamp, key, field, value): set or replace the field with a non-expiring integer value.
get(timestamp, key, field): return the visible value, or None when the record or field is absent or expired.
compare_and_set(timestamp, key, field, expected_value, new_value): replace the visible value only when it equals expected_value, and return whether the replacement happened.
compare_and_delete(timestamp, key, field, expected_value): delete the visible field only when its value equals expected_value, and return whether the deletion happened.
scan(timestamp, key): return every visible field as field(value), sorted lexicographically by field name.
scan_by_prefix(timestamp, key, prefix): return only the visible fields whose names begin with prefix, using the same formatting and order.
set_with_ttl(timestamp, key, field, value, ttl): set or replace the field. The new value is visible during the half-open interval [timestamp, timestamp + ttl).
compare_and_set_with_ttl(timestamp, key, field, expected_value, new_value, ttl): perform the conditional replacement and, on success, give the new value the supplied TTL.
All reads, scans, comparisons, and deletions treat an expired value as absent.
Level 4
The database should support look back get operation.
get_when(self, timestamp: int, key: str, field: str, at_timestamp: int) -> int | None, should return the value of field at at_timestamp from the record associated with key. If at_timestamp is 0, perform the get operation described in Level 1. It is guaranteed that at_timestamp will not be greater than timestamp. If the specified field or record did not exist at the given timestamp, return None.
Examples The example below shows how these operations should work (the section is scrollable to the right):
Queries
set_with_ttl(1, "A", "B", 3, 10)
compare_and_set_with_ttl(4, "A", "B", 3, 7, 9)
get(10, "A", "B")
get_when(13, "A", "B", 3)
get_when(15, "A", "B", 13)
Explanations
database state: {"A": {"B": 3}} with {"B": 3} expiring at timestamp 11
returns True; database state: {"A": {"B": 7}}
updates field "B" to {"B": 7} expiring at timestamp 13
returns 7; field "B" in record "A" had a value of 7 at timestamp 10
returns 3; field "B" in record "A" had a value of 3 at timestamp 3
returns None; field "B" in record "A" expired at timestamp 13
[execution time limit] 3 seconds
[memory limit] 4g
FastPrep practice interface
Complete runHistoricalDatabase. Process the rows of operations in order. The second item in every row is a strictly increasing timestamp. Return one string array for every input row.
["SET", timestamp, key, field, value]: call set and return an empty array.
["GET", timestamp, key, field]: call get and return a one-item array containing the value, or an empty array for None.
["COMPARE_AND_SET", timestamp, key, field, expectedValue, newValue]: call compare_and_set and return ["true"] or ["false"].
["COMPARE_AND_DELETE", timestamp, key, field, expectedValue]: call compare_and_delete and return ["true"] or ["false"].
["SCAN", timestamp, key]: call scan and return its formatted list.
["SCAN_BY_PREFIX", timestamp, key, prefix]: call scan_by_prefix and return its formatted list.
["SET_WITH_TTL", timestamp, key, field, value, ttl]: call set_with_ttl and return an empty array.
["COMPARE_AND_SET_WITH_TTL", timestamp, key, field, expectedValue, newValue, ttl]: call compare_and_set_with_ttl and return ["true"] or ["false"].
["GET_WHEN", timestamp, key, field, atTimestamp]: call get_when and return a one-item array containing the value, or an empty array for None.
Overwrites and successful deletions end the previous version at their timestamp but do not erase earlier history. An older value never reappears after a later version expires.

Function
runHistoricalDatabase(operations: String[][]) → String[][]

Examples
Example 1
operations = [["SET_WITH_TTL","1","A","B","3","10"],["COMPARE_AND_SET_WITH_TTL","4","A","B","3","7","9"],["GET","10","A","B"],["GET_WHEN","13","A","B","3"],["GET_WHEN","15","A","B","13"]]
return = [[],["true"],["7"],["3"],[]]
The value 3 is first visible on [1,11). The successful TTL compare-and-set writes 7 on [4,13), so the current read at timestamp 10 returns 7, the historical read at timestamp 3 returns 3, and the read at the exact expiration timestamp 13 returns no value.
Example 2
operations = [["SET","1","user2","age","18"],["SET","2","user2","height","180"],["SET","3","user2","address","1"],["SCAN","4","user2"],["SCAN_BY_PREFIX","5","user2","a"],["COMPARE_AND_SET","6","user2","age","18","19"],["COMPARE_AND_DELETE","7","user2","height","181"],["GET","8","user2","age"]]
return = [[],[],[],["address(1)","age(18)","height(180)"],["address(1)","age(18)"],["true"],["false"],["19"]]
The full scan sorts address, age, and height by field name. The prefix scan keeps only the two fields beginning with a. The conditional update of age succeeds, while deleting height with the wrong expected value fails.

Constraints
1 <= operations.length <= 2000.
Every operation row has exactly the format listed in the statement.
Timestamps are base-10 integers in [1, 10^9] and strictly increase across the input.
atTimestamp is in [0, timestamp].
Every ttl is in [1, 10^9].
Values are canonical signed 32-bit decimal integers.
Keys, fields, and prefixes contain 1 through 50 case-sensitive English letters or digits.
The source execution time limit is 3 seconds and the source memory limit is 4 GB.

Here's what it reduces to: for each (key, field), keep an append-only list of versions, each with a start timestamp, a value, and an expiry (infinity for plain set). Timestamps are strictly increasing, so the list stays sorted without extra work. Current get is just get_when with at_timestamp equal to the current time. For get_when, find the last version with start <= at_timestamp, then check at_timestamp < expiry. Return None otherwise. Deletions need a tombstone version so history stays correct. The pitfall is TTL on overwrite: when a new write lands, the old version's effective end is the new start, not its own expiry, whichever comes first. Also remember at_timestamp 0 means a normal get. Linear scan passes since efficiency isn't required, and binary search is a bonus. If the version logic gets tangled live, StealthCoder can sketch the structure while you keep typing.

Drill it cold or hedge it with StealthCoder. Either way, don't walk into the OA hoping you remember the trick.