PracHub
QuestionsPremiumCoachesLearningGuidesInterview Prep

Quick Overview

This question evaluates a candidate's understanding of time-versioned key-field storage, per-write TTL expirations, timestamp-based visibility, and atomic compare-and-set/delete semantics, exercising competency in maintaining historical state and correct value visibility over time.

  • medium
  • Tradedesk
  • Coding & Algorithms
  • Machine Learning Engineer

Design a time-travel key-field store with TTL

Company: Tradedesk

Role: Machine Learning Engineer

Category: Coding & Algorithms

Difficulty: medium

Interview Round: Take-home Project

## Problem Implement an in-memory “database” that stores **records** by `key` and **fields** within each key. Each operation is given a `timestamp` (integer, non-decreasing across calls) and should behave as if executed at that time. A record conceptually looks like: - `DB[key][field] = value` (value is an integer) However, later levels add **TTL expiration** and **historical (“time-travel”) queries**, so your implementation must maintain enough history to answer those queries. ### Common rules - If a requested `key` or `field` does not exist (or is expired at the queried time), treat it as missing. - Deleting a field removes it from the record at that time. - Unless otherwise specified, functions that read data use the provided `timestamp` as the “current time” for visibility/expiration. - Return formats must be deterministic. Unless specified by the interviewer, return scan results sorted by `field` ascending. --- ## Level 1: Basic operations Implement: 1. `set(timestamp: int, key: str, field: str, value: int) -> None` - Sets `DB[key][field] = value` at `timestamp`. 2. `get(timestamp: int, key: str, field: str) -> Optional[int]` - Returns the current value for `(key, field)` at `timestamp`, or `None` if missing. 3. `compare_and_set(timestamp: int, key: str, field: str, expected_value: int, new_value: int) -> bool` - If the current value at `timestamp` equals `expected_value`, update it to `new_value` and return `True`. - Otherwise return `False` (no change). 4. `compare_and_delete(timestamp: int, key: str, field: str, expected_value: int) -> bool` - If the current value at `timestamp` equals `expected_value`, delete the field and return `True`. - Otherwise return `False`. --- ## Level 2: Scans Implement: 1. `scan(timestamp: int, key: str) -> List[str]` - Returns all visible fields for `key` at `timestamp` formatted as: `"{field}({value})"`. - Return the list sorted by `field` ascending. 2. `scan_with_prefix(timestamp: int, key: str, prefix: str) -> List[str]` - Same as `scan`, but only include entries where the formatted string starts with `prefix`. - (Equivalently: include only fields whose names start with `prefix`.) --- ## Level 3: TTL support Add per-write TTL (time-to-live). A value written with TTL is visible only in the half-open interval: - visible for times `t` where `write_timestamp <= t < write_timestamp + ttl`. Implement: 1. `set_with_ttl(timestamp: int, key: str, field: str, value: int, ttl: int) -> None` 2. `compare_and_set_with_ttl(timestamp: int, key: str, field: str, expected_value: int, new_value: int, ttl: int) -> bool` - Same semantics as `compare_and_set`, but when the update happens it writes `new_value` with the provided `ttl`. Additionally, **all previously implemented read/write operations** must be updated so that: - reads (`get`, `scan`, `scan_with_prefix`) do not return expired values, - compare-and-* operations compare against the value visible at that `timestamp` (treat expired as missing). --- ## Level 4: Time-travel query Implement: - `get_when(timestamp: int, key: str, field: str, at_timestamp: int) -> Optional[int]` It should return the value of `(key, field)` **as it was visible at time `at_timestamp`**, considering: - historical `set` / `set_with_ttl` - successful compare-and-* updates - deletions - TTL expiration relative to each write time Assume `at_timestamp <= timestamp`. If the value was missing or expired at `at_timestamp`, return `None`. --- ## Notes / Constraints (if not provided, assume typical interview constraints) - Timestamps are non-decreasing across operations. - Up to ~1e5–2e5 operations total. - Aim for efficient per-operation runtime (e.g., logarithmic in the number of updates per field).

Quick Answer: This question evaluates a candidate's understanding of time-versioned key-field storage, per-write TTL expirations, timestamp-based visibility, and atomic compare-and-set/delete semantics, exercising competency in maintaining historical state and correct value visibility over time.

Part 1: Basic Key-Field Store Operations

Implement a batch runner for an in-memory key-field store. Each record is addressed by a string key and contains string fields with integer values. Operations are processed in the given order, and timestamps are non-decreasing but do not otherwise affect Part 1 behavior. Support SET, GET, CAS, and CAD. SET writes a value. GET reads the current value. CAS compares the current value with an expected value and updates it if equal. CAD compares the current value with an expected value and deletes the field if equal.

Constraints

  • 1 <= len(operations) <= 200000
  • Timestamps are non-decreasing integers encoded as strings.
  • Keys and fields are non-empty lowercase strings of length at most 30.
  • Values fit in a signed 32-bit integer.
  • A compare operation against a missing field must fail.

Examples

Input: ([['SET', '1', 'user1', 'age', '30'], ['GET', '2', 'user1', 'age'], ['CAS', '3', 'user1', 'age', '30', '31'], ['GET', '4', 'user1', 'age'], ['CAD', '5', 'user1', 'age', '30'], ['CAD', '6', 'user1', 'age', '31'], ['GET', '7', 'user1', 'age']],)

Expected Output: ['30', 'true', '31', 'false', 'true', '']

Explanation: The value is set to 30, updated to 31 by a successful CAS, then deleted by a successful CAD.

Input: ([['GET', '1', 'k', 'f'], ['CAS', '2', 'k', 'f', '0', '1'], ['CAD', '3', 'k', 'f', '0']],)

Expected Output: ['', 'false', 'false']

Explanation: Missing fields read as empty output and cannot satisfy compare operations.

Input: ([['SET', '1', 'k1', 'a', '-5'], ['SET', '1', 'k1', 'b', '10'], ['SET', '2', 'k2', 'a', '7'], ['GET', '3', 'k1', 'a'], ['GET', '3', 'k2', 'a'], ['CAS', '4', 'k1', 'b', '10', '11'], ['GET', '5', 'k1', 'b'], ['GET', '5', 'k2', 'b']],)

Expected Output: ['-5', '7', 'true', '11', '']

Explanation: Different keys and fields are independent, and negative integer values are supported.

Input: ([['SET', '5', 'k', 'f', '1'], ['SET', '5', 'k', 'f', '2'], ['GET', '5', 'k', 'f'], ['CAD', '5', 'k', 'f', '1'], ['CAD', '5', 'k', 'f', '2'], ['GET', '5', 'k', 'f']],)

Expected Output: ['2', 'false', 'true', '']

Explanation: Operations with the same timestamp are still processed in input order.

Hints

  1. A nested dictionary key -> field -> value is enough for this part.
  2. Implement one helper-style lookup behavior and reuse it for GET, CAS, and CAD.

Part 2: Key-Field Store with Sorted Scans

Extend the basic key-field store with scan operations. In addition to SET, GET, CAS, and CAD, support SCAN to list all current fields under a key and SCAN_PREFIX to list only fields whose names begin with a given prefix. Scan results must be deterministic: entries are sorted by field name ascending and formatted as field(value).

Constraints

  • 1 <= len(operations) <= 200000
  • Timestamps are non-decreasing integers encoded as strings.
  • Keys, fields, and prefixes contain lowercase letters; fields do not contain commas or parentheses.
  • Values fit in a signed 32-bit integer.
  • Scan output must be sorted by field name ascending.

Examples

Input: ([['SET', '1', 'profile', 'name', '5'], ['SET', '2', 'profile', 'age', '30'], ['SET', '3', 'profile', 'zip', '90210'], ['SCAN', '4', 'profile'], ['SCAN_PREFIX', '5', 'profile', 'z'], ['SCAN_PREFIX', '6', 'profile', 'na']],)

Expected Output: ['age(30),name(5),zip(90210)', 'zip(90210)', 'name(5)']

Explanation: SCAN sorts fields alphabetically. Prefix scans include only matching field names.

Input: ([['SCAN', '1', 'missing'], ['SCAN_PREFIX', '2', 'missing', 'a'], ['GET', '3', 'missing', 'f']],)

Expected Output: ['', '', '']

Explanation: Scanning or reading a missing key returns an empty output string.

Input: ([['SET', '1', 'k', 'apple', '1'], ['SET', '2', 'k', 'apricot', '2'], ['SET', '3', 'k', 'banana', '3'], ['CAD', '4', 'k', 'banana', '3'], ['SCAN_PREFIX', '5', 'k', 'ap'], ['CAS', '6', 'k', 'apple', '1', '9'], ['SCAN', '7', 'k']],)

Expected Output: ['true', 'apple(1),apricot(2)', 'true', 'apple(9),apricot(2)']

Explanation: Deleted fields disappear from scans, and successful CAS changes the displayed value.

Input: ([['SET', '1', 'k', 'x', '4'], ['SCAN_PREFIX', '2', 'k', '']],)

Expected Output: ['x(4)']

Explanation: An empty prefix matches every field.

Hints

  1. A scan is just a filtered view of the current dictionary for one key.
  2. Sort field names before formatting; test the prefix against the field name, not against the final formatted string.

Part 3: Key-Field Store with TTL Expiration

Extend the scanned key-field store with per-write TTL. A value written at timestamp t with ttl is visible exactly for times x where t <= x < t + ttl. Support all previous commands plus SET_TTL and CAS_TTL. Reads, scans, and compare operations must treat expired values as missing. Non-TTL SET and successful non-TTL CAS write permanent values.

Constraints

  • 1 <= len(operations) <= 200000
  • Timestamps are non-decreasing integers encoded as strings.
  • 1 <= ttl <= 1000000000 for TTL writes.
  • Keys, fields, and prefixes contain lowercase letters; fields do not contain commas or parentheses.
  • Values fit in a signed 32-bit integer.

Examples

Input: ([['SET_TTL', '1', 'k', 'f', '10', '5'], ['GET', '1', 'k', 'f'], ['GET', '5', 'k', 'f'], ['GET', '6', 'k', 'f']],)

Expected Output: ['10', '10', '']

Explanation: The value is visible at timestamps 1 through 5, but not at timestamp 6.

Input: ([['SET_TTL', '1', 'k', 'f', '1', '3'], ['GET', '3', 'k', 'f'], ['SET', '4', 'k', 'f', '2'], ['GET', '100', 'k', 'f']],)

Expected Output: ['1', '2']

Explanation: The TTL value expires at timestamp 4, then a permanent SET overwrites it.

Input: ([['SET_TTL', '1', 'k', 'f', '5', '2'], ['CAS', '3', 'k', 'f', '5', '6'], ['SET_TTL', '4', 'k', 'f', '7', '10'], ['CAS_TTL', '5', 'k', 'f', '7', '8', '2'], ['GET', '6', 'k', 'f'], ['GET', '7', 'k', 'f']],)

Expected Output: ['false', 'true', '8', '']

Explanation: The first CAS fails because the old value expired. CAS_TTL then writes 8, which expires at timestamp 7.

Input: ([['SET_TTL', '1', 'k', 'a', '1', '10'], ['SET_TTL', '2', 'k', 'b', '2', '3'], ['SET', '3', 'k', 'c', '3'], ['SCAN', '4', 'k'], ['SCAN', '5', 'k'], ['SCAN_PREFIX', '6', 'k', 'b']],)

Expected Output: ['a(1),b(2),c(3)', 'a(1),c(3)', '']

Explanation: Field b expires at timestamp 5, so it is absent from later scans.

Input: ([['SET_TTL', '10', 'k', 'f', '99', '1'], ['GET', '10', 'k', 'f'], ['GET', '11', 'k', 'f'], ['CAD', '12', 'k', 'f', '99']],)

Expected Output: ['99', '', 'false']

Explanation: A ttl of 1 makes the value visible only at its write timestamp; after expiration, CAD fails.

Hints

  1. Store an expiration time together with each current value. Permanent writes can use a very large expiration time.
  2. The interval is half-open: a value with write time t and ttl is already expired at timestamp t + ttl.

Part 4: Time-Travel Key-Field Store with TTL

Build the full time-travel key-field store. Support SET, GET, CAS, CAD, SCAN, SCAN_PREFIX, SET_TTL, CAS_TTL, and GET_WHEN. GET_WHEN asks for the value of a key-field pair as it was visible at an earlier at_timestamp, considering all historical writes, successful compare updates, deletions, and TTL expiration. Timestamps of operations are non-decreasing, and at_timestamp is never greater than the operation timestamp.

Constraints

  • 1 <= len(operations) <= 200000
  • Timestamps are non-decreasing integers encoded as strings.
  • For GET_WHEN, at_timestamp <= timestamp.
  • 1 <= ttl <= 1000000000 for TTL writes.
  • If multiple updates to the same field have the same timestamp, later commands in the input are considered later for subsequent queries at that timestamp.
  • Keys, fields, and prefixes contain lowercase letters; fields do not contain commas or parentheses.

Examples

Input: ([['SET', '1', 'k', 'f', '10'], ['SET', '3', 'k', 'f', '20'], ['GET_WHEN', '4', 'k', 'f', '2'], ['GET_WHEN', '4', 'k', 'f', '3'], ['GET', '4', 'k', 'f'], ['CAD', '5', 'k', 'f', '20'], ['GET_WHEN', '6', 'k', 'f', '4'], ['GET_WHEN', '6', 'k', 'f', '5'], ['GET', '6', 'k', 'f']],)

Expected Output: ['10', '20', '20', 'true', '20', '', '']

Explanation: Historical queries before the deletion still see 20; queries at or after the deletion see missing.

Input: ([['SET_TTL', '10', 'k', 'f', '7', '5'], ['GET_WHEN', '12', 'k', 'f', '10'], ['GET_WHEN', '16', 'k', 'f', '14'], ['GET_WHEN', '16', 'k', 'f', '15'], ['GET', '16', 'k', 'f'], ['SET', '20', 'k', 'f', '9'], ['GET_WHEN', '21', 'k', 'f', '16'], ['GET_WHEN', '21', 'k', 'f', '20']],)

Expected Output: ['7', '7', '', '', '', '9']

Explanation: The TTL write is visible for times 10 through 14 only. A later permanent write does not change history at timestamp 16.

Input: ([['SET', '1', 'k', 'a', '1'], ['CAS_TTL', '2', 'k', 'a', '1', '2', '3'], ['GET_WHEN', '4', 'k', 'a', '1'], ['GET_WHEN', '4', 'k', 'a', '2'], ['GET_WHEN', '5', 'k', 'a', '5'], ['CAS', '5', 'k', 'a', '2', '3'], ['SET_TTL', '6', 'k', 'a', '4', '10'], ['CAD', '7', 'k', 'a', '4'], ['GET_WHEN', '8', 'k', 'a', '6'], ['GET_WHEN', '8', 'k', 'a', '7']],)

Expected Output: ['true', '1', '2', '', 'false', 'true', '4', '']

Explanation: CAS_TTL creates a historical TTL version. The CAS at timestamp 5 fails because that version has expired. The later delete is represented in history.

Input: ([['SET_TTL', '1', 'k', 'b', '2', '5'], ['SET', '2', 'k', 'a', '1'], ['SCAN', '3', 'k'], ['SCAN', '6', 'k'], ['GET_WHEN', '7', 'k', 'b', '5'], ['GET_WHEN', '7', 'k', 'b', '6'], ['SCAN_PREFIX', '7', 'k', 'b']],)

Expected Output: ['a(1),b(2)', 'a(1)', '2', '', '']

Explanation: Current scans respect TTL expiration, while GET_WHEN can still inspect earlier visible times.

Input: ([['GET_WHEN', '1', 'missing', 'f', '1'], ['SET', '2', 'k', 'f', '1'], ['SET', '2', 'k', 'f', '2'], ['GET_WHEN', '2', 'k', 'f', '2'], ['CAD', '2', 'k', 'f', '2'], ['GET_WHEN', '2', 'k', 'f', '2']],)

Expected Output: ['', '2', 'true', '']

Explanation: This edge case covers missing history and multiple updates with the same timestamp processed in order.

Hints

  1. Keep an append-only version list for each key-field pair. Include tombstone versions for successful deletes.
  2. For a historical read, binary search for the last version with write_timestamp <= at_timestamp, then check whether it was a deletion or expired by at_timestamp.
Last updated: Jun 26, 2026

Loading coding console...

PracHub

Master your tech interviews with 8,000+ real questions from top companies.

Product

  • Questions
  • Learning Tracks
  • Interview Guides
  • Resources
  • Premium
  • For Universities
  • Student Access

Browse

  • By Company
  • By Role
  • By Category
  • Topic Hubs
  • SQL Questions
  • Compare Platforms
  • Discord Community

Support

  • support@prachub.com
  • (916) 541-4762

Legal

  • Privacy Policy
  • Terms of Service
  • About Us

© 2026 PracHub. All rights reserved.

Related Coding Questions

  • Calculate Bowling Game Score - Tradedesk (medium)
  • Implement a Cloud Storage Service - Tradedesk (medium)
  • Implement monotonic-array linear interpolation - Tradedesk (easy)