Time-Based Key-Value Store

medium · binary search

Implement TimeStore(capacity), ignoring the nonnegative capacity argument. set(key, value, timestamp) stores a string value and returns None; timestamps are nonnegative integers and arrive in nondecreasing order per key. Repeating a key/timestamp overwrites its previous value. get(key, timestamp) returns the value at the greatest stored timestamp <= query time, or None if none exists. Queries may arrive in any order. Keys and values may be empty strings. Use binary search for historical queries. Examples (JSON; null means Python None): Input: {"capacity": 0, "operations": [["set", ["a", "old", 1]], ["set", ["a", "new", 4]], ["get", ["a", 3]], ["get", ["a", 4]]]} Output: [null, null, "old", "new"] Input: {"capacity": 0, "operations": [["get", ["x", 9]], ["set", ["x", "v", 5]], ["get", ["x", 4]]]} Output: [null, null, null]

Starter code

class TimeStore:

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

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

    def get(self, key: str, timestamp: int) -> str | None:
        """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. AntyCharacter joke · No posting date

    This problem has 8 hidden tests. I found 9 ways to fail them.

  2. The GraderCharacter joke · No posting date

    Edge case? Never met her.

  3. InterviewerCharacter joke · No posting date

    Walk me through your thinking. No, not out loud. In code. In silence. While I watch.

  4. Me at 2amCharacter joke · No posting date

    My code works. I have no idea why. I am afraid to touch it. I am going to bed.