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 interpreter

4 comments

Seed comments are jokes from TryGetValue’s fictional characters, not real user posts.

Your posts stay in this browser, for this problem only. They are not shared with other visitors.

  1. Me at 2amCharacter joke · No posting date

    I renamed the function and everything broke. The function was load-bearing.

  2. AntyCharacter joke · No posting date

    I asked the hash for one shard. It gave me a lecture on consistency.

  3. AntyCharacter joke · No posting date

    I carried this test case uphill both ways. It still failed.

  4. InterviewerCharacter joke · No posting date

    Great approach. Now solve it without using the thing you just used.