What is the best way to solve Time Based Key Value Store?

The optimized O(n) approach using Binary Search patterns is generally preferred.

상위 150개 인터뷰쉬움

시간 기반 키 값 저장소

'시간 기반 키 값 저장소' 문제에 대한 자세한 가이드 및 Python 구현입니다.

문제 설명

쉬움

서로 다른 타임스탬프에서 동일한 키에 대한 여러 값을 저장하고 특정 타임스탬프에서 키 값을 검색할 수 있는 시간 기반 키-값 데이터 구조를 설계합니다.

TimeMap 클래스를 구현합니다.

- TimeMap() 객체를 초기화합니다.

- set(key: str, value: str, timestamp: int) 주어진 시간 timestamp에 value 값으로 key 키를 저장합니다.

- get(key: str, timestamp: int) -> str timestamp_prev <= timestamp을 사용하여 이전에 set이 호출된 것과 같은 값을 반환합니다. 이러한 값이 여러 개인 경우 가장 큰 timestamp_prev과 관련된 값을 반환합니다. 값이 없으면 ""을 반환합니다.

제약

•1 <= key.length, value.length <= 100
•key and value consist of lowercase English letters and digits
•1 <= timestamp <= 10^7
•All timestamps of set are strictly increasing for each key
•At most 2 * 10^5 calls will be made to set and get

예

Example 1

Input

["TimeMap", "set", "get", "get", "set", "get", "get"]
[[], ["foo", "bar", 1], ["foo", 1], ["foo", 3], ["foo", "bar2", 4], ["foo", 4], ["foo", 5]]

Output

[None, None, "bar", "bar", None, "bar2", "bar2"]

Explanation

set("foo", "bar", 1): stores bar at time 1. get("foo", 1): returns "bar". get("foo", 3): returns "bar" (latest value at or before time 3). set("foo", "bar2", 4): stores bar2 at time 4. get("foo", 4): returns "bar2". get("foo", 5): returns "bar2".

Need a Hint?

세트나 힙과 같은 이진 검색 관련 데이터 구조를 사용하는 것을 고려해보세요.

Edge Cases to Watch

빈 입력 구조
단일 요소 입력
큰 수치 범위

해결할 준비가 되셨나요?

Open the problem in PyRun's browser-based Python editor. Your code runs fully offline — no server required.

편집기에서 열기

인터뷰 통찰력 및 변형

이진 검색 접근 방식의 논리를 설명하세요.

null 또는 빈 입력과 같은 극단적인 경우에 대해 논의합니다.

복잡성 분석 분석

무차별 대입 복잡성

Time: O(n)•Space: O(1)

왜 시간인가?: Directly evaluates all possibilities.

왜 우주인가?: Uses standard local memory.

최적화된 복잡성

Time: O(n)•Space: O(n)

왜 시간인가?: Optimized paths reduce total operations.

왜 우주인가?: May trade memory for speed.

최적화된 솔루션 Python 코드

컴파일러에서 시도해 보세요

class TimeMapOpt:
    def __init__(self):
        self.store = {}
    def set(self, key: str, value: str, timestamp: int) -> None:
        if key not in self.store: self.store[key] = []
        self.store[key].append([value, timestamp])
    def get(self, key: str, timestamp: int) -> str:
        res = ""
        values = self.store.get(key, [])
        l, r = 0, len(values) - 1
        while l <= r:
            m = (l + r) // 2
            if values[m][1] <= timestamp:
                res = values[m][0]
                l = m + 1
            else:
                r = m - 1
        return res

무차별 대입 코드(스포일러 보호)

컴파일러에서 시도해 보세요

class TimeMapBrute:
    def __init__(self):
        self.store = {}
    def set(self, key: str, value: str, timestamp: int) -> None:
        if key not in self.store: self.store[key] = []
        self.store[key].append([value, timestamp])
    def get(self, key: str, timestamp: int) -> str:
        res = ""
        values = self.store.get(key, [])
        for v, t in values:
            if t <= timestamp: res = v
        return res