Implement an Expiring Record Store

Implement a level-based in-memory record store.

The store contains records identified by a string key. Each record contains fields, where each field is a string and each value is a string.

Level 1: Basic mutations

Implement:

• set(key, field, value): Create the record if it does not exist, then set field to value.
• get(key, field): Return the current value for field, or null if the record or field does not exist.
• delete(key, field): Remove field from the record. Return true if a field was removed, otherwise return false. If a record becomes empty, it may be removed from the store.

Level 2: Scanning

Implement:

• scan(key): Return all fields for key, sorted lexicographically by field name. Format each item as field(value). Return an empty list if the record does not exist.
• scan_by_prefix(key, prefix): Return only fields whose names start with prefix, sorted lexicographically by field name and formatted as field(value).

Level 3: Timestamps and TTL

Extend the store so fields can be written with timestamps and optional time-to-live values.

Implement:

• set_at(key, field, value, timestamp): Set the field at timestamp with no expiration.
• set_at_with_ttl(key, field, value, timestamp, ttl): Set the field at timestamp; it is visible for query times t such that timestamp <= t < timestamp + ttl.
• delete_at(key, field, timestamp): Delete the field at timestamp if it exists and is not expired at that time. Return true if a field was deleted, otherwise return false.
• get_at(key, field, timestamp): Return the value visible at timestamp, or null if none exists.
• scan_at(key, timestamp): Return all fields visible at timestamp, sorted and formatted as in scan.
• scan_by_prefix_at(key, prefix, timestamp): Return all visible fields at timestamp whose names start with prefix, sorted and formatted as in scan_by_prefix.

Assume timestamps passed to timestamped operations are non-decreasing. A later write to the same (key, field) replaces the previous value and expiration policy. Expired or deleted fields must not appear in reads or scans.

Part 1: Basic In-Memory Record Store

Implement the core mutation operations of an in-memory record store. Each record is identified by a string key and stores string field -> value pairs. Process the operations in order and return the result of each operation. Supported operations: ['set', key, field, value] creates the record if needed and stores the value; ['get', key, field] returns the current value or None; ['delete', key, field] removes the field and returns True if something was removed, otherwise False. If a record becomes empty after deletion, remove it from the store.

Constraints

• 1 <= len(operations) <= 200000
• Each key, field, and value is a string of length between 1 and 100
• The total length of all strings in the input is at most 200000
• All operation names are valid and appear exactly as specified

Examples

Example 1

Input: [['set', 'user', 'name', 'alice'], ['get', 'user', 'name'], ['set', 'user', 'name', 'bob'], ['get', 'user', 'name'], ['delete', 'user', 'name'], ['get', 'user', 'name']]
Output: [None, 'alice', None, 'bob', True, None]

Explanation: Setting the same field again overwrites the old value.

Example 2

Input: [['get', 'missing', 'field'], ['delete', 'missing', 'field'], ['set', 'a', 'x', '1'], ['delete', 'a', 'y'], ['get', 'a', 'x']]
Output: [None, False, None, False, '1']

Explanation: Reading or deleting a missing field should safely return None or False.

Hints

1. A dictionary from key to another dictionary of field -> value is enough for all Level 1 operations.
2. After deleting a field, check whether its record became empty and remove that record too.

Part 2: Record Store with Scanning

Extend the in-memory record store to support scanning. Each record is identified by a string key and stores string field -> value pairs. Process the operations in order and return the result of each operation. In addition to set, get, and delete, support ['scan', key], which returns all fields for that key sorted lexicographically and formatted as field(value), and ['scan_by_prefix', key, prefix], which returns only fields whose names start with prefix, also sorted and formatted. If a record does not exist, scans return an empty list.

Constraints

• 1 <= len(operations) <= 200000
• Each key, field, value, and prefix is a string of length between 0 and 100
• The total length of all strings in the input is at most 200000
• Fields in scans must be sorted lexicographically by field name

Examples

Example 1

Input: [['set', 'user', 'name', 'alice'], ['set', 'user', 'age', '30'], ['set', 'user', 'email', 'a@example.com'], ['scan', 'user'], ['scan_by_prefix', 'user', 'e']]
Output: [None, None, None, ['age(30)', 'email(a@example.com)', 'name(alice)'], ['email(a@example.com)']]

Explanation: Scan results must be sorted by field name, not by insertion order.

Example 2

Input: [['set', 'k', 'apple', '1'], ['set', 'k', 'app', '2'], ['set', 'k', 'banana', '3'], ['scan_by_prefix', 'k', 'app'], ['delete', 'k', 'app'], ['scan_by_prefix', 'k', 'app']]
Output: [None, None, None, ['app(2)', 'apple(1)'], True, ['apple(1)']]

Explanation: Only fields starting with the prefix are returned, still in lexicographic order.

Hints

1. Keep the same nested dictionary structure from Part 1, then build scan results from the inner dictionary.
2. For prefix scans, filter field names first, then sort the matching fields before formatting them.

Part 3: Expiring Record Store with Timestamps and TTL

Implement a timestamped in-memory record store with TTL support. Each record is identified by a string key, and each field stores a string value plus an optional expiration time. Process operations in order and return the result of each operation. Timestamps in the input are non-decreasing across the whole operation list. Supported operations: ['set_at', key, field, value, timestamp] writes a non-expiring value; ['set_at_with_ttl', key, field, value, timestamp, ttl] writes a value visible exactly when timestamp <= t < timestamp + ttl; ['delete_at', key, field, timestamp] deletes the field only if it exists and is not expired at that time; ['get_at', key, field, timestamp] returns the visible value or None; ['scan_at', key, timestamp] returns all visible fields sorted and formatted as field(value); ['scan_by_prefix_at', key, prefix, timestamp] returns only visible fields whose names start with prefix, also sorted and formatted. A later write to the same (key, field) replaces the previous value and expiration policy.

Constraints

• 1 <= len(operations) <= 200000
• The sequence of timestamps across all operations is non-decreasing
• 1 <= ttl <= 1000000000
• Each key, field, value, and prefix is a string of length between 0 and 100

Examples

Example 1

Input: [['set_at_with_ttl', 'user', 'token', 'abc', '10', '5'], ['get_at', 'user', 'token', '10'], ['get_at', 'user', 'token', '14'], ['get_at', 'user', 'token', '15'], ['scan_at', 'user', '15']]
Output: [None, 'abc', 'abc', None, []]

Explanation: A TTL write at time 10 with TTL 5 is visible at times 10 through 14, but not at 15.

Example 2

Input: [['set_at_with_ttl', 'k', 'a', '1', '1', '10'], ['set_at', 'k', 'a', '2', '5'], ['get_at', 'k', 'a', '6'], ['get_at', 'k', 'a', '20'], ['scan_at', 'k', '20']]
Output: [None, None, '2', '2', ['a(2)']]

Explanation: A later write replaces both the old value and the old expiration policy.

Hints

1. Because timestamps never go backward, you do not need full history for each field; keeping only the current value and its expiration time is enough.
2. On any read, scan, or delete at time t, treat a field with expire_at <= t as missing, and you can lazily remove it from the store.