Provided Interface

class FileSystem:
    def save_blob(self, data: bytes) -> None:
        """Write bytes to the file system."""
        pass

    def get_blob(self) -> bytes:
        """Read bytes from the file system."""
        pass

# Supplied utility functions
def serialize_int(value: int) -> bytes:
    """Encode an integer as bytes."""
    pass

def deserialize_int(data: bytes) -> int:
    """Decode bytes as an integer."""
    pass

def serialize_str(value: str) -> bytes:
    """Encode a string as bytes."""
    pass

def deserialize_str(data: bytes) -> str:
    """Decode bytes as a string."""
    pass

Required Implementation

Create a KVStore class with these operations:

class KVStore:
    def __init__(self, file_system: FileSystem):
        """Set up the store with a file-system object."""
        pass

    def put(self, key: str, value: str) -> None:
        """Add or replace a key-value pair in memory."""
        pass

    def get(self, key: str) -> str:
        """Return the value associated with a key."""
        pass

    def shutdown(self) -> None:
        """Encode the complete in-memory store and persist it."""
        pass

    def restore(self) -> None:
        """Read the persisted representation and rebuild the store."""
        pass

Example Usage

fs = FileSystem()
store = KVStore(fs)

store.put("user", "Ada:LovE")
store.put("location", "San,Jose")
store.put("line\nbreak", "left=right")

store.shutdown()

reloaded = KVStore(fs)
reloaded.restore()

assert reloaded.get("user") == "Ada:LovE"
assert reloaded.get("location") == "San,Jose"
assert reloaded.get("line\nbreak") == "left=right"

Each assertion checks that punctuation and newlines survive the persistence round trip without alteration.

Additional Examples

Input:

store = KVStore(fs)
store.put("", "")
store.shutdown()
restored = KVStore(fs)
restored.restore()
restored.get("")

Output:

""

An empty key and an empty value are both valid and must remain distinguishable from missing data.

Input:

store = KVStore(fs)
store.put("emoji", "☕")
store.put("path", "a:b,c=d")
store.shutdown()
restored = KVStore(fs)
restored.restore()

Output:

restored.get("emoji") == "☕"
restored.get("path") == "a:b,c=d"

The restored values retain Unicode characters and all delimiter characters.

Key Challenges

1. Separators can occur in the data. A format such as key:value cannot safely represent a key like part:2 or a value containing =.
2. Escaping is easy to get wrong. A backslash-based escaping scheme requires unambiguous rules for both escaping and unescaping every special character.
3. Content is unrestricted. A key or value may include colons, commas, equals signs, line breaks, quotes, arbitrary Unicode, and, in some implementations, null bytes.

Test Cases to Consider

• An empty dictionary
• Empty keys and empty values
• Separators such as :, ,, and = inside keys or values
• Embedded newlines
• Unicode text
• Very large strings
• Several key-value pairs
• Repeated put, shutdown, and restore operations

Follow-up

Suppose no individual file may contain more than 1 KB. How would you extend the design so callers can persist and restore stores whose serialized form is larger than that limit, without needing to know how many files are involved?

Requirements

• Every file must contain no more than 1024 bytes.
• The public store behavior should not depend on the number of files used internally.
• Persisting and reloading must reconstruct the same key-value data.
• Serialized stores larger than 1 KB must be supported.

Design Considerations

Chunk Boundaries

• Is splitting at arbitrary byte offsets sufficient?
• Would preserving character boundaries matter when the encoded text uses multi-byte UTF-8 sequences?

Metadata Storage

• How will the system record the number of chunks?
• If chunk sizes can vary, is additional size information needed?
• Should metadata be written before the chunks or after them to reduce the risk of exposing an incomplete snapshot?

Edge Cases

• The final chunk will often be shorter than 1 KB.
• The metadata representation must also fit within the per-file limit.
• An empty store still needs a well-defined persisted representation.

File Naming

Use a predictable ordering scheme such as chunk_0, chunk_1, chunk_2, and a separate metadata file such as metadata or _meta.

Updated Interface

The file-system abstraction now addresses files by name:

from typing import List

class FileSystem:
    def save_blob(self, filename: str, data: bytes) -> None:
        """Write bytes to the named file."""
        pass

    def get_blob(self, filename: str) -> bytes:
        """Read bytes from the named file."""
        pass

    def list_files(self) -> List[str]:
        """Return available file names; useful for cleanup or diagnostics."""
        pass

Test Cases for Part 2

• A store that occupies less than 1 KB
• A serialized representation exactly 1024 bytes long
• A representation just over 1 KB
• A store spanning many chunks, such as approximately 8 KB
• An empty store
• Verification that chunks are reassembled in their original order
• A final chunk smaller than the maximum size