Implement an in-memory database with record locking
Company: Meta
Role: Software Engineer
Category: Coding & Algorithms
Difficulty: easy
Interview Round: Take-home Project
Implement an in-memory key–record database that supports basic CRUD on fields plus an exclusive lock per record.
You are given a sequence of queries. Each query is an array of strings. Implement a function that processes all queries in order and returns an array of strings containing the outputs of the queries that produce output.
### Data model
- The database contains **records** identified by `recordKey` (string).
- Each record is a map from `field` (string) to `value` (string).
### Locking model
- A record can be **unlocked** or **locked by exactly one user** (`userId`, string).
- A lock applies to the whole record (all its fields).
- **Reads are always allowed**.
- **Writes/deletes are allowed only if** the record is not locked, or it is locked by the same `userId` performing the operation.
### Query types
Each query is one of:
1) `SET recordKey field value userId`
- If the write is allowed, set `recordKey[field] = value` (creating the record if needed) and output `"OK"`.
- Otherwise output `"LOCKED"` and do not change the database.
2) `GET recordKey field`
- Output the value if present, otherwise output an empty string `""`.
3) `DELETE recordKey field userId`
- If the delete is allowed and the field existed, remove it and output `"true"`.
- If the delete is allowed but the field did not exist, output `"false"`.
- If the delete is not allowed due to locking, output `"LOCKED"`.
- If a record becomes empty after deletion, remove the record entirely. If the record is removed, its lock (if any) is also removed.
4) `LOCK recordKey userId`
- If the record does not exist, output `"INVALID"`.
- If the record is unlocked, lock it for `userId` and output `"ACQUIRED"`.
- If the record is already locked by `userId`, output `"ACQUIRED"` (idempotent).
- If the record is locked by a different user, output `"WAIT"`.
5) `UNLOCK recordKey userId`
- If the record does not exist, output `"INVALID"`.
- If the record is locked by `userId`, unlock it and output `"RELEASED"`.
- If the record is unlocked, output `"RELEASED"` (idempotent).
- If the record is locked by a different user, output `"INVALID"`.
### Requirements
- Process queries efficiently (aim for average O(1) per query using hash maps).
- Return outputs **only** for the queries above (all of them produce output in this spec).
### Example
If a record `A` is locked by user `u1`, then `SET A x 5 u2` must output `"LOCKED"`, while `GET A x` still returns the stored value (or empty string if missing).
Quick Answer: This question evaluates proficiency in implementing stateful in-memory data structures, record-level exclusive locking semantics, concurrent access control, and efficient string-keyed CRUD operations.
Implement a function `solution(queries)` that processes a sequence of database commands on an in-memory key-record store.
Each record is identified by a string `recordKey` and stores string fields mapped to string values. In addition to basic CRUD operations, each record may have an exclusive lock owned by exactly one `userId`.
Rules:
- Reads are always allowed.
- Writes and deletes are allowed only when the record is unlocked, or when it is locked by the same `userId` performing the operation.
- Locks apply to the whole record.
- If deleting the last field removes the record entirely, its lock must also be removed.
Supported queries:
1. `SET recordKey field value userId`
- If allowed, set the field value, creating the record if needed, and output `"OK"`.
- Otherwise output `"LOCKED"`.
2. `GET recordKey field`
- Output the stored value, or `""` if the record or field does not exist.
3. `DELETE recordKey field userId`
- If blocked by another user's lock, output `"LOCKED"`.
- Otherwise, if the field existed, delete it and output `"true"`.
- If the field did not exist, output `"false"`.
- If the record becomes empty, remove the record and its lock.
4. `LOCK recordKey userId`
- If the record does not exist, output `"INVALID"`.
- If the record is unlocked, lock it for `userId` and output `"ACQUIRED"`.
- If it is already locked by the same `userId`, output `"ACQUIRED"`.
- If it is locked by a different user, output `"WAIT"`.
5. `UNLOCK recordKey userId`
- If the record does not exist, output `"INVALID"`.
- If the record is unlocked, output `"RELEASED"`.
- If the record is locked by `userId`, unlock it and output `"RELEASED"`.
- If the record is locked by a different user, output `"INVALID"`.
Return a list of output strings in the same order as the queries.
Constraints
- 0 <= len(queries) <= 200000
- Each query has valid syntax and one of the five supported operation names
- All record keys, fields, values, and user IDs are strings
- Aim for average O(1) processing per query using hash maps
Examples
Input: []
Expected Output: []
Explanation: No queries means no outputs.
Input: [["SET", "A", "x", "5", "u1"], ["GET", "A", "x"], ["GET", "A", "y"], ["DELETE", "A", "y", "u1"], ["DELETE", "A", "x", "u1"], ["GET", "A", "x"]]
Expected Output: ["OK", "5", "", "false", "true", ""]
Explanation: Basic create, read, delete-missing-field, delete-existing-field, and reading after the record is removed.
Hints
- Use one hash map for the records themselves, such as recordKey -> {field: value}, and a second hash map for lock ownership, such as recordKey -> userId.
- Be careful when deleting the last field of a record: once the record disappears, any lock for that record must disappear too.