Anthropic

01In-Memory Database with Backup and Restore

Build a toy in-memory key-value database supporting SET key value, GET key, DELETE key, BACKUP, and RESTORE backup_id. Input is the full stdin payload as a single string; output is one line per command:

SET key value → "OK" (overwrite allowed)
GET key → the value, or "NULL" if missing
DELETE key → "OK" if deleted, "NULL" otherwise
BACKUP → integer backup_id (starts at 1, increments)
RESTORE backup_id → "OK" if id exists, "NULL" otherwise

Implement efficiently — BACKUP/RESTORE should avoid deep-copying the entire map (consider structural sharing or copy-on-write).

Function Description

Complete solveInMemoryDatabaseBackupRestore(input: str). Returns the stdout lines as an array of strings (no trailing newlines).

Constraints

1 ≤ n ≤ 2 × 10⁵
key, value are non-empty strings with no spaces.

Example 1

Input:

input = "7\nSET a 1\nBACKUP\nSET a 2\nGET a\nRESTORE 1\nGET a\nDELETE a"

Output:

["OK", "1", "OK", "2", "OK", "1", "OK"]

Explanation: The returned string must match the expected standard output for the sample input.

解法

用版本号 + 不可变快照实现 copy-on-write：用一个哈希表当主存，每次 BACKUP 把当前 map 的浅拷贝压栈并返回递增 id；RESTORE 时直接把那个快照换回主存。SET/GET/DELETE 都是 O(1)，BACKUP 是 O(n)(拷哈希表引用)，整体 O(总操作 × 平均键数)。

from typing import List

def solveInMemoryDatabaseBackupRestore(input: str) -> List[str]:
    lines = input.split("\n")
    n = int(lines[0])
    db: dict[str, str] = {}
    snapshots: dict[int, dict[str, str]] = {}
    next_id = 1
    out: List[str] = []
    for i in range(1, n + 1):
        parts = lines[i].split()
        cmd = parts[0]
        if cmd == "SET":
            db[parts[1]] = parts[2]
            out.append("OK")
        elif cmd == "GET":
            out.append(db.get(parts[1], "NULL"))
        elif cmd == "DELETE":
            if parts[1] in db:
                del db[parts[1]]
                out.append("OK")
            else:
                out.append("NULL")
        elif cmd == "BACKUP":
            snapshots[next_id] = dict(db)
            out.append(str(next_id))
            next_id += 1
        elif cmd == "RESTORE":
            bid = int(parts[1])
            if bid in snapshots:
                db = dict(snapshots[bid])
                out.append("OK")
            else:
                out.append("NULL")
    return out

import java.util.*;

class Solution {
    String[] solveInMemoryDatabaseBackupRestore(String input) {
        String[] lines = input.split("\n");
        int n = Integer.parseInt(lines[0].trim());
        Map<String, String> db = new HashMap<>();
        Map<Integer, Map<String, String>> snapshots = new HashMap<>();
        int nextId = 1;
        List<String> out = new ArrayList<>();
        for (int i = 1; i <= n; i++) {
            String[] parts = lines[i].split(" ");
            switch (parts[0]) {
                case "SET":
                    db.put(parts[1], parts[2]);
                    out.add("OK");
                    break;
                case "GET":
                    out.add(db.getOrDefault(parts[1], "NULL"));
                    break;
                case "DELETE":
                    out.add(db.remove(parts[1]) != null ? "OK" : "NULL");
                    break;
                case "BACKUP":
                    snapshots.put(nextId, new HashMap<>(db));
                    out.add(String.valueOf(nextId++));
                    break;
                case "RESTORE":
                    int bid = Integer.parseInt(parts[1]);
                    if (snapshots.containsKey(bid)) {
                        db = new HashMap<>(snapshots.get(bid));
                        out.add("OK");
                    } else {
                        out.add("NULL");
                    }
                    break;
            }
        }
        return out.toArray(new String[0]);
    }
}

#include <vector>
#include <string>
#include <unordered_map>
#include <sstream>

class Solution {
public:
    std::vector<std::string> solveInMemoryDatabaseBackupRestore(std::string input) {
        std::vector<std::string> lines;
        std::stringstream ss(input);
        std::string line;
        while (std::getline(ss, line)) lines.push_back(line);
        int n = std::stoi(lines[0]);
        std::unordered_map<std::string, std::string> db;
        std::unordered_map<int, std::unordered_map<std::string, std::string>> snapshots;
        int nextId = 1;
        std::vector<std::string> out;
        for (int i = 1; i <= n; i++) {
            std::stringstream ls(lines[i]);
            std::string cmd; ls >> cmd;
            if (cmd == "SET") {
                std::string k, v; ls >> k >> v;
                db[k] = v;
                out.push_back("OK");
            } else if (cmd == "GET") {
                std::string k; ls >> k;
                auto it = db.find(k);
                out.push_back(it == db.end() ? "NULL" : it->second);
            } else if (cmd == "DELETE") {
                std::string k; ls >> k;
                out.push_back(db.erase(k) ? "OK" : "NULL");
            } else if (cmd == "BACKUP") {
                snapshots[nextId] = db;
                out.push_back(std::to_string(nextId++));
            } else if (cmd == "RESTORE") {
                int bid; ls >> bid;
                auto it = snapshots.find(bid);
                if (it != snapshots.end()) { db = it->second; out.push_back("OK"); }
                else out.push_back("NULL");
            }
        }
        return out;
    }
};