In-Memory Database

Your task is to implement a simplified version of an in-memory database. All operations that should be supported by this database are described below.

Solving this task consists of several levels. Subsequent levels are opened when the current level is correctly solved. You always have access to the data for the current and all previous levels.

You are not required to provide the most efficient implementation. Any code that passes the unit tests is sufficient.

Level 1

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

• void set(String key, String field, String value) — should insert a field-value pair to the record associated with key. 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.
• Optional<String> get(String key, String field) — should return the value contained within field of the record associated with key. If the record or the field does not exist, should return Optional.empty().
• boolean delete(String key, String field) — should remove the field from the record associated with key. Returns true if the field was successfully deleted, and false if the key or the field do not exist in the database.

Level 2

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

• List<String> scan(String key) — should return a list of strings representing the fields of a record associated with key. The returned list should be in the following format ["<field_1>(<value_1>)", "<field_2>(<value_2>)", ...], where fields are sorted lexicographically. If the specified record does not exist, returns an empty list.
• List<String> scanByPrefix(String key, String prefix) — should return a list of strings representing some fields of a record associated with key. Specifically, only fields that start with prefix should be included. The returned list should be in the same format as in the scan operation with fields sorted in lexicographical order.

Level 3

Support the timeline of operations and TTL (Time-To-Live) settings for records and fields. Each operation from previous levels now has an alternative version with a timestamp parameter to represent when the operation was executed. For each field-value pair in the database, the TTL determines how long that value will persist before being removed.

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

Each test cannot contain both versions of operations (with and without timestamp). However, you should maintain backward compatibility, so all previously defined methods should work in the same way as before.

• void setAt(String key, String field, String value, int timestamp) — should insert a field-value pair or update the value of the field in the record associated with key.
• void setAtWithTtl(String key, String field, String value, int timestamp, int 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).
• boolean deleteAt(String key, String field, int timestamp) — the same as delete, but with timestamp of the operation specified.
• Optional<String> getAt(String key, String field, int timestamp) — the same as get, but with timestamp of the operation specified.
• List<String> scanAt(String key, int timestamp) — the same as scan, but with timestamp of the operation specified.
• List<String> scanByPrefixAt(String key, String prefix, int timestamp) — the same as scanByPrefix, but with timestamp of the operation specified.

Level 4

The database should be backed up from time to time. Introduce operations to support backing up and restoring the database state based on timestamps. When restoring, ttl expiration times should be recalculated accordingly.

• int backup(int timestamp) — should save the database state at the specified timestamp, including the remaining ttl for all records and fields. Remaining ttl is the difference between their initial ttl and their current lifespan. Returns the number of non-empty non-expired records in the database.
• void restore(int timestamp, int timestampToRestore) — should restore the database from the latest backup before or at timestampToRestore. It is guaranteed that a backup before or at timestampToRestore will exist. Expiration times for restored records and fields should be recalculated according to the timestamp of this operation. Since the database timeline always flows forward, restored records and fields should expire after the timestamp of this operation, depending on their remaining ttls at backup.

FastPrep interface

Complete runInMemoryDatabase. The operations parameter 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]
• ["scanByPrefix", key, prefix]
• ["setAt", key, field, value, timestamp]
• ["setAtWithTtl", key, field, value, timestamp, ttl]
• ["deleteAt", key, field, timestamp]
• ["getAt", key, field, timestamp]
• ["scanAt", key, timestamp]
• ["scanByPrefixAt", key, prefix, timestamp]
• ["backup", timestamp]
• ["restore", timestamp, timestampToRestore]

Timestamps and TTLs are base-10 integer strings. Return an empty row for set, setAt, setAtWithTtl, and restore. Return a one-element row for get or getAt 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 decimal-string row.