# Build a Versioned In-Memory Database The source reports a four-stage in-memory database exercise but does not provide its exact method signatures. The following driver, return values, and error rules are a deterministic practice contract. Implement `VersionedDatabase` with these methods: ```python class VersionedDatabase: def set(self, timestamp: int, key: str, value: str, ttl: int | None = None) -> bool: ... def get(self, timestamp: int, key: str) -> str | None: ... def delete(self, timestamp: int, key: str) -> bool: ... def scan_prefix(self, timestamp: int, prefix: str) -> list[list[str]]: ... def get_at(self, timestamp: int, key: str, as_of_timestamp: int) -> str | None: ... ``` Also implement the literal-input console driver: ```python def run_versioned_database(operations: list[list[object]]) -> list[object]: ... ``` Process operations in list order and return one result per operation: - `["SET", timestamp, key, value]` calls `set(..., ttl=None)` and returns `True`. - `["SET", timestamp, key, value, ttl]` creates a version visible on `[timestamp, timestamp + ttl)` and returns `True`. - `["GET", timestamp, key]` returns the visible value or `None`. - `["DELETE", timestamp, key]` returns `True` and writes a tombstone only when the key is visible at that point. It returns `False` and writes nothing when the key is absent or expired. - `["SCAN_PREFIX", timestamp, prefix]` returns `[[key, value], ...]` for all visible keys beginning with `prefix`, ordered by key ascending. An empty prefix matches every visible key. - `["GET_AT", timestamp, key, as_of_timestamp]` returns the value visible at `as_of_timestamp`, or `None` if the key had no live version then. Every write, overwrite, and successful delete is an immutable version. A later version supersedes an earlier one for current reads but does not erase history. A non-expiring write stays live until superseded. Expiration does not delete history. Historical lookup chooses the most recent already-processed version whose `(timestamp, operation order)` is at or before the requested time and then applies that version's TTL and tombstone state. ## Deterministic Ordering and Errors - Operation timestamps and `as_of_timestamp` values are nonnegative integers. Operation timestamps are nondecreasing; operations sharing a timestamp take effect in list order. - A query observes only operations processed before that query. Because operation timestamps never decrease, a later query for an earlier timestamp sees every operation at that earlier timestamp that has already appeared in the list. - `as_of_timestamp` must not exceed the query's `timestamp`. - Keys and values are strings; keys and values may be empty. TTL, when present, is a positive integer. - A malformed operation, unknown command, decreasing timestamp, invalid TTL, or future `as_of_timestamp` raises `ValueError`. Validate such an operation before changing state. Ordinary misses use the `None` or `False` results above and are not exceptions. ## Performance Expectations Discuss the cost of point reads and writes, prefix scans, and historical reads. Historical lookup should use per-key ordered history rather than replaying the full database log. Test exact expiration boundaries, overwrites at the same timestamp, expired deletes, delete-then-recreate, empty prefixes, and queries before the first version.