Sharded Key-Value Store

medium · stable hashing

Implement ShardedStore(capacity), using capacity >= 1 shards. route(key) returns sum(key.encode('utf-8')) modulo shard count; do not use Python's randomized hash(). put(key, value) stores an integer and returns None; get(key) returns the stored integer or None; delete(key) returns whether the key existed. dump() returns a list of shard dictionaries in shard-index order. Empty and Unicode keys are allowed. The same key must always route to the same shard; shard count never changes. Examples (JSON; null means Python None): Input: {"capacity": 2, "operations": [["put", ["a", 1]], ["put", ["b", 2]], ["dump", []]]} Output: [null, null, [{"b": 2}, {"a": 1}]] Input: {"capacity": 3, "operations": [["route", ["é"]], ["put", ["", 0]], ["get", [""]], ["get", ["missing"]]]} Output: [1, null, 0, null]

Starter code

class ShardedStore:

    def __init__(self, capacity: int):
        """Implement this operation according to the statement."""
        pass

    def route(self, key: str) -> int:
        """Implement this operation according to the statement."""
        pass

    def put(self, key: str, value: int) -> None:
        """Implement this operation according to the statement."""
        pass

    def get(self, key: str) -> int | None:
        """Implement this operation according to the statement."""
        pass

    def delete(self, key: str) -> bool:
        """Implement this operation according to the statement."""
        pass

    def dump(self) -> list[dict]:
        """Implement this operation according to the statement."""
        pass

Loading editor…

Each test has a five-second execution limit. Your practice drafts and solved progress stay in this browser.

Return to the Python compiler