How do I practice coding and algorithm questions?

Use PracHub's coding console to write, test, and debug your solutions in Python or JavaScript. View hints, test against sample inputs, and compare with official solutions.

What difficulty level is this coding question?

This is a medium difficulty Coding & Algorithms question, commonly asked during Take-home Project rounds at Meta.

What role is this question designed for?

This question is commonly asked for Software Engineer candidates at Meta during technical interviews.

Implement an in-memory key-field-value DB with TTL

Q: Implement an in-memory key-field-value DB with TTL

This question evaluates implementation skills in efficient in-memory data structures, time-to-live (TTL) expiration semantics, ordered and prefix scans, and snapshot backup/restore mechanisms.

Company: Meta

Role: Software Engineer

Category: Coding & Algorithms

Difficulty: medium

Interview Round: Take-home Project

## In-Memory DB with TTL + Scan + Backup/Restore Implement an in-memory database storing records by `(key, field) -> value` with optional TTL. ### Data model / rules - `key` and `field` are strings. - `value` is a string (or integer; choose one and be consistent). - Each stored `(key, field)` has an expiration time `expire_at`. - If a value is set without TTL, `expire_at = +∞`. - A value is **visible** at query time `t` iff `t < expire_at`. ### API 1. `set(key, field, value, timestamp) -> void` - Store `(value, +∞)`. 2. `set_with_ttl(key, field, value, timestamp, ttl) -> void` - Store `(value, timestamp + ttl)`. 3. `get(key, field, timestamp) -> value | null` - Return `null` if missing or expired at `timestamp`. 4. `delete(key, field, timestamp) -> bool` - Delete the field (regardless of TTL). - Return `false` if `(key, field)` does not exist; otherwise `true`. 5. `scan(key, timestamp) -> list<(field, value)>` - Return all non-expired fields for `key` at `timestamp`. - Sort results by `field` ascending. 6. `scan_with_prefix(key, prefix, timestamp) -> list<(field, value)>` - Like `scan`, but only include `field`s that start with `prefix`. 7. `backup(timestamp) -> void` - Persist a full snapshot of the DB state at `timestamp`. 8. `restore(timestamp, restore_to_time) -> void` - Restore DB state from the **most recent** backup with `backup_time <= restore_to_time`. - If no such backup exists, restore to an empty DB. ### Notes - Assume timestamps are integers. - Assume up to ~1e5 operations; aim for efficient scans and correct TTL handling.

Quick Answer: This question evaluates implementation skills in efficient in-memory data structures, time-to-live (TTL) expiration semantics, ordered and prefix scans, and snapshot backup/restore mechanisms.

Implement an in-memory database that stores records keyed by `(key, field)` with an optional time-to-live (TTL), plus prefix scans and point-in-time backup/restore. You are given a list of `operations`. Each operation is a list whose first element is the operation name, followed by its arguments: - `["set", key, field, value, timestamp]` — store `value` at `(key, field)` with no expiry. Returns nothing. - `["set_with_ttl", key, field, value, timestamp, ttl]` — store `value` with `expire_at = timestamp + ttl`. Returns nothing. - `["get", key, field, timestamp]` — return the value if present and **not expired** at `timestamp` (visible iff `timestamp < expire_at`), else `None`. - `["delete", key, field, timestamp]` — remove `(key, field)` regardless of TTL. Return `True` if it existed, else `False`. - `["scan", key, timestamp]` — return a list of `[field, value]` for every non-expired field under `key`, sorted by `field` ascending. - `["scan_with_prefix", key, prefix, timestamp]` — like `scan`, but only fields that start with `prefix`. - `["backup", timestamp]` — persist a full snapshot of the DB at `timestamp`. Returns nothing. - `["restore", timestamp, restore_to_time]` — replace the DB with the **most recent** backup whose `backup_time <= restore_to_time`. If none exists, the DB becomes empty. Returns nothing. Return a list with one entry per operation: the operation's return value, or `None` for the void operations (`set`, `set_with_ttl`, `backup`, `restore`). Values are strings and timestamps are integers.

Constraints

key, field, prefix, and value are strings; value is treated as a string.
timestamps and ttl are integers; ttl > 0.
A (key, field) is visible at time t iff t < expire_at; a no-TTL set uses expire_at = +inf.
delete removes the field regardless of expiry and returns whether it existed.
restore selects the most recent backup with backup_time <= restore_to_time; if none, the DB becomes empty.
Up to ~1e5 operations total.

Examples

Input: ([['set', 'k1', 'f1', 'v1', 1], ['get', 'k1', 'f1', 2], ['set_with_ttl', 'k1', 'f2', 'v2', 5, 10], ['get', 'k1', 'f2', 14], ['get', 'k1', 'f2', 15], ['get', 'k1', 'fX', 3], ['get', 'kX', 'f1', 3], ['delete', 'k1', 'f1', 20], ['delete', 'k1', 'f1', 21], ['get', 'k1', 'f1', 22]],)

Expected Output: [None, 'v1', None, 'v2', None, None, None, True, False, None]

Explanation: Basic set/get with a TTL expiry boundary (t>=expire is expired), missing key/field returns null, and delete returns true only when the field exists.

Input: ([['set', 'k', 'banana', 'B', 0], ['set', 'k', 'apple', 'A', 0], ['set_with_ttl', 'k', 'apricot', 'AP', 0, 5], ['set', 'k', 'cherry', 'C', 0], ['scan', 'k', 3], ['scan', 'k', 5], ['scan_with_prefix', 'k', 'ap', 3], ['scan_with_prefix', 'k', 'ap', 5], ['scan', 'missing', 0]],)

Expected Output: [None, None, None, None, [['apple', 'A'], ['apricot', 'AP'], ['banana', 'B'], ['cherry', 'C']], [['apple', 'A'], ['banana', 'B'], ['cherry', 'C']], [['apple', 'A'], ['apricot', 'AP']], [['apple', 'A']], []]

Explanation: scan and scan_with_prefix return [field, value] pairs sorted by field ascending, filtering out expired entries; a missing key yields an empty list.

Input: ([['set', 'k', 'f', 'v1', 1], ['backup', 10], ['set', 'k', 'f', 'v2', 11], ['backup', 20], ['set', 'k', 'f', 'v3', 21], ['get', 'k', 'f', 22], ['restore', 30, 25], ['get', 'k', 'f', 31], ['restore', 40, 15], ['get', 'k', 'f', 41], ['restore', 50, 5], ['get', 'k', 'f', 51]],)

Expected Output: [None, None, None, None, None, 'v3', None, 'v2', None, 'v1', None, None]

Explanation: backup/restore: restore loads the most recent backup whose backup_time <= restore_to_time; with no eligible backup the DB becomes empty.

Input: ([['set_with_ttl', 'a', 'x', '1', 0, 100], ['backup', 5], ['delete', 'a', 'x', 6], ['get', 'a', 'x', 7], ['restore', 8, 5], ['get', 'a', 'x', 9], ['get', 'a', 'x', 100], ['restore', 200, 1], ['scan', 'a', 201]],)

Expected Output: [None, None, True, None, None, '1', None, None, []]

Explanation: TTL and deletes are captured in snapshots: a deleted field comes back after restore with its original expiry intact; no eligible backup restores to empty.

Input: ([],)

Expected Output: []

Explanation: Edge case: an empty operation list returns an empty result list.

Hints

Model storage as a nested map key -> field -> (value, expire_at). Store expire_at = +inf for set without TTL and timestamp + ttl for set_with_ttl, so get/scan only need the single check t < expire_at.
Don't physically purge expired entries on a timer — just filter them at read time (get/scan). Deletion is the only thing that actually removes a field.
For backup, store a DEEP copy of the whole storage map under its timestamp; a shallow copy would let later mutations corrupt the snapshot. For restore, keep backup timestamps sorted and binary-search for the largest one <= restore_to_time (and restore to empty when there is none).

Quick Overview

This question evaluates implementation skills in efficient in-memory data structures, time-to-live (TTL) expiration semantics, ordered and prefix scans, and snapshot backup/restore mechanisms.