PracHub
QuestionsPremiumCoachesLearningGuidesInterview Prep

Quick Overview

This question evaluates skills in designing and implementing an in-memory, level-based key-field-value store with lexicographic scanning, time-based versioning, TTL semantics, and efficient mutation operations.

  • medium
  • Meta
  • Coding & Algorithms
  • Software Engineer

Implement an Expiring Record Store

Company: Meta

Role: Software Engineer

Category: Coding & Algorithms

Difficulty: medium

Interview Round: Technical Screen

Implement a level-based in-memory record store. The store contains records identified by a string `key`. Each record contains fields, where each `field` is a string and each `value` is a string. ### Level 1: Basic mutations Implement: - `set(key, field, value)`: Create the record if it does not exist, then set `field` to `value`. - `get(key, field)`: Return the current value for `field`, or `null` if the record or field does not exist. - `delete(key, field)`: Remove `field` from the record. Return `true` if a field was removed, otherwise return `false`. If a record becomes empty, it may be removed from the store. ### Level 2: Scanning Implement: - `scan(key)`: Return all fields for `key`, sorted lexicographically by field name. Format each item as `field(value)`. Return an empty list if the record does not exist. - `scan_by_prefix(key, prefix)`: Return only fields whose names start with `prefix`, sorted lexicographically by field name and formatted as `field(value)`. ### Level 3: Timestamps and TTL Extend the store so fields can be written with timestamps and optional time-to-live values. Implement: - `set_at(key, field, value, timestamp)`: Set the field at `timestamp` with no expiration. - `set_at_with_ttl(key, field, value, timestamp, ttl)`: Set the field at `timestamp`; it is visible for query times `t` such that `timestamp <= t < timestamp + ttl`. - `delete_at(key, field, timestamp)`: Delete the field at `timestamp` if it exists and is not expired at that time. Return `true` if a field was deleted, otherwise return `false`. - `get_at(key, field, timestamp)`: Return the value visible at `timestamp`, or `null` if none exists. - `scan_at(key, timestamp)`: Return all fields visible at `timestamp`, sorted and formatted as in `scan`. - `scan_by_prefix_at(key, prefix, timestamp)`: Return all visible fields at `timestamp` whose names start with `prefix`, sorted and formatted as in `scan_by_prefix`. Assume timestamps passed to timestamped operations are non-decreasing. A later write to the same `(key, field)` replaces the previous value and expiration policy. Expired or deleted fields must not appear in reads or scans.

Quick Answer: This question evaluates skills in designing and implementing an in-memory, level-based key-field-value store with lexicographic scanning, time-based versioning, TTL semantics, and efficient mutation operations.

Part 1: Basic In-Memory Record Store

Implement the core mutation operations of an in-memory record store. Each record is identified by a string `key` and stores string `field -> value` pairs. Process the operations in order and return the result of each operation. Supported operations: `['set', key, field, value]` creates the record if needed and stores the value; `['get', key, field]` returns the current value or `None`; `['delete', key, field]` removes the field and returns `True` if something was removed, otherwise `False`. If a record becomes empty after deletion, remove it from the store.

Constraints

  • 1 <= len(operations) <= 200000
  • Each `key`, `field`, and `value` is a string of length between 1 and 100
  • The total length of all strings in the input is at most 200000
  • All operation names are valid and appear exactly as specified

Examples

Input: [['set', 'user', 'name', 'alice'], ['get', 'user', 'name'], ['set', 'user', 'name', 'bob'], ['get', 'user', 'name'], ['delete', 'user', 'name'], ['get', 'user', 'name']]

Expected Output: [None, 'alice', None, 'bob', True, None]

Explanation: Setting the same field again overwrites the old value.

Input: [['get', 'missing', 'field'], ['delete', 'missing', 'field'], ['set', 'a', 'x', '1'], ['delete', 'a', 'y'], ['get', 'a', 'x']]

Expected Output: [None, False, None, False, '1']

Explanation: Reading or deleting a missing field should safely return `None` or `False`.

Input: [['set', 'r', 'f1', 'v1'], ['set', 'r', 'f2', 'v2'], ['delete', 'r', 'f1'], ['get', 'r', 'f2'], ['delete', 'r', 'f2'], ['get', 'r', 'f2']]

Expected Output: [None, None, True, 'v2', True, None]

Explanation: Deleting the last remaining field removes the record, so later reads return `None`.

Input: [['set', 'k1', 'a', '1'], ['set', 'k2', 'a', '2'], ['get', 'k1', 'a'], ['get', 'k2', 'a'], ['delete', 'k1', 'a'], ['get', 'k2', 'a']]

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

Explanation: Different keys must be stored independently.

Hints

  1. A dictionary from `key` to another dictionary of `field -> value` is enough for all Level 1 operations.
  2. After deleting a field, check whether its record became empty and remove that record too.

Part 2: Record Store with Scanning

Extend the in-memory record store to support scanning. Each record is identified by a string `key` and stores string `field -> value` pairs. Process the operations in order and return the result of each operation. In addition to `set`, `get`, and `delete`, support `['scan', key]`, which returns all fields for that key sorted lexicographically and formatted as `field(value)`, and `['scan_by_prefix', key, prefix]`, which returns only fields whose names start with `prefix`, also sorted and formatted. If a record does not exist, scans return an empty list.

Constraints

  • 1 <= len(operations) <= 200000
  • Each `key`, `field`, `value`, and `prefix` is a string of length between 0 and 100
  • The total length of all strings in the input is at most 200000
  • Fields in scans must be sorted lexicographically by field name

Examples

Input: [['set', 'user', 'name', 'alice'], ['set', 'user', 'age', '30'], ['set', 'user', 'email', 'a@example.com'], ['scan', 'user'], ['scan_by_prefix', 'user', 'e']]

Expected Output: [None, None, None, ['age(30)', 'email(a@example.com)', 'name(alice)'], ['email(a@example.com)']]

Explanation: Scan results must be sorted by field name, not by insertion order.

Input: [['set', 'k', 'apple', '1'], ['set', 'k', 'app', '2'], ['set', 'k', 'banana', '3'], ['scan_by_prefix', 'k', 'app'], ['delete', 'k', 'app'], ['scan_by_prefix', 'k', 'app']]

Expected Output: [None, None, None, ['app(2)', 'apple(1)'], True, ['apple(1)']]

Explanation: Only fields starting with the prefix are returned, still in lexicographic order.

Input: [['scan', 'missing'], ['scan_by_prefix', 'missing', 'a'], ['set', 'm', 'z', '9'], ['scan_by_prefix', 'm', 'a']]

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

Explanation: Scanning a missing record or with a prefix that matches nothing should return an empty list.

Input: [['set', 'r', 'x', '1'], ['delete', 'r', 'x'], ['scan', 'r'], ['get', 'r', 'x']]

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

Explanation: After the only field is deleted, the record is empty and scans should return `[]`.

Hints

  1. Keep the same nested dictionary structure from Part 1, then build scan results from the inner dictionary.
  2. For prefix scans, filter field names first, then sort the matching fields before formatting them.

Part 3: Expiring Record Store with Timestamps and TTL

Implement a timestamped in-memory record store with TTL support. Each record is identified by a string `key`, and each field stores a string value plus an optional expiration time. Process operations in order and return the result of each operation. Timestamps in the input are non-decreasing across the whole operation list. Supported operations: `['set_at', key, field, value, timestamp]` writes a non-expiring value; `['set_at_with_ttl', key, field, value, timestamp, ttl]` writes a value visible exactly when `timestamp <= t < timestamp + ttl`; `['delete_at', key, field, timestamp]` deletes the field only if it exists and is not expired at that time; `['get_at', key, field, timestamp]` returns the visible value or `None`; `['scan_at', key, timestamp]` returns all visible fields sorted and formatted as `field(value)`; `['scan_by_prefix_at', key, prefix, timestamp]` returns only visible fields whose names start with `prefix`, also sorted and formatted. A later write to the same `(key, field)` replaces the previous value and expiration policy.

Constraints

  • 1 <= len(operations) <= 200000
  • The sequence of timestamps across all operations is non-decreasing
  • 1 <= ttl <= 1000000000
  • Each `key`, `field`, `value`, and `prefix` is a string of length between 0 and 100

Examples

Input: [['set_at_with_ttl', 'user', 'token', 'abc', '10', '5'], ['get_at', 'user', 'token', '10'], ['get_at', 'user', 'token', '14'], ['get_at', 'user', 'token', '15'], ['scan_at', 'user', '15']]

Expected Output: [None, 'abc', 'abc', None, []]

Explanation: A TTL write at time 10 with TTL 5 is visible at times 10 through 14, but not at 15.

Input: [['set_at_with_ttl', 'k', 'a', '1', '1', '10'], ['set_at', 'k', 'a', '2', '5'], ['get_at', 'k', 'a', '6'], ['get_at', 'k', 'a', '20'], ['scan_at', 'k', '20']]

Expected Output: [None, None, '2', '2', ['a(2)']]

Explanation: A later write replaces both the old value and the old expiration policy.

Input: [['set_at_with_ttl', 'k', 'a', '1', '2', '3'], ['delete_at', 'k', 'a', '5'], ['set_at', 'k', 'a', '2', '6'], ['delete_at', 'k', 'a', '7'], ['get_at', 'k', 'a', '8']]

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

Explanation: The first delete happens exactly at the expiration boundary, so the field is already expired and cannot be deleted.

Input: [['scan_at', 'missing', '100'], ['set_at', 'user', 'apple', 'red', '1'], ['set_at_with_ttl', 'user', 'app', 'green', '2', '3'], ['set_at', 'user', 'banana', 'yellow', '3'], ['scan_by_prefix_at', 'user', 'app', '4'], ['scan_by_prefix_at', 'user', 'app', '5']]

Expected Output: [[], None, None, None, ['app(green)', 'apple(red)'], ['apple(red)']]

Explanation: The field `app` expires before time 5, while `apple` remains visible.

Hints

  1. Because timestamps never go backward, you do not need full history for each field; keeping only the current value and its expiration time is enough.
  2. On any read, scan, or delete at time `t`, treat a field with `expire_at <= t` as missing, and you can lazily remove it from the store.
Last updated: Jun 13, 2026

Loading coding console...

PracHub

Master your tech interviews with 8,500+ 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

  • Compute Exclusive Execution Times - Meta (medium)
  • Solve Tree Columns And Maze Variants - Meta (medium)
  • Solve Tree Diameter and Palindromic Counts - Meta (medium)
  • Simulate Monster Team Battles - Meta (hard)
  • Solve a Key-Door Corridor Maze - Meta (medium)