Read Current and Historical Field Values with Expiration

Problem Statement

Implement an in-memory database that stores values associated with a composite key of (key, field). The store must support write operations with optional time-to-live (TTL) expiration, deletions, and point-in-time historical reads.

Historical reads should accurately reflect the state of any (key, field) at the queried timestamp: if a field was active at that timestamp, its value should be returned; if it had expired, had been deleted, or had not yet been set, the query should indicate it was not present.

Implement the HistoricalFieldStore class with the following methods:

• __init__(): Initializes the data store.
• set_field(key: str, field: str, value: str, timestamp: int, ttl: int | None = None) -> None: Sets the field to value at the given timestamp. If ttl is provided (where ttl > 0), the value is valid for the half-open interval [timestamp, timestamp + ttl). If ttl is None, the value does not expire automatically. If a previous value was active at timestamp, its validity ends at timestamp.
• delete_field(key: str, field: str, timestamp: int) -> bool: Deletes the specified field at timestamp. Returns True if the field was active immediately prior to timestamp, or False if the field did not exist, was already deleted, or had already expired.
• get_field(key: str, field: str, timestamp: int) -> str | None: Returns the value of field under key at the specified timestamp. If the field was not set, had expired, or was deleted as of timestamp, return None.

Constraints

• Calls to set_field and delete_field are guaranteed to have strictly increasing timestamp values across all operations.
• Calls to get_field may query any integer timestamp >= 1 in any order.
• 1 <= timestamp, ttl <= 10^9
• key, field, and value consist of alphanumeric characters and have lengths between 1 and 50.
• At most 10^5 total calls will be made across all methods.

Examples

Example 1

store = HistoricalFieldStore()

# Set user:1 role to 'engineer' at t=10 with TTL=10 (valid for t in [10, 20))
store.set_field("user:1", "role", "engineer", timestamp=10, ttl=10)

# Query before set
assert store.get_field("user:1", "role", timestamp=5) is None

# Query during validity
assert store.get_field("user:1", "role", timestamp=10) == "engineer"
assert store.get_field("user:1", "role", timestamp=19) == "engineer"

# Query at and after expiration
assert store.get_field("user:1", "role", timestamp=20) is None
assert store.get_field("user:1", "role", timestamp=25) is None

Example 2

store = HistoricalFieldStore()

store.set_field("doc:42", "status", "draft", timestamp=100) # No TTL
store.set_field("doc:42", "status", "published", timestamp=200, ttl=50) # valid [200, 250)

assert store.get_field("doc:42", "status", timestamp=150) == "draft"
assert store.get_field("doc:42", "status", timestamp=200) == "published"
assert store.get_field("doc:42", "status", timestamp=249) == "published"
assert store.get_field("doc:42", "status", timestamp=250) is None

# Historical draft is still readable in its original active window
assert store.get_field("doc:42", "status", timestamp=199) == "draft"

# Deleting after expiration returns False
assert store.delete_field("doc:42", "status", timestamp=300) is False

Edge Cases

• Querying at exactly timestamp + ttl: The entry should be considered expired (exclusive upper bound).
• Overwriting an entry before its TTL expires: The previous entry's expiration must be capped at the new entry's start timestamp.
• Deleting a field that was set without a TTL vs. deleting one that already expired naturally.