In-Memory Database with TTL and Historical Lookup

For this exercise, implement the four-level in-memory database through the batch interface below. Earlier-level operations remain available after later levels are added.
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.

The trick: map key to field to a list of versions, each with a start timestamp, an optional expiry, and a value or a deletion marker. Timestamps are strictly increasing, so you just append and the list stays sorted. get at time t checks the last version only. get_when at_timestamp binary searches or scans back for the last version with start <= at_timestamp, then checks expiry against at_timestamp using the half-open rule [start, start+ttl). Overwrites and successful deletions must close out the prior version, so the old value stays readable in history but not in the present. Pitfalls: treating expiry as inclusive, forgetting that at_timestamp 0 means a plain get, and scan formatting as field(value) sorted by field name. Filter by prefix after the visibility check. If the version logic gets tangled under the clock, StealthCoder is the hedge that keeps you moving on the live OA.

If you see this problem in your OA tomorrow, the play is to recognize the pattern in 30 seconds. StealthCoder buys you that recognition.