Archivio valori chiave basato sul tempo
Guida dettagliata e implementazione Python per il problema "Archivio valori chiave basato sul tempo".
1. Impara
Il problema dell'archivio di valori chiave basato sul tempo è una sfida chiave nella sezione Ricerca binaria.
Questa implementazione si concentra sulla logica di livello semplice in Python.
Diamo priorità all'accuratezza tecnica e alla leggibilità del codice nelle soluzioni fornite.
2. Real-World Applications
3. Visual Intuition
Visualizzazione del flusso logico per l'archivio valori chiave basato sul tempo.
4. Prerequisites
5. Step-by-Step Thinking
1. Understand the problem
Leggere attentamente la dichiarazione del problema per l'archivio valori chiave basato sul tempo.
2. Formulate brute force
Elaborare una semplice soluzione iterativa.
3. Identify inefficiency
Cerca calcoli ridondanti.
4. Optimize search path
Utilizza l'hashing o l'ordinamento per accelerare il processo.
5. Final Implementation
Ripulire il codice per gli standard di produzione.
Dichiarazione del problema
Progettare una struttura dati chiave-valore basata sul tempo in grado di memorizzare più valori per la stessa chiave con timestamp diversi e recuperare il valore della chiave a un determinato timestamp.
Implementa la classe TimeMap:
- TimeMap() Inizializza l'oggetto.
- set(key: str, value: str, timestamp: int) Memorizza la chiave key con il valore value al momento specificato timestamp.
- get(key: str, timestamp: int) -> str Restituisce un valore tale che set è stato chiamato in precedenza, con timestamp_prev <= timestamp. Se sono presenti più valori di questo tipo, restituisce il valore associato al più grande timestamp_prev. Se non sono presenti valori, restituisce "".
- •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
Esempi
["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
- Strutture di input vuote
- Ingressi a elemento singolo
- Grandi limiti numerici
Pronto a risolvere?
Open the problem in PyRun's browser-based Python editor. Your code runs fully offline — no server required.
Approfondimenti e variazioni dell'intervista
Scomposizione dell'analisi della complessità
Perché il tempo: Directly evaluates all possibilities.
Perché lo spazio: Uses standard local memory.
Perché il tempo: Optimized paths reduce total operations.
Perché lo spazio: May trade memory for speed.
Codice Python della soluzione ottimizzata
Codice Python della soluzione ottimizzata
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 resCodice forza bruta (protetto da spoiler)
Codice forza bruta (protetto da spoiler)
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?
Key Revision Notes
Si applicano le proprietà del problema di ricerca binaria standard.
Domande correlate
PyRun is built and maintained by an independent solo developer. If this helped your interview prep, consider buying a coffee!
Risorse Python consigliate
Espandi le tue conoscenze con tutorial interattivi, foglietti illustrativi e confronti di codici correlati.
Python Datetime
Scopri come gestire date, orari, fusi orari e calcoli in Python. Padroneggia la formattazione, l'analisi e l'aritmetica utilizzando datetime e timedelta.
Come ordinare un dizionario per valore in Python
Scopri come ordinare un dizionario Python in base ai suoi valori. Scopri l'ordinamento utilizzando sorted(), chiavi lambda personalizzate e la creazione di strutture dict ordinate.
Foglio informativo sulla formattazione di Python DateTime
Scopri come analizzare e formattare date e ore in Python utilizzando datetime, strftime e strptime.
Python vs JavaScript: quale linguaggio di programmazione è il migliore?
Un confronto completo tra Python e JavaScript. Esplora le differenze di sintassi, le prestazioni, i casi d'uso (backend e frontend) ed esempi di codifica.