基於時間的鍵值存儲
「基於時間的鍵值儲存」問題的詳細指南和 Python 實作。
1. 學習
「基於時間的鍵值儲存」問題是二分搜尋部分的關鍵挑戰。
此實作著重於 Python 中的簡單層級邏輯。
在我們提供的解決方案中，我們優先考慮技術準確性和程式碼可讀性。
2. Real-World Applications
3. Visual Intuition
可視化基於時間的鍵值儲存的邏輯流程。
4. Prerequisites
5. Step-by-Step Thinking
1. Understand the problem
仔細閱讀基於時間的鍵值儲存的問題陳述。
2. Formulate brute force
起草一個簡單的迭代解決方案。
3. Identify inefficiency
尋找冗餘計算。
4. Optimize search path
使用散列或排序來加速該過程。
5. Final Implementation
清理生產標準代碼。
問題陳述
設計一個基於時間的鍵值資料結構，可以儲存同一鍵在不同時間戳記的多個值，並在某個時間戳記檢索該鍵的值。
實作 TimeMap 類別：
- TimeMap() 初始化物件。
- set(key: str, value: str, timestamp: int) 在給定時間 timestamp 儲存鍵 key 和值 value。
- get(key: str, timestamp: int) -> str 傳回一個值，使得 set 之前使用 timestamp_prev <= timestamp 被呼叫。如果有多個這樣的值，則傳回與最大的 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
範例
["TimeMap", "set", "get", "get", "set", "get", "get"] [[], ["foo", "bar", 1], ["foo", 1], ["foo", 3], ["foo", "bar2", 4], ["foo", 4], ["foo", 5]]
[None, None, "bar", "bar", None, "bar2", "bar2"]
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.
面試見解和變化
複雜度分析分解
為什麼時間: Directly evaluates all possibilities.
為什麼選擇太空: Uses standard local memory.
為什麼時間: Optimized paths reduce total operations.
為什麼選擇太空: May trade memory for speed.
最佳化解決方案Python程式碼
最佳化解決方案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 resAlgorithm Pattern Checklist
When dealing with Binary Search data patterns.
- Are constraints clear?
- Is there a linear or logarithmic optimization possible?
PyRun is built and maintained by an independent solo developer. If this helped your interview prep, consider buying a coffee!
推薦的 Python 資源
透過相關的互動式教學、備忘單和程式碼比較來擴展您的知識。
Python 日期時間：使用日期和時間
了解如何在 Python 中處理日期、時間、時區和計算。使用日期時間和時間增量來掌握格式化、解析和算術。
如何在 Python 中按值對字典進行排序
了解如何按 Python 字典的值對字典進行排序。探索使用排序（）、自訂鍵 lambda 進行排序，以及建立有序字典結構。
Python 日期時間格式備忘單
了解如何在 Python 中使用 datetime、strftime 和 strptime 解析和格式化日期和時間。
Python 與 JavaScript：哪種程式語言最好？
Python 和 JavaScript 的全面比較。探索語法差異、效能、用例（後端與前端）和編碼範例。