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.
input = "7\nSET a 1\nBACKUP\nSET a 2\nGET a\nRESTORE 1\nGET a\nDELETE a" return = ["OK", "1", "OK", "2", "OK", "1", "OK"]
The returned string must match the expected standard output for the sample input.
Use the limits and requirements stated in the prompt.
public String[] solveInMemoryDatabaseBackupRestore(String input) {
// write your code here
}