Implement a Persistent Key-Value Store on Top of a Fixed-Size Block Device

Implement a key-value store on top of a block device. The device is the only storage you have: it holds a fixed number of fixed-size blocks addressed by index, and it can only read or write one whole block at a time. The interviewer supplied a test suite, every test case had to pass, and AI coding tools were not allowed. The report gives only this one-line prompt. The interfaces below are assumptions that make the task concrete; confirm the real ones with the interviewer before coding. ```python class BlockDevice: block_size: int # bytes per block num_blocks: int # blocks are numbered 0 .. num_blocks - 1 def read_block(self, index: int) -> bytes: ... # exactly block_size bytes def write_block(self, index: int, data: bytes) -> None: ... # data is exactly block_size bytes class KVStore: def __init__(self, device: BlockDevice): ... def put(self, key: bytes, value: bytes) -> None: ... # insert, or overwrite an existing key def get(self, key: bytes) -> bytes | None: ... # None when the key is absent def delete(self, key: bytes) -> bool: ... # True when the key existed ``` ```hint Where the index lives If a new KVStore is opened on a device that already holds data, how does it find the existing keys? Decide what has to be on the device, not just in memory. ``` ```hint Values larger than a block A value can be longer than one block. Decide how the blocks of one value are found in order, and how a reader knows where the value ends inside its last block. ``` ```hint Reusing space Deletes and overwrites free blocks. Decide how free blocks are tracked, and in which order an overwrite writes its blocks so that a failure halfway through does not lose the old value. ``` ### Constraints and Clarifications - Not given: the exact BlockDevice interface, the block size, the maximum key and value sizes, whether data must survive reopening the store, whether a crash can interrupt an operation, and whether calls can be concurrent. Ask, or state your assumptions. - Assume keys and values are arbitrary byte strings, and that an empty value is a legal value, distinct from a missing key. - The device's blocks are the only persistent state: anything held only in memory is gone once the store object is discarded. ### Clarifying Questions - What exactly does the device API look like, and is a single block write atomic (after a failure, the block holds either the old or the new bytes)? - Must a new `KVStore` opened on the same device see the data written through an earlier one? - How large can keys and values be relative to the block size, and roughly how many keys will be stored? - What should `put` do when the device is full? - Is the store used from one thread, or must operations be safe under concurrency? - Does the device start zeroed, or can it contain arbitrary bytes? ### What a Strong Answer Covers - Settling the device interface, persistence and failure assumptions before writing code - A concrete on-device layout: metadata, record headers, and how a multi-block value is located and terminated - Free-space tracking and reclamation on delete and overwrite, with defined behavior when the device is full - Rebuilding in-memory state when the store is reopened, and an overwrite order that never exposes a half-written value - Correct byte-level encoding (fixed-width integers, lengths, padding) and tests at block-boundary sizes - The cost of each operation in block reads and writes, and the space overhead per record ### Follow-up Questions - Most values are a few bytes long. How would you avoid spending a whole block on each one? - Opening the store scans every block. How would you make startup fast on a large device? - The device caches writes and may reorder them unless you call a flush. Where do you need flushes for your overwrite and delete to stay safe? - Several threads call `put` and `get` at once. What do you lock, and can readers proceed while a writer is writing?