How should I practice In-Memory Database?

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

Is In-Memory Database associated with Coinbase?

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

Problem · Design

In-Memory Database

Learn this problem

● Hard

CoinbaseFULLTIMEOA

Problem statement

Implement a simplified in-memory database. The requirements are cumulative: each level includes every operation from the earlier levels.

Level 1: Basic operations

The database contains records identified by string keys. Each record contains string field-value pairs.

SET key field value: insert the field-value pair into the record. Replace the old value if the field already exists, and create the record if needed.
GET key field: return the stored value, or no value if the record or field does not exist.
DELETE key field: remove the field and return whether it existed.

Level 2: Filtering

SCAN key: return every field of the record as field(value), sorted lexicographically by field. Return an empty list if the record does not exist.
SCAN_BY_PREFIX key prefix: return only fields that start with prefix, using the same format and ordering as SCAN.

Level 3: Timestamps and TTL

Timestamped operations are processed in strictly increasing timestamp order. A field set with a time-to-live of ttl at time timestamp is available during [timestamp, timestamp + ttl).

SET_AT, DELETE_AT, GET_AT, SCAN_AT, and SCAN_BY_PREFIX_AT behave like their earlier counterparts at the supplied timestamp.
SET_AT_WITH_TTL inserts or updates a field and sets its TTL beginning at the supplied timestamp.

A test uses either the untimestamped operations or the timestamped alternatives, not both. The earlier operations must remain supported.

Level 4: Backup and restore

BACKUP timestamp: save the current database state, including each active field's remaining TTL. Return the number of non-empty, non-expired records in the database.
RESTORE timestamp timestampToRestore: restore the latest backup whose backup timestamp is at most timestampToRestore. A suitable backup is guaranteed to exist. Recalculate each restored expiring field so that its remaining TTL begins at the restore operation's timestamp.

FastPrep operation format

Complete runInMemoryDatabase. The parameter operations is an array of string arrays. Process the rows in order and return one result row for every operation.

["SET", key, field, value]
["GET", key, field]
["DELETE", key, field]
["SCAN", key]
["SCAN_BY_PREFIX", key, prefix]
["SET_AT", key, field, value, timestamp]
["SET_AT_WITH_TTL", key, field, value, timestamp, ttl]
["DELETE_AT", key, field, timestamp]
["GET_AT", key, field, timestamp]
["SCAN_AT", key, timestamp]
["SCAN_BY_PREFIX_AT", key, prefix, timestamp]
["BACKUP", timestamp]
["RESTORE", timestamp, timestampToRestore]

All timestamps and TTLs are base-10 integer strings. Return an empty row for SET, SET_AT, SET_AT_WITH_TTL, and RESTORE. Return a one-element row for GET or GET_AT when a value exists, and an empty row otherwise. Return ["true"] or ["false"] for delete operations. Scan operations return their formatted fields directly. BACKUP returns the record count as a one-element row containing a decimal string.

Function

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

Examples

Example 1

operations = [["SET","A","B","E"],["SET","A","C","F"],["GET","A","B"],["GET","A","D"],["DELETE","A","B"],["DELETE","A","D"]]return = [[],[],["E"],[],["true"],["false"]]

The two SET operations create fields B and C. GET finds B but not D. Deleting B succeeds, while deleting the missing field D does not.

Example 2

operations = [["SET","A","BC","E"],["SET","A","BD","F"],["SET","A","C","G"],["SCAN_BY_PREFIX","A","B"],["SCAN","A"],["SCAN_BY_PREFIX","B","B"]]return = [[],[],[],["BC(E)","BD(F)"],["BC(E)","BD(F)","C(G)"],[]]

The prefix scan includes BC and BD. A full scan also includes C. Record B does not exist, so its scan result is empty.

Example 3

operations = [["SET_AT_WITH_TTL","A","B","C","1","10"],["BACKUP","3"],["SET_AT","A","D","E","4"],["BACKUP","5"],["DELETE_AT","A","B","8"],["BACKUP","9"],["RESTORE","10","7"],["BACKUP","11"],["SCAN_AT","A","15"],["SCAN_AT","A","16"]]return = [[],["1"],[],["1"],["true"],["1"],[],["1"],["B(C)","D(E)"],["D(E)"]]

RESTORE selects the backup from timestamp 5. At that backup, field B has 6 units of TTL remaining, so restoring at timestamp 10 makes it expire at timestamp 16. Field D does not expire.

Constraints

Every operation uses one of the listed row formats.
Keys, fields, values, and prefixes are strings.
Within a timestamped test, operation timestamps are strictly increasing.
A test does not mix untimestamped database operations with their timestamped alternatives.