Armazenamento de valor-chave baseado em tempo
Guia detalhado e implementação de Python para o problema de 'Armazenamento de valores-chave baseado em tempo'.
1. Aprenda
O problema do 'armazenamento de valores-chave baseado no tempo' é um desafio importante na seção de pesquisa binária.
Esta implementação concentra-se na lógica de nível fácil em Python.
Priorizamos a precisão técnica e a legibilidade do código em nossas soluções fornecidas.
2. Real-World Applications
3. Visual Intuition
Visualizando o fluxo lógico para armazenamento de valores-chave baseado em tempo.
4. Prerequisites
5. Step-by-Step Thinking
1. Understand the problem
Leia atentamente a declaração do problema do armazenamento de valores-chave baseado em tempo.
2. Formulate brute force
Elabore uma solução iterativa simples.
3. Identify inefficiency
Procure cálculos redundantes.
4. Optimize search path
Use hashing ou classificação para acelerar o processo.
5. Final Implementation
Limpe o código para padrões de produção.
Declaração do problema
Projete uma estrutura de dados de valor-chave baseada em tempo que possa armazenar vários valores para a mesma chave em carimbos de data/hora diferentes e recuperar o valor da chave em um determinado carimbo de data/hora.
Implemente a classe TimeMap:
- TimeMap() Inicializa o objeto.
- set(key: str, value: str, timestamp: int) Armazena a chave key com o valor value no horário determinado timestamp.
- get(key: str, timestamp: int) -> str Retorna um valor tal que set foi chamado anteriormente, com timestamp_prev <= timestamp. Se houver vários desses valores, ele retornará o valor associado ao maior timestamp_prev. Se não houver valores, retorna "".
- •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
Exemplos
["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
- Estruturas de entrada vazias
- Entradas de elemento único
- Grandes limites numéricos
Pronto para resolver?
Open the problem in PyRun's browser-based Python editor. Your code runs fully offline — no server required.
Insights e variações da entrevista
Análise de complexidade
Por que tempo: Directly evaluates all possibilities.
Por que espaço: Uses standard local memory.
Por que tempo: Optimized paths reduce total operations.
Por que espaço: May trade memory for speed.
Código Python da solução otimizada
Código Python da solução otimizada
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 resCódigo de força bruta (protegido por spoiler)
Código de força bruta (protegido por 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
Aplicam-se propriedades de problema de pesquisa binária padrão.
Perguntas relacionadas
PyRun is built and maintained by an independent solo developer. If this helped your interview prep, consider buying a coffee!
Recursos Python recomendados
Expanda seu conhecimento com tutoriais interativos relacionados, folhas de dicas e comparações de código.
Python Datetime
Aprenda como lidar com datas, horas, fusos horários e cálculos em Python. Domine a formatação, análise e aritmética usando datetime e timedelta.
Como classificar um dicionário por valor em Python
Aprenda como classificar um dicionário Python por seus valores. Descubra a classificação usando sorted(), lambdas de chave personalizada e construção de estruturas de dict ordenadas.
Folha de dicas sobre formatação de data e hora em Python
Aprenda como analisar e formatar datas e horas em Python usando datetime, strftime e strptime.
Python vs JavaScript: qual linguagem de programação é a melhor?
Uma comparação abrangente entre Python e JavaScript. Explore diferenças de sintaxe, desempenho, casos de uso (backend versus frontend) e exemplos de codificação.