## Problem Simulate an in-memory key-value database with nested transactions. Keys and values are strings. The database begins empty and supports these operations: - `begin`: push a new active transaction. - `get key`: return the value visible through the deepest active transaction, then its ancestors, then permanent storage; return `NULL` if absent. - `set key value`: write in the deepest active transaction. - `count`: return the number of keys in permanent storage only. - `rollback`: discard and end only the deepest active transaction. - `commit`: apply the visible writes from all active transactions to permanent storage and end every active transaction. `begin`, `get`, and `count` may be called with no active transaction. Calling `set`, `rollback`, or `commit` with no active transaction produces `ERROR: No active transaction` and changes no state. To make the stateful task portable, process an array of token arrays and return one output string per operation: ```text ["begin"] -> "OK" ["get", key] -> value or "NULL" ["set", key, value] -> "OK" or the error string ["count"] -> decimal count ["rollback"] -> "OK" or the error string ["commit"] -> "OK" or the error string ``` ### Function Contract Implement `simulateDatabase(operations)` and return the output array. ### Constraints & Assumptions - `0 <= len(operations) <= 200,000`. - Keys and values are nonempty strings that are never the reserved output text `NULL`. - Deletion is not part of this contract. - A nested transaction sees writes from every enclosing transaction. - When several active levels set the same key, the deepest write is visible and is the value committed. - `count` ignores all uncommitted keys and overrides. ### Clarifying Questions to Ask - Does `commit` merge only the top transaction? No, it commits all active transactions and closes them all. - Does `rollback` affect permanent values? No. - Can `get` run outside a transaction? Yes. - Does `count` include keys first created inside an active transaction? No. ```hint Store a write map per transaction depth Visibility searches write maps from newest to oldest before permanent storage. Commit can merge maps in chronological order so deeper overrides win. ``` ```hint Permanent count changes only on commit Because there is no delete operation, the permanent key count is simply the permanent map size. ``` ### Example ```text operations = [ ["begin"], ["set", "color", "blue"], ["begin"], ["set", "color", "green"], ["get", "color"], ["rollback"], ["get", "color"], ["count"], ["commit"], ["count"] ] ``` Return: ```text ["OK", "OK", "OK", "OK", "green", "OK", "blue", "0", "OK", "1"] ``` ### Evaluation Focus - Resolves nested visibility in deepest-to-oldest order. - Rolls back only one level and commits all levels with the correct override order. - Enforces which operations require an active transaction. - Keeps permanent `count` isolated from pending state. - Supports the full operation limit without copying the whole database at each `begin`. ### Extensions to Discuss 1. How would a `delete` tombstone interact with nested visibility and commit? 2. How could `count(value)` be supported efficiently? 3. What synchronization would be needed for multiple concurrent clients with isolated transactions?