Why do we need binary search in Time Based Key-Value Store?

Binary search efficiently finds the most recent value at or before the given timestamp, avoiding a slow linear scan over all stored values for a key.

Can timestamps be repeated for the same key?

No, timestamps are strictly increasing for each key, which ensures that each binary search retrieves a unique latest value.

What should get return if no value exists at the query timestamp?

It should return an empty string if the key doesn't exist or the query timestamp is earlier than any stored timestamp.

How does GhostInterview help with edge cases?

It points out boundary conditions, such as querying before the first timestamp or at exact timestamp matches, ensuring correct implementation.

What is the space complexity for storing Time Based Key-Value data?

Space complexity is O(m), where m is the total number of set operations across all keys, because each (timestamp, value) pair is stored.

#981

Medium

auto_awesome二分·搜索·答案·空间

LeetCode 题解工作台

基于时间的键值存储

设计一个基于时间的键值数据结构，该结构可以在不同时间戳存储对应同一个键的多个值，并针对特定时间戳检索键对应的值。实现 TimeMap 类： TimeMap() 初始化数据结构对象 void set(String key, String value, int timestamp) 存储给定时间戳 t…

哈希表字符串二分查找设计

题目描述

设计一个基于时间的键值数据结构，该结构可以在不同时间戳存储对应同一个键的多个值，并针对特定时间戳检索键对应的值。

实现 TimeMap 类：

TimeMap() 初始化数据结构对象
void set(String key, String value, int timestamp) 存储给定时间戳 timestamp 时的键 key 和值 value。
String get(String key, int timestamp) 返回一个值，该值在之前调用了 set，其中 timestamp_prev <= timestamp 。如果有多个这样的值，它将返回与最大 timestamp_prev 关联的值。如果没有值，则返回空字符串（""）。

示例 1：

输入：
["TimeMap", "set", "get", "get", "set", "get", "get"]
[[], ["foo", "bar", 1], ["foo", 1], ["foo", 3], ["foo", "bar2", 4], ["foo", 4], ["foo", 5]]
输出：
[null, null, "bar", "bar", null, "bar2", "bar2"]

解释：
TimeMap timeMap = new TimeMap();
timeMap.set("foo", "bar", 1);  // 存储键 "foo" 和值 "bar" ，时间戳 timestamp = 1   
timeMap.get("foo", 1);         // 返回 "bar"
timeMap.get("foo", 3);         // 返回 "bar", 因为在时间戳 3 和时间戳 2 处没有对应 "foo" 的值，所以唯一的值位于时间戳 1 处（即 "bar"） 。
timeMap.set("foo", "bar2", 4); // 存储键 "foo" 和值 "bar2" ，时间戳 timestamp = 4  
timeMap.get("foo", 4);         // 返回 "bar2"
timeMap.get("foo", 5);         // 返回 "bar2"

提示：

1 <= key.length, value.length <= 100
key 和 value 由小写英文字母和数字组成
1 <= timestamp <= 10⁷
set 操作中的时间戳 timestamp 都是严格递增的
最多调用 set 和 get 操作 2 * 10⁵ 次

lightbulb

解题思路

方法一：哈希表 + 有序集合（或二分查找）

我们可以用哈希表 $\textit{kvt}$ 记录键值对，其中键为字符串 $\textit{key}$ ，值为一个有序集合，集合中的每个元素为一个二元组 $(\textit{timestamp}, \textit{value})$ ，表示键 $\textit{key}$ 在时间戳 $\textit{timestamp}$ 时对应的值为 $\textit{value}$ 。

当我们需要查询键 $\textit{key}$ 在时间戳 $\textit{timestamp}$ 时对应的值时，我们可以通过有序集合的方法找到最大的时间戳 $\textit{timestamp}'$ ，使得 $\textit{timestamp}' \leq \textit{timestamp}$ ，然后返回对应的值即可。

时间复杂度方面，对于 $\textit{set}$ 操作，由于哈希表的插入操作的时间复杂度为 $O(1)$ ，因此时间复杂度为 $O(1)$ 。对于 $\textit{get}$ 操作，由于哈希表的查找操作的时间复杂度为 $O(1)$ ，而有序集合的查找操作的时间复杂度为 $O(\log n)$ ，因此时间复杂度为 $O(\log n)$ 。空间复杂度为 $O(n)$ ，其中 $n$ 为 $\textit{set}$ 操作的次数。

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

17

18

19

20

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

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

    def get(self, key: str, timestamp: int) -> str:
        if key not in self.ktv:
            return ''
        tv = self.ktv[key]
        i = bisect_right(tv, (timestamp, chr(127)))
        return tv[i - 1][1] if i else ''


# Your TimeMap object will be instantiated and called as such:
# obj = TimeMap()
# obj.set(key,value,timestamp)
# param_2 = obj.get(key,timestamp)

speed

复杂度分析

指标	值
时间	Depends on the final approach
空间	Depends on the final approach

psychology

面试官常问的追问

外企场景

question_mark
Ask if you can assume timestamps are strictly increasing per key.
question_mark
Check if the candidate uses binary search instead of linear scan for retrieval.
question_mark
Confirm handling of keys with no stored value at the queried timestamp.

warning

常见陷阱

外企场景

error
Performing linear search instead of binary search for get operations, leading to timeouts.
error
Not handling empty lists or keys with no stored timestamps properly.
error
Incorrectly implementing binary search boundaries, returning the wrong value for edge timestamps.

swap_horiz

进阶变体

外企场景

arrow_right_alt
Support deletion of key-value pairs at specific timestamps.
arrow_right_alt
Allow multiple keys with overlapping timestamp ranges and query across them.
arrow_right_alt
Retrieve all values within a given timestamp range instead of just the latest one.

help

常见问题

外企场景

继续练习

#911 在线选举 #1146 快照数组 #792 匹配子序列的单词数