Constraints

• 1 <= len(operations) <= 200000
• The total number of bytes appearing in all keys, values, and serialized blobs is at most 10^6
• Each key and value length is between 0 and 2^32 - 1 bytes
• Average-case O(1) map operations are acceptable; each serialize/deserialize must be linear in the blob size

Examples

Solution

def solution(operations):
    MAGIC = b'KVS1'
    MAX_U32 = (1 << 32) - 1

    def to_bytes(x):
        if isinstance(x, bytes):
            return x
        if isinstance(x, bytearray):
            return bytes(x)
        if isinstance(x, str):
            return x.encode('utf-8')
        raise TypeError('Expected bytes, bytearray, or str')

    def write_u32(n):
        return bytes([
            (n >> 24) & 0xFF,
            (n >> 16) & 0xFF,
            (n >> 8) & 0xFF,
            n & 0xFF,
        ])

    def read_u32(data, pos):
        if pos + 4 > len(data):
            return None, pos
        value = (
            (data[pos] << 24)
            | (data[pos + 1] << 16)
            | (data[pos + 2] << 8)
            | data[pos + 3]
        )
        return value, pos + 4

    def serialize_store(store):
        if len(store) > MAX_U32:
            raise ValueError('Too many entries to serialize')
        parts = [MAGIC, write_u32(len(store))]
        for key, value in store.items():
            if len(key) > MAX_U32 or len(value) > MAX_U32:
                raise ValueError('Key or value too large to serialize')
            parts.append(write_u32(len(key)))
            parts.append(key)
            parts.append(write_u32(len(value)))
            parts.append(value)
        return b''.join(parts)

    def try_deserialize(blob):
        try:
            data = to_bytes(blob)
        except TypeError:
            return False, None

        if len(data) < 8:
            return False, None
        if data[:4] != MAGIC:
            return False, None

        pos = 4
        count, pos = read_u32(data, pos)
        if count is None:
            return False, None

        new_store = {}
        for _ in range(count):
            key_len, pos = read_u32(data, pos)
            if key_len is None or pos + key_len > len(data):
                return False, None
            key = data[pos:pos + key_len]
            pos += key_len

            value_len, pos = read_u32(data, pos)
            if value_len is None or pos + value_len > len(data):
                return False, None
            value = data[pos:pos + value_len]
            pos += value_len

            if key in new_store:
                return False, None
            new_store[key] = value

        if pos != len(data):
            return False, None

        return True, new_store

    store = {}
    result = []

    for op in operations:
        cmd = op[0]

        if cmd == 'put':
            key = to_bytes(op[1])
            value = to_bytes(op[2])
            if len(key) > MAX_U32 or len(value) > MAX_U32:
                raise ValueError('Key or value too large')
            store[key] = value

        elif cmd == 'get':
            key = to_bytes(op[1])
            result.append(store.get(key))

        elif cmd == 'erase':
            key = to_bytes(op[1])
            store.pop(key, None)

        elif cmd == 'serialize':
            result.append(serialize_store(store))

        elif cmd == 'deserialize':
            ok, parsed = try_deserialize(op[1])
            result.append(ok)
            if ok:
                store = parsed

        else:
            raise ValueError('Unknown operation: {}'.format(cmd))

    return result

Time complexity: O(Q + B) average, where Q is the number of map operations and B is the total number of bytes serialized or deserialized. Space complexity: O(M + S), where M is the current store contents and S is the size of the largest blob being parsed or produced.

Hints

1. A delimiter like ':' is unsafe because keys and values may contain arbitrary bytes. Store a fixed-size length before each raw byte sequence.
2. For failure recovery, do not modify the live store while parsing a blob. Decode into a temporary dictionary first, then replace the store only if parsing finishes exactly at the end.