How should I practice Temporal Key-Field Database with Prefix Scans?

Start by reading the full statement, solve the visible examples, then compare the pattern against related Trade Desk online assessment problems in FastPrep.

Is Temporal Key-Field Database with Prefix Scans associated with Trade Desk?

FastPrep tags this as a Trade Desk online assessment coding practice problem when the problem catalog has that company and stage context.

Problem · Design

Temporal Key-Field Database with Prefix Scans

Learn this problem

● Medium

Trade DeskFULLTIMEOA

Problem statement

Implement a temporal in-memory database whose records are identified by a string key. Each record contains string field-to-value pairs.

You are given operations in strictly increasing timestamp order. Every operation is an array of strings whose second element is its decimal timestamp:

["SET", timestamp, key, field, value]: set or replace the field with a value that does not expire.
["SET_WITH_TTL", timestamp, key, field, value, ttl]: set or replace the field. The new value is live during the half-open interval [timestamp, timestamp + ttl).
["DELETE", timestamp, key, field]: remove the field if it is live at this timestamp.
["SCAN", timestamp, key]: list every live field in the record.
["SCAN_BY_PREFIX", timestamp, key, prefix]: list only the live fields whose names begin with prefix.

A later write to the same key and field replaces both its value and its expiration. In particular, SET replaces any previous TTL value with a non-expiring value.

Return one string array for every input operation, preserving operation order:

Both write operations return ["true"].
DELETE returns ["true"] if a live field was removed, or ["false"] otherwise.
A scan returns one field(value) string per matching live field, sorted lexicographically by field. A scan with no matches returns an empty array.

Every operation observes expiration at its own timestamp. Expired values never appear in scans and cannot be deleted. Historical reads are outside this exercise.

Function

processTemporalDatabase(operations: String[][]) → String[][]

Examples

Example 1

operations = [["SET","1","user","name","Ada"],["SET","2","user","city","Paris"],["SCAN","3","user"],["SCAN_BY_PREFIX","4","user","na"],["DELETE","5","user","city"],["SCAN","6","user"]]return = [["true"],["true"],["city(Paris)","name(Ada)"],["name(Ada)"],["true"],["name(Ada)"]]

The first scan sorts city before name. The prefix scan keeps only name, and deleting city removes it from the final scan.

Example 2

operations = [["SET_WITH_TTL","10","job","state","queued","5"],["SCAN","14","job"],["SCAN","15","job"],["DELETE","16","job","state"]]return = [["true"],["state(queued)"],[],["false"]]

The TTL value is live on [10,15). It appears at timestamp 14, is expired at timestamp 15, and therefore cannot be deleted later.

Example 3

operations = [["SET_WITH_TTL","1","cache","aa","old","3"],["SET","2","cache","aa","fresh"],["SET_WITH_TTL","3","cache","ab","short","2"],["SCAN_BY_PREFIX","4","cache","a"],["SCAN","5","cache"]]return = [["true"],["true"],["true"],["aa(fresh)","ab(short)"],["aa(fresh)"]]

The ordinary write at timestamp 2 replaces aa and removes its old expiration. Field ab expires exactly at timestamp 5.

Constraints

1 <= operations.length <= 2000.
Every operation uses one of the five supported operation types and has the corresponding number of string elements.
Timestamps are decimal integers from 1 through 10^9 and are strictly increasing.
Every TTL is a decimal integer from 1 through 10^9; timestamp + ttl fits in a signed 64-bit integer.
Keys, fields, values, and prefixes contain from 1 through 40 letters or digits.