Design an in-memory database with TTL and backups

You are asked to implement a small in-memory “database” that evolves across 4 parts. In each part you may reuse your previous code and only add/extend methods.

Data model

Each record is identified by a string key and stores a string value. Time is represented by an integer timestamp t (monotonically increasing in tests).

Part 1 — Basic read/write

Implement a database supporting:

• put(key, value, t) : store value for key .
• get(key, t) -> value | null : return the currently stored value for key , or null if missing.

Notes:

• If put is called multiple times for the same key, the latest write should be returned.

Part 2 — Scan

Add:

• scan(prefix, t) -> List<(key, value)> : return all key/value pairs whose key starts with prefix .

Requirements:

• Results must be sorted by key in lexicographic order.

Part 3 — Expiration (TTL)

Extend put to optionally accept a TTL:

• put(key, value, t, ttlSeconds) means the entry is valid for timestamps in the half-open interval [t, t + ttlSeconds) . After that it is expired.

Update get and scan so that expired items are not returned.

Clarifications:

• If a key is overwritten with a new put , the new value/TTL replaces the old one.
• Keys without TTL never expire.

Part 4 — Backup / Restore

Add support for backups:

• backup(t) -> backupId : captures the database state at time t (only non-expired entries at time t ).
• restore(backupId, t) : restores the database to exactly the state captured in that backup.

TTL behavior on restore:

• If an entry had remaining TTL at backup time, it should still expire after the remaining time elapses following the restore (i.e., expiration is based on the original timestamps/remaining lifetime, not “reset” to a fresh TTL).

What you need to deliver

Implement the required methods so that all provided test cases pass.

Constraints (typical for this style of OA)

• Up to ~10^5 operations.
• Keys/values are short strings.
• Aim for efficient lookups and scans.