How do I practice coding and algorithm questions?

Use PracHub's coding console to write, test, and debug your solutions in Python or JavaScript. View hints, test against sample inputs, and compare with official solutions.

What difficulty level is this coding question?

This is a medium difficulty Coding & Algorithms question, commonly asked during Take-home Project rounds at Ziprecruiter.

What role is this question designed for?

This question is commonly asked for Software Engineer candidates at Ziprecruiter during technical interviews.

Implement an in-memory storage with TTL and scans

Quick Overview

This question evaluates implementation of an in-memory two-level key->field->value store with TTL semantics, lexicographic scans and prefix filtering, and time-travel reads, covering competencies in data structures, time-based expiry handling, and maintaining correct state across monotonic timestamps.

Company: Ziprecruiter

Role: Software Engineer

Category: Coding & Algorithms

Difficulty: medium

Interview Round: Take-home Project

## Problem Implement an in-memory storage system similar to a tiny key–field–value database. - Data model: a **2-level map** `key -> field -> value`. - Each operation includes a **timestamp** `ts` (non-decreasing across the input). - A `(key, field)` entry may optionally have a **TTL** (time-to-live), after which it is considered **expired** and must behave as if it does not exist. You will be given a sequence of queries/commands. Process them in order and return outputs for the commands that produce an output. ## Commands Assume all `key`, `field`, `value`, `prefix` are non-empty strings without spaces; `ts` and `ttl` are integers. ### Basic operations (Level 1) 1. `SET ts key field value` - Set `value` for `(key, field)` at time `ts`. - This write has **no TTL** (never expires) and overwrites any previous value/TTL. 2. `GET ts key field` - Return the current value of `(key, field)` at time `ts`. - If missing or expired, return an empty string `""`. 3. `COMPARE_AND_SET ts key field expected newValue` - If the current (non-expired) value equals `expected`, set it to `newValue` (no TTL) and return `"true"`. - Otherwise return `"false"`. 4. `COMPARE_AND_DELETE ts key field expected` - If the current (non-expired) value equals `expected`, delete the field and return `"true"`. - Otherwise return `"false"`. ### Scans (Level 2) 5. `SCAN ts key` - Return all non-expired fields for `key`, **sorted lexicographically by field name**. - Format each as `field(value)` and join with commas, e.g. `a(1),b(2)`. - If `key` has no non-expired fields, return `""`. 6. `SCAN_BY_PREFIX ts key prefix` - Same as `SCAN`, but include only fields whose name starts with `prefix`. ### TTL support (Level 3) 7. `SET_WITH_TTL ts key field value ttl` - Set `value` for `(key, field)` at time `ts` with expiration time `expireAt = ts + ttl`. - The entry is considered valid for timestamps `t` such that `ts <= t < expireAt`. - Overwrites any previous value/TTL. **TTL rule:** At timestamp `ts`, an entry is visible only if it exists and is not expired at `ts`. ### Time-travel queries (Level 4 / advanced) 8. `GET_AT ts key field atTs` - Return the value that `(key, field)` had at time `atTs` (with TTL and deletes respected). - If it did not exist or was expired at `atTs`, return `""`. - You may assume `atTs <= ts`. ## Input / Output - Input: `queries`, a list where each element is a list of strings describing one command (tokens in the order shown above). - Output: a list of strings containing the results of each command that produces output: - `GET`, `COMPARE_AND_SET`, `COMPARE_AND_DELETE`, `SCAN`, `SCAN_BY_PREFIX`, `GET_AT`. - `SET` and `SET_WITH_TTL` produce no output. ## Constraints (typical interview scale) - `1 <= len(queries) <= 100000` - Timestamps are non-decreasing. - Total length of all strings is manageable in memory. Implement the function that processes the queries and returns the output list.

Quick Answer: This question evaluates implementation of an in-memory two-level key->field->value store with TTL semantics, lexicographic scans and prefix filtering, and time-travel reads, covering competencies in data structures, time-based expiry handling, and maintaining correct state across monotonic timestamps.

Process key-field-value database commands with TTL, scans, compare-and-set/delete, and historical get-at queries.

Examples

Input: ([['SET', '1', 'k', 'a', '1'], ['GET', '2', 'k', 'a'], ['COMPARE_AND_SET', '3', 'k', 'a', '1', '2'], ['GET', '4', 'k', 'a']],)

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

Explanation: Set/get/CAS.

Input: ([['SET_WITH_TTL', '1', 'k', 'a', 'v', '3'], ['GET', '3', 'k', 'a'], ['GET', '4', 'k', 'a'], ['GET_AT', '5', 'k', 'a', '2']],)

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

Explanation: TTL and history.

Input: ([['SET', '1', 'k', 'b', '2'], ['SET', '2', 'k', 'a', '1'], ['SCAN', '3', 'k'], ['SCAN_BY_PREFIX', '3', 'k', 'a'], ['COMPARE_AND_DELETE', '4', 'k', 'a', '1'], ['SCAN', '5', 'k']],)

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

Explanation: Scans and delete.

Quick Overview