Katkat
Back

Process Operations in a Timestamped In-Memory Database

TradedeskSoftware Engineer · Online Assessment
MediumSoftware EngineerOnline AssessmentCoding & Algorithms

Last updated

This problem tests your ability to design an in-memory data store with complex querying and expiration requirements using efficient nested data structures.

Problem Statement

Implement an in-memory key-value store that supports a two-level hierarchy (key and field). Each value has an optional Time-To-Live (TTL) attribute. If a TTL is set, the value expires after current_time + ttl. If a key or field does not exist or has expired, it should be treated as non-existent.

API Requirements

Implement a class TimestampedDB with the following methods:

  1. SET(key, field, value, ttl): Stores the value. If ttl > 0, the value expires at now + ttl. If ttl is 0, it never expires.
  2. GET(key, field, now): Returns the value for the given key and field if it exists and hasn't expired relative to now. Otherwise, return null.
  3. DELETE(key, field): Removes the entry.
  4. SCAN(key, now): Returns all non-expired fields and their values for a given key, sorted lexicographically by field name.
  5. SCAN_PREFIX(key, field_prefix, now): Returns all non-expired fields and values for a given key where the field starts with field_prefix, sorted lexicographically.

Constraints

  • Number of operations: up to 100,000.
  • Keys and fields are non-empty strings.
  • now is an integer representing the current system time.

Examples

db = TimestampedDB()
db.SET("user:1", "name", "Alice", 100) # Expires at t=100
db.SET("user:1", "age", "30", 0)       # Never expires

# At t=50:
db.GET("user:1", "name", 50)  # Returns "Alice"
db.SCAN("user:1", 50)         # Returns [("age", "30"), ("name", "Alice")]

# At t=150:
db.GET("user:1", "name", 150) # Returns null (expired)

Edge Cases

  • Accessing a key that has no fields.
  • Updating a value that already has a TTL.
  • SCAN where all entries have expired.

Hints

Hint 1

Use a nested dictionary structure where the outer key maps to an inner dictionary containing fields and their metadata (value and expiration time).

Hint 2

For the SCAN operations, use a sorted data structure for fields or collect all fields and sort them manually if the number of fields per key is relatively small.

Hint 3

During GET and SCAN operations, always check the current timestamp against the expiration timestamp to determine if the data should be lazily deleted or ignored.

Follow-up questions

  • How would you optimize the storage if the number of keys grows to billions and cannot fit in one machine's memory?
  • If we needed to perform a background cleanup of expired keys, what data structure would you use to efficiently find expired entries without scanning the entire database?
  • How would you implement concurrency control if multiple threads are reading and writing to this database simultaneously?