In-Memory Database with Backup and Restore

Problem: In-Memory Database with Backup and Restore Build a toy core-logic, purely in-memory key-value database (no UI/framework), using only the standard library. You must process input commands and output the result for each command. Data Model The database is a mapping key -> value, both strings. All data is in memory only. Commands Implement at least the following commands (the interview note says BACKUP and RESTORE were tested): SET key value Set key to value (overwrite allowed). Output: "OK" GET key If key exists output its value, else output "NULL". DELETE key Delete key. If deleted output "OK", else output "NULL". BACKUP Create a snapshot of the current database state. Output: an integer backup_id (starting from 1, increasing). RESTORE backup_id Restore database state to the snapshot identified by backup_id. If backup_id exists: restore and output "OK"; otherwise output "NULL". Input Format First line: integer n, number of commands. Next n lines: one command per line. Output Format Output one line per command, the command result. Constraints 1 <= n <= 2 * 10^5 key, value are non-empty strings with no spaces. Implement efficiently: BACKUP/RESTORE should not deep-copy the entire map on each backup (consider structural sharing, incremental snapshots, copy-on-write, or versioning). Sample Tests Test 1 Input: 7 SET a 1 BACKUP SET a 2 GET a RESTORE 1 GET a DELETE a Output: OK 1 OK 2 OK 1 OK Test 2 Input: 5 GET missing RESTORE 99 SET k v BACKUP RESTORE 1 Output: NULL NULL OK 1 OK Test 3 Input: 8 SET x 10 SET y 20 BACKUP DELETE x GET x RESTORE 1 GET x GET y Output: OK OK 1 OK NULL OK 10 20 Test 4 Input: 6 SET a 1 BACKUP SET b 2 BACKUP RESTORE 1 GET b Output: OK 1 OK 2 OK NULL Test 5 Input: 6 SET a 1 BACKUP SET a 3 BACKUP RESTORE 2 GET a Output: OK 1 OK 2 OK 3 Example Input 7 SET a 1 BACKUP SET a 2 GET a RESTORE 1 GET a DELETE a Output OK 1 OK 2 OK 1 OK