Design an in-memory database with TTL and history

Q: Design an in-memory database with TTL and history

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.

Q: How do I approach Coding & Algorithms interview questions?

Coding & Algorithms questions require understanding of core concepts and practice. PracHub provides solutions with explanations to help you master coding & algorithms interviews.

Question

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: (

set(timestamp, key, field, value): store value at key-field. (
get(timestamp, key, field): return the current value or null if key or field does not exist or the value has expired. (
compareAndSet(timestamp, key, field, expectedValue, newValue): if the current value equals expectedValue, atomically set to newValue and return true; otherwise return false. (
compareAndDelete(timestamp, key, field, expectedValue): if the current value equals expectedValue, delete it and return true; otherwise return false. (
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. (
scanByPrefix(timestamp, key, prefix): like scan but only include fields whose names start with prefix. (
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. (
compareAndSetWithTtl(timestamp, key, field, expectedValue, newValue, ttl): like compareAndSet; on success, set newValue with the given ttl. (
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(...,
= null, getWhen(...,
= 10, getWhen(...,
= null, getWhen(...,
= 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.

Design an in-memory database with TTL and history

Overview

Comments (0)