Implement a Transactional In-Memory Table
Company: Addepar
Role: Software Engineer
Category: Coding & Algorithms
Difficulty: medium
Interview Round: Technical Screen
# Implement a Transactional In-Memory Table
Implement `process_table(operations)` for an in-memory table whose state maps each row name to a map of column names and string values. The table starts empty and supports at most one active transaction.
Each operation is a list of strings:
- `["BEGIN"]`: start a transaction and capture the current state.
- `["COMMIT"]`: keep all changes made since `BEGIN` and end the transaction.
- `["ROLLBACK"]`: restore the exact state captured by `BEGIN` and end the transaction.
- `["CREATE", row]`: create an empty row.
- `["DELETE", row]`: delete a row and all its cells.
- `["UPDATE", row, column, value]`: set one cell.
- `["REPLACE", find, replacement]`: replace every nonoverlapping literal occurrence of `find` in every cell value. Row and column names do not change.
- `["SHOW"]`: append a canonical serialization of the current table to the output.
Only `CREATE`, `DELETE`, `UPDATE`, and `REPLACE` mutate table data, and they take effect only inside an active transaction. Outside a transaction they are no-ops. Creating an existing row, deleting a missing row, or updating a missing row is also a no-op. `find` is nonempty.
For `SHOW`, sort rows and columns lexicographically. Serialize a row as `row{column=value,...}`, serialize an empty row as `row{}`, join rows with semicolons, and use the empty string for an empty table. Names and values never contain `{`, `}`, `,`, `=`, or `;`.
Input never contains nested `BEGIN`, and `COMMIT` or `ROLLBACK` appears only during an active transaction. These exact edge and serialization rules are pedagogical assumptions added to the source's stated API.
## Function Contract
`process_table(operations: list[list[str]]) -> list[str]`
## Constraints
- `0 <= len(operations) <= 100000`
- Names and values contain printable ASCII characters subject to the delimiter restriction above.
- The total size of all operation strings is at most `1000000` characters.
- No nested or concurrent transaction is present.
## Examples
### Example 1
```text
Input: [
["BEGIN"],
["CREATE", "r"],
["UPDATE", "r", "c", "old"],
["SHOW"],
["UPDATE", "r", "c", "new"],
["ROLLBACK"],
["SHOW"]
]
Output: ["r{c=old}", ""]
```
Rollback restores the empty table that existed at `BEGIN`, including removal of the newly created row.
### Example 2
```text
Input: [
["BEGIN"],
["CREATE", "a"],
["UPDATE", "a", "x", "apple"],
["UPDATE", "a", "y", "pineapple"],
["COMMIT"],
["SHOW"],
["BEGIN"],
["REPLACE", "apple", "pear"],
["SHOW"],
["DELETE", "a"],
["ROLLBACK"],
["SHOW"]
]
Output: ["a{x=apple,y=pineapple}", "a{x=pear,y=pinepear}", "a{x=apple,y=pineapple}"]
```
The replacement is visible inside the second transaction, while rollback restores both original cell values after the intervening delete.
Overview: Implement an in-memory row-and-column table with transactional create, delete, update, find-and-replace, commit, and rollback behavior. The prompt defines one active transaction, complete state restoration, canonical display ordering, boundary no-ops, and deterministic serialization for portable verification.
Read the full Addepar Software Engineer interview experience this question came from
Implement process_table(operations) for an initially empty table that maps row names to column/value maps and permits at most one active transaction. Each operation is one of ["BEGIN"], ["COMMIT"], ["ROLLBACK"], ["CREATE", row], ["DELETE", row], ["UPDATE", row, column, value], ["REPLACE", find, replacement], or ["SHOW"]. BEGIN starts a transaction; COMMIT keeps its changes; ROLLBACK restores the exact state at BEGIN. CREATE, DELETE, UPDATE, and REPLACE mutate data only inside a transaction and otherwise do nothing. Creating an existing row, deleting a missing row, or updating a missing row also does nothing. REPLACE changes every nonoverlapping literal occurrence of find in every cell value; it never changes row or column names, and find is nonempty. SHOW returns a serialization with row and column names sorted lexicographically: each row is row{column=value,...}, rows are joined by semicolons, an empty row is row{}, and an empty table is the empty string.
Constraints
- 0 <= operations.length <= 100,000
- The total size of all operation strings is at most 1,000,000 characters.
- At most one transaction is active; BEGIN is not nested and COMMIT or ROLLBACK occurs only during a transaction.
- REPLACE find strings are nonempty.
- Names and values are printable ASCII and do not contain {, }, comma, =, or semicolon delimiters.
- CREATE, DELETE, UPDATE, and REPLACE outside a transaction are no-ops.
Examples
Input: ([],)
Expected Output: []
Explanation: No operations produce no SHOW results.
Input: ([['SHOW']],)
Expected Output: ['']
Explanation: SHOW serializes an empty table as the empty string.
Hints
- Think about the prior state each successful mutation must restore if the current transaction rolls back.
- Apply rollback records in reverse mutation order.
- Build SHOW output from lexicographically ordered row and column names.