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.

Design an in-memory database with TTL and history

Quick Overview

This question evaluates understanding of time-versioned in-memory key–field–value stores, covering TTL-based expiration, historical reads, atomic compare-and-set/delete semantics, efficient scan/scan-by-prefix operations, and time/space complexity analysis, and it belongs to the Coding & Algorithms domain.

Company: Meta

Role: Software Engineer

Category: Coding & Algorithms

Difficulty: Medium

Interview Round: Take-home Project

Design and implement an in-memory key–field–value store with monotonic timestamps. Keys and fields are strings; values are integers. Provide these APIs and behaviors: ( 1) set(timestamp, key, field, value): store value at key-field. ( 2) get(timestamp, key, field): return the current value or null if key or field does not exist or the value has expired. ( 3) compareAndSet(timestamp, key, field, expectedValue, newValue): if the current value equals expectedValue, atomically set to newValue and return true; otherwise return false. ( 4) compareAndDelete(timestamp, key, field, expectedValue): if the current value equals expectedValue, delete it and return true; otherwise return false. ( 5) scan(timestamp, key): return an array of strings formatted as "field(value)" for all fields under key, sorted alphabetically by field; return an empty array if key does not exist. ( 6) scanByPrefix(timestamp, key, prefix): like scan but only include fields whose names start with prefix. ( 7) setWithTtl(timestamp, key, field, value, ttl): like set, but the value expires automatically at timestamp + ttl; expired values must not appear in get/scan/scanByPrefix results. ( 8) compareAndSetWithTtl(timestamp, key, field, expectedValue, newValue, ttl): like compareAndSet; on success, set newValue with the given ttl. ( 9) getWhen(timestamp, key, field, atTimestamp): return the value that would have been visible at atTimestamp (where atTimestamp < timestamp), or null if none; for example, if value 10 is set at time 10, expires at 12, and value 18 is set at 18, then getWhen(..., 5) = null, getWhen(..., 11) = 10, getWhen(..., 15) = null, getWhen(..., 20) = 18. Assume all provided timestamps across calls are strictly increasing. Describe your data structures, how you track expirations and history, and analyze time and space complexity.

Quick Answer: This question evaluates understanding of time-versioned in-memory key–field–value stores, covering TTL-based expiration, historical reads, atomic compare-and-set/delete semantics, efficient scan/scan-by-prefix operations, and time/space complexity analysis, and it belongs to the Coding & Algorithms domain.

Implement an in-memory key-field-value store with monotonically increasing timestamps. Keys and fields are strings; values are integers. Rather than instantiating a class, write a single function `solution(operations)` that replays a list of API calls and returns one result per call (None/null for void methods). Each operation is a list `[methodName, ...args]`. Support the following methods, which build up across four levels (each level keeps every earlier behavior): Level 1 - Basic store - `set(timestamp, key, field, value)` -> void: store value at key/field. - `get(timestamp, key, field)` -> int|null: current value, or null if the key/field is absent or the value has expired. - `compareAndSet(timestamp, key, field, expectedValue, newValue)` -> bool: if the current value equals expectedValue, set it to newValue and return true; otherwise return false. - `compareAndDelete(timestamp, key, field, expectedValue)` -> bool: if the current value equals expectedValue, delete it and return true; otherwise return false. Level 2 - Scanning - `scan(timestamp, key)` -> string[]: every live field formatted as "field(value)", sorted alphabetically by field; empty array if the key does not exist. - `scanByPrefix(timestamp, key, prefix)` -> string[]: like scan but only fields whose name starts with prefix. Level 3 - TTL / expiration - `setWithTtl(timestamp, key, field, value, ttl)` -> void: like set, but the value expires at timestamp + ttl. Expired values must not appear in get/scan/scanByPrefix. - `compareAndSetWithTtl(timestamp, key, field, expectedValue, newValue, ttl)` -> bool: like compareAndSet; on success, write newValue with the given ttl. Level 4 - Point-in-time history - `getWhen(timestamp, key, field, atTimestamp)` -> int|null: the value that would have been visible at atTimestamp (with atTimestamp <= timestamp), accounting for past writes and expirations; null if none. A value written with a ttl is visible on the half-open interval [writeTime, writeTime + ttl); at exactly the expiry time it is already gone. A later write to the same key/field supersedes the earlier value from the moment of the new write. All timestamps across calls are strictly increasing.

Constraints

Keys, fields, and prefixes are non-empty strings; values and ttl are integers with ttl > 0.
Timestamps passed to successive calls are strictly increasing.
For getWhen, atTimestamp <= timestamp (you only ever query the past or present).
A value set with ttl is live on [timestamp, timestamp + ttl); it is expired at exactly timestamp + ttl.
scan / scanByPrefix output is sorted alphabetically by field name and excludes expired or deleted fields.
1 <= number of operations <= 10^4.

Examples

Input: [['set', 1, 'user1', 'age', 12], ['get', 2, 'user1', 'age'], ['get', 3, 'user1', 'height'], ['get', 4, 'userX', 'age'], ['compareAndSet', 5, 'user1', 'age', 12, 13], ['get', 6, 'user1', 'age'], ['compareAndSet', 7, 'user1', 'age', 99, 100], ['compareAndDelete', 8, 'user1', 'age', 13], ['get', 9, 'user1', 'age'], ['compareAndDelete', 10, 'user1', 'age', 13]]

Expected Output: [None, 12, None, None, True, 13, False, True, None, False]

Explanation: Level 1: set stores 12; get returns it; missing field/key give null. compareAndSet succeeds when current==expected (12->13) and fails otherwise (current 13 != 99). compareAndDelete removes the field when it matches (13), so the next get is null and the second delete fails.

Input: [['set', 1, 'user2', 'age', 18], ['set', 2, 'user2', 'height', 180], ['set', 3, 'user2', 'address', 1], ['scan', 4, 'user2'], ['scanByPrefix', 5, 'user2', 'a'], ['scan', 6, 'nope']]

Expected Output: [None, None, None, ['address(1)', 'age(18)', 'height(180)'], ['address(1)', 'age(18)'], []]

Explanation: Level 2: scan lists every live field as 'field(value)' sorted alphabetically (address, age, height). scanByPrefix 'a' keeps only address and age. Scanning a missing key returns an empty array.

Input: [['setWithTtl', 10, 'k', 'f', 5, 5], ['get', 12, 'k', 'f'], ['get', 15, 'k', 'f'], ['get', 20, 'k', 'f'], ['scan', 16, 'k']]

Expected Output: [None, 5, None, None, []]

Explanation: Level 3: setWithTtl at t=10 with ttl=5 makes the value live on [10,15). get at 12 sees 5; at 15 (the expiry boundary, exclusive) and at 20 it is gone. scan at 16 omits the expired field, returning [].

Input: [['setWithTtl', 10, 'k', 'f', 10, 2], ['set', 18, 'k', 'f', 18], ['getWhen', 30, 'k', 'f', 5], ['getWhen', 30, 'k', 'f', 11], ['getWhen', 30, 'k', 'f', 15], ['getWhen', 30, 'k', 'f', 20]]

Expected Output: [None, None, None, 10, None, 18]

Explanation: Level 4 (the prompt's worked example): value 10 lives on [10,12), value 18 lives on [18,inf). getWhen(5)=null (before any write), getWhen(11)=10, getWhen(15)=null (10 expired, 18 not yet written), getWhen(20)=18.

Input: [['set', 1, 'a', 'x', 5], ['compareAndSetWithTtl', 2, 'a', 'x', 5, 9, 3], ['get', 3, 'a', 'x'], ['get', 5, 'a', 'x'], ['get', 6, 'a', 'x']]

Expected Output: [None, True, 9, None, None]

Explanation: compareAndSetWithTtl: current value 5 matches expected, so it writes 9 with ttl=3 -> live on [2,5). get at 3 returns 9; at 5 (exclusive expiry) and 6 the value has expired.

Input: []

Expected Output: []

Explanation: Edge case: no operations yields an empty result list.

Hints

Model the store as key -> field -> list of versions, where each version is (start, end, value). end is the expiry timestamp (writeTime + ttl) or infinity for a non-TTL value.
Because timestamps strictly increase, a new write to an existing field can simply close the previous live version by setting its end to the new write time; compareAndDelete closes the current version at the delete time.
For get / scan, the relevant version is the latest one whose interval [start, end) contains the query timestamp. For getWhen(atTimestamp), binary-search the version list for the interval covering atTimestamp.
Treat expiry as exclusive: a value with end = E is visible for t < E and gone at t == E. This is exactly why getWhen(15) is null in the worked example (10 expired at 12, 18 not written until 18).

Quick Overview