Design an in-memory key-value database that supports transactional reads and writes. Expose a class with these operations: - `begin()` starts a transaction and returns a transaction id. - `get(txid, key)` reads the value visible to that transaction. - `set(txid, key, value)` writes a value inside that transaction. - `commit(txid)` attempts to make the transaction's writes visible. - `rollback(txid)` discards the transaction's writes. The interviewer is especially interested in how your design handles conflicting concurrent writes to the same key, and read/write races where two transactions observe stale values and then swap values between keys. ### Constraints & Assumptions - The database is in memory only; durability and crash recovery are out of scope unless the interviewer asks. - Keys and values can be treated as strings. - Transaction ids are generated by the database. - A transaction should read its own writes. - You may choose optimistic or pessimistic concurrency control, but you must explain the trade-offs. ### Clarifying Questions to Ask - Should transactions provide serializable isolation, snapshot isolation, or a weaker guarantee? - Can two transactions write the same key concurrently, or should the second writer block or fail? - Should `commit` return a success/failure result, raise an error, or retry automatically? - Are long-running transactions common, and is starvation acceptable? - Do we need nested transactions, deletes, TTLs, or range scans? ### What a Strong Answer Covers ```premium-lock What a Strong Answer Covers ``` ### Follow-up Questions - How would your design change if `get` outside a transaction must also be supported? - How would you add deletes? - How would you prevent a long transaction from making validation expensive? - How would you test the two-key swap race? - What would need to change to make the database durable?