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.