In-Memory Database with Backup and Restore

Complete the function below. The function receives the full standard input as a single string and must return the exact standard output lines for the described problem.

Original prompt

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

Complete solveInMemoryDatabaseBackupRestore. It has one parameter, String input, containing the full stdin payload. Return the stdout payload as an array of lines, without trailing newline characters.