#981

Time Based Key-Value Store

medium· Binary Searchruns: 0

Design a time-based key-value data structure that supports storing multiple values for the same key at different timestamps and retrieving the value at a specific timestamp. Implement set(key, value, timestamp) and get(key, timestamp), where get returns the value with the largest timestamp not greater than the given timestamp, or empty string if no such entry exists.

wpm 0acc 100%time 0:000 / 645

from collections import defaultdict

class TimeMap:
    def __init__(self):
        self.store = defaultdict(list)

    def set(self, key: str, value: str, timestamp: int) -> None:
        self.store[key].append((timestamp, value))

    def get(self, key: str, timestamp: int) -> str:
        entries = self.store.get(key, [])
        left, right = 0, len(entries) - 1
        result = ""
        while left <= right:
            mid = (left + right) // 2
            if entries[mid][0] <= timestamp:
                result = entries[mid][1]
                left = mid + 1
            else:
                right = mid - 1
        return result

click the box to focus · tab inserts 4 spaces · backspace to correct · esc to pause

desktop only

codedrill is a typing game and needs a real keyboard. open this on a laptop or desktop to practice.

you can still browse problems and sections from your phone.