Logo
All Interview Questions

Meta Online Assessment -- In Memory KV Store

Requirements

Your task is to implement a simplified version of an in-memory key value store. Plan your design according to the level specifications below:

  • Level 1: In-memory kv tore should support basic operations to get, set compare_and_udpate, compare_and_delete.
  • Level 2: In-memory kv tore should support scan, scanByPrefix
  • Level 3: In-memory kv tore should support TTL (Time-To-Live) configurations on database records.
  • Level 4: In-memory database should support should support time-travel functionality to query any historical point.

Note You will receive a list of queries to the system, and the final output should be an array of strings representing the returned values of all queries. Each query will only call one operation.

(Please notice this is different from the question: In Memory Database )

Level 1

The basic level of the in-memory database contains records with timestamps. Each record can be accessed with a unique identifier key of string type at a specific timestamp. A record may contain several field-value pairs, both of which are of string type.

SET <timestamp> <key> <field> <value> — should insert a field-value pair to the record associated with key at the given timestamp. If the field in the record already exists, replace the existing value with the specified value. If the record does not exist, create a new one. This operation should return an empty string. GET <timestamp> <key> <field> — should return the value contained within field of the record associated with key at the given timestamp. If the record or the field doesn't exist, should return an empty string. COMPARE_AND_UPDATE <timestamp> <key> <field> <expected_value> <new_value> — should update the field value only if the current value matches the expected_value. Returns "true" if updated successfully, "false" otherwise. COMPARE_AND_DELETE <timestamp> <key> <field> <expected_value> — should delete the field only if the current value matches the expected_value. Returns "true" if deleted successfully, "false" otherwise.

Examples

The example below shows how these operations should work:

Queries

queries = [
["SET", "1", "A", "B", "E"],
["SET", "2", "A", "C", "F"],
["GET", "3", "A", "B"],
["GET", "3", "A", "D"],
["COMPARE_AND_UPDATE", "4", "A", "B", "E", "X"],
["COMPARE_AND_DELETE", "5", "A", "C", "F"]
]

Explanations

returns ""; database state at t=1: {"A": {"B": "E"}}
returns ""; database state at t=2: {"A": {"B": "E", "C": "F"}}
returns "E"
returns ""
returns "true"; database state at t=4: {"A": {"B": "X", "C": "F"}}
returns "true"; database state at t=5: {"A": {"B": "X"}}

Level 2

The database should support displaying data based on filters. Introduce an operation to support printing some fields of a record.

  • scan(timestamp, key) — should return a string representing the fields of a record associated with key at the given timestamp. The returned string should be in the following format "<field1>(<value1>), <field2>(<value2>), ...", where fields are sorted lexicographically. If the specified record does not exist, returns an empty string.
  • scanByPrefix(timestamp, key, prefix) — should return a string representing some fields of a record associated with key at the given timestamp. Specifically, only fields that start with prefix should be included. The returned string should be in the same format as in the scan operation with fields sorted in lexicographical order.

Examples

The example below shows how these operations should work

Queries

queries = [
["set", "1", "A", "BC", "E"],
["set", "1", "A", "BD", "F"],
["set", "1", "A", "C", "G"],
["scanByPrefix", "2", "A", "B"],
["scan", "2", "A"],
["scanByPrefix", "2", "B", "B"]
]

Explanations

returns ""; database state: {"A": {"BC": "E"}}
returns ""; database state: {"A": {"BC": "E", "BD": "F"}}
returns ""; database state: {"A": {"BC": "E", "BD": "F", "C": "G"}}
returns "BC(E), BD(F)"
returns "BC(E), BD(F), C(G)"
returns ""

The output should be ["", "", "", "BC(E), BD(F)", "BC(E), BD(F), C(G)", ""].

Level 3

Support TTL (Time-To-Live) settings for records and fields. For each field-value pair in the database, the TTL determines how long that value will persist before being removed. Notes:

Time should always flow forward, so timestamps are guaranteed to strictly increase as operations are executed.

  • setWithTTL(timestamp, key, field, value, ttl) — should insert a field-value pair or update the value of the field in the record associated with key. Also sets its Time-To-Live starting at timestamp to be ttl. The ttl is the amount of time that this field-value pair should exist in the database, meaning it will be available during this interval: [timestamp, timestamp + ttl). This operation should return an empty string.
  • compareAndUpdateWithTTL(timestamp, key, field, expectedValue, newValue, ttl) — should update the field value with TTL only if the current value matches the expectedValue. Returns "true" if updated successfully, "false" otherwise.

Examples

The examples below show how these operations should work

Queries

queries = [
["setWithTTL", "1", "A", "BC", "E", "9"],
["setWithTTL", "5", "A", "BC", "E", "10"],
["set", "5", "A", "BD", "F"],
["scanByPrefix", "14", "A", "B"],
["scanByPrefix", "15", "A", "B"]
]

Explanations

returns ""; database state: {"A": {"BC": "E"}} where {"BC": "E"} expires at timestamp 10
returns ""; database state: {"A": {"BC": "E"}} as field "BC" in record "A" already exists, it was overwritten, and {"BC": "E"} now expires at timestamp 15
returns ""; database state: {"A": {"BC": "E", "BD": "F"}} where {"BD": "F"} does not expire
returns "BC(E), BD(F)"
returns "BD(F)" (BC has expired)

The output should be ["", "", "", "BC(E), BD(F)", "BD(F)"].

Level 4

The database should support time-travel queries to retrieve values at any historical point in time.

  • getValueAt(currentTimestamp, key, field, atTimestamp) — should return the value of the field in the record associated with key as it existed at the specified historical timestamp (atTimestamp). The function searches through all timestamps up to and including atTimestamp to find the most recent value. If the field didn't exist at that time or had expired due to TTL, returns an empty string.

Examples

Queries

queries = [
["set", "1", "A", "B", "v1"],
["set", "5", "A", "B", "v2"],
["setWithTTL", "10", "A", "B", "v3", "5"],
["getValueAt", "20", "A", "B", "3"],
["getValueAt", "20", "A", "B", "7"],
["getValueAt", "20", "A", "B", "12"],
["getValueAt", "20", "A", "B", "16"]
]

Explanations

returns ""; sets "B" to "v1" at timestamp 1
returns ""; updates "B" to "v2" at timestamp 5
returns ""; updates "B" to "v3" at timestamp 10 with TTL=5 (expires at timestamp 15)
returns "v1"; value at timestamp 3 was "v1"
returns "v2"; value at timestamp 7 was "v2"
returns "v3"; value at timestamp 12 was "v3" (not yet expired)
returns ""; value at timestamp 16 had expired (TTL ended at timestamp 15)

The output should be ["", "", "", "v1", "v2", "v3", ""].