Coinbase OA 面试真题解析：Sandbox Tests｜In-Memory Database 字段查询与 TTL/备份恢复

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.

• set(self, key: str, field: str, value: str) -> None — 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.
• get(self, key: str, field: str) -> str | None — should return the value contained within field of the record associated with key. If the record or the field doesn’t exist, should return None.
• delete(self, key: str, field: str) -> bool — 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.

Examples

The example below shows how these operations should work (the section is scrollable to the right):

Level 2

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

• scan(self, key: str) -> list[str] — 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>)", ...], where fields are sorted lexicographically. If the specified record does not exist, returns an empty list.
• scan_by_prefix(self, key: str, prefix: str) -> list[str] — 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.

Examples

The example below shows how these operations should work (the section is scrollable to the right):

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.

Notes:

• 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.

• set_at(self, key: str, field: str, value: str, timestamp: int) -> None — should insert a field-value pair or updates the value of the field in the record associated with key.
• set_at_with_ttl(self, key: str, field: str, value: str, timestamp: int, ttl: int) -> None — 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).
• delete_at(self, key: str, field: str, timestamp: int) -> bool — the same as delete, but with timestamp of the operation specified. Should return True if the field existed and was successfully deleted and False if the key didn’t exist.
• get_at(self, key: str, field: str, timestamp: int) -> str | None — the same as get, but with timestamp of the operation specified.
• scan_at(self, key: str, timestamp: int) -> list[str] — the same as scan, but with timestamp of the operation specified.
• scan_by_prefix_at(self, key: str, prefix: str, timestamp: int) -> list[str] — the same as scan_by_prefix, but with timestamp of the operation specified.

Examples

The examples below show how these operations should work (the section is scrollable to the right):

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.

• backup(self, timestamp: int) -> int — 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 (the duration between the timestamp of this operation and their initial timestamp). Returns the number of non-empty non-expired records in the database.
• restore(self, timestamp: int, timestamp_to_restore: int) -> None — should restore the database from the latest backup before or at timestamp_to_restore. It’s guaranteed that a backup before or at timestamp_to_restore 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 ttl at backup.

Examples

The examples below show how these operations should work (the section is scrollable to the right):

Execution time limit: 3 seconds

Memory limit: 4g

这道 Coinbase OA 的题目要求你实现一个带层级能力的内存数据库：Level 1 需要支持按 key/field 的增删查，Level 2 在此基础上增加按字典序排序的 scan 和前缀过滤 scan_by_prefix，Level 3 再引入严格递增的时间戳与 TTL，到期字段在查询时必须自动失效，Level 4 还要支持 backup/restore，并且恢复后要根据备份时剩余 TTL 重新计算过期时间。做题关键是用哈希表保存记录，再为每个 field 记录值、过期时间和历史版本信息；查询时先清理过期数据，再按字段名排序输出，恢复时则需要从最近一次不晚于目标时间的备份快照重建状态。