Implement Simple Database
Instructions
You are asked to design and implement a simple in-memory database that supports multiple users, record storage, querying, and compression operations.
Requirements
Design and implement a class Database that simulates a small in-memory database supporting multiple users, tables, and records.
Each user has limited storage capacity, and each record consumes a certain number of bytes.
The system should support record creation, copying, searching, compression, decompression, and user capacity management.
All operations occur in memory only — there is no need to read or write any real files.
Interfaces
class Database:
def __init__(self):
"""
Initializes the in-memory database.
The system starts with a default 'root' user who has unlimited storage.
"""
pass
def create_user(self, user_id: str, capacity: int) -> str:
"""
Creates a new user with a storage limit (in bytes).
Returns "true" if the user was created successfully,
or "false" if the user already exists.
"""
def create_table(self, table_name: str) -> str:
"""
Creates a new table in the database.
Returns "true" if created successfully,
or "false" if the table already exists.
"""
def insert(self, user_id: str, table_name: str, record_name: str, size: int) -> str:
"""
Inserts a new record into a table under a specific user.
Fails if:
- the table does not exist,
- the record name already exists globally,
- or inserting the record would exceed the user's storage capacity.
Returns the remaining user capacity as a string on success,
or "" (empty string) otherwise.
"""
def copy(self, source: str, target: str) -> str:
"""
Copies an existing record to a new record with a different name.
The new record belongs to the same table and user as the source.
Returns "true" on success or "false" if the source doesn't exist
or the target name already exists.
"""
def info(self, record_name: str) -> str:
"""
Returns "<record_name>(<size>)" if the record exists,
or "" if it does not exist.
"""
def query(self, prefix: str, suffix: str) -> str:
"""
Returns all records whose names start with 'prefix' and end with 'suffix',
formatted as "name1(size1), name2(size2), ...".
Results should be sorted by:
1. descending size, and
2. lexicographically ascending name if sizes are equal.
Returns "" if no matches are found.
"""
def compress(self, user_id: str, record_name: str) -> str:
"""
Compresses a record owned by the given user.
Replaces it with a new record named "<record_name>_Z"
whose size is half the original (no rounding).
Returns the remaining capacity for the user if successful,
or "" otherwise.
Fails if the record doesn't exist, is already compressed,
or compression would exceed capacity.
"""
def decompress(self, user_id: str, record_name: str) -> str:
"""
Decompresses a record ending with "_Z".
Restores it to its original name and doubles its size.
Fails if the decompressed name already exists or exceeds user capacity.
Returns remaining capacity if successful, or "" otherwise.
"""
def update_limit(self, user_id: str, new_capacity: int) -> str:
"""
Updates a user's storage capacity.
If the total record size exceeds the new capacity,
automatically deletes the largest records first
(breaking ties lexicographically by record name)
until the total fits the limit.
Returns the number of deleted records as a string,
or "" if the user does not exist.
"""
Description
Your database should support the following operations:
1, create_user(user_id: str, capacity: int) -> str
Creates a new user with the given storage limit (in bytes). Returns "true" if created successfully or "false" if the user already exists. The special user "root" always exists with unlimited capacity.
2, create_table(table_name: str) -> str
Creates a new table in the system. Returns "true" if successful, "false" if the table already exists.
3, insert(user_id: str, table_name: str, record_name: str, size: int) -> str
Inserts a record owned by the user into the given table. Fails if the table doesn’t exist, record already exists, or user’s remaining capacity is insufficient. Returns the user’s remaining capacity (as string) if successful, or "" otherwise.
4, copy(source: str, target: str) -> str
Copies an existing record to a new record name under the same table and owner. Fails if the source does not exist or the target name is taken. Returns "true" if successful, "false" otherwise.
5, info(record_name: str) -> str
Returns a string "<record_name>(<size>)" if the record exists, or "" otherwise.
6, query(prefix: str, suffix: str) -> str
Finds all records whose names start with prefix and end with suffix. Returns a comma-separated list in the format "r1(size1), r2(size2), ..." sorted by descending size, then lexicographically. Returns an empty string if no matches are found.
7, compress(user_id: str, record_name: str) -> str
Compresses a record (belonging to the user) by replacing it with a new record named record_name_Z, whose size is exactly half of the original (no rounding). Returns the remaining capacity for the user if successful, or "" otherwise. Fails if the record doesn’t exist, is already compressed, or compression would exceed capacity.
8, decompress(user_id: str, record_name: str) -> str
Decompresses a record whose name ends with _Z, restoring it to its original name and doubling its size. Fails if the uncompressed name already exists or the user’s limit would be exceeded. Returns remaining capacity if successful, or "" otherwise.
9, update_limit(user_id: str, new_capacity: int) -> str
Updates the user’s capacity. If total record size exceeds the new capacity, automatically delete the largest records first (lexicographically smaller names break ties) until the size fits. Returns the number of records deleted, or "" if the user does not exist.
Constrains
Record names are globally unique across all tables.
Each record belongs to one user and one table.
The "root" user always exists and has unlimited capacity.
Records ending with _Z are compressed versions and cannot be inserted manually.
When a compressed record is copied, the _Z suffix is preserved.
All returned values must be strings (as specified).
Example 1
Input:
[
"create_user alice 100",
"create_table logs",
"insert alice logs recA 40",
"insert alice logs recB 30",
"compress alice recA",
"query r c",
"update_limit alice 30"
]
Expected Output:
["true", "true", "60", "30", "50", "recA_Z(20), recB(30)", "1"]
Example 2
Input:
[
"create_user alice 100",
"create_user bob 50",
"create_table logs",
"create_table archive",
"insert alice logs recA 40",
"insert alice logs recB 20",
"insert bob archive data1 30",
"copy recA recA_copy",
"info recA_copy",
"query r c",
"compress alice recA",
"info recA_Z",
"decompress alice recA_Z",
"update_limit bob 20",
"compress bob data1",
"copy data1_Z data2_Z",
"query d Z"
]
Output:
[
"true", # create_user alice
"true", # create_user bob
"true", # create_table logs
"true", # create_table archive
"60", # insert recA (100-40)
"40", # insert recB (100-60)
"20", # insert data1 (50-30)
"true", # copy recA -> recA_copy
"recA_copy(40)", # info
"recA(40), recA_copy(40), recB(20)", # query by prefix/suffix
"60", # compress recA -> recA_Z(20)
"recA_Z(20)", # info
"60", # decompress recA_Z back to recA(40)
"1", # update_limit bob -> data1(30) removed
"20", # compress bob data1 (reinserted before)
"true", # copy data1_Z -> data2_Z
"data1_Z(15), data2_Z(15)" # query all compressed records
]
Explanation
Alice and Bob are created with limits 100 B and 50 B.
Two tables logs and archive are created.
Alice inserts two records (40 B, 20 B). Bob inserts one record (30 B).
Copying recA creates recA_copy under the same table and owner.
query r c finds all record names starting with r and ending with c.
Compressing recA halves its size and renames it to recA_Z.
Decompressing restores it to the original size and name.
Bob’s capacity is reduced; one record is removed automatically.
Bob compresses data1 and copies it, producing two _Z entries.
Final query lists all compressed records.