Katkat
Back

Design an in-memory database with TTL and history

MetaSoftware Engineer · Online Assessment
MediumSoftware EngineerOnline AssessmentCoding & Algorithms

Last updated

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.

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(...,
  10. = null, getWhen(...,
  11. = 10, getWhen(...,
  12. = null, getWhen(...,
  13. = 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.