Requisições na última janela
A missão
Problema
Um serviço registra o horário de chegada de cada requisição em milissegundos, e os horários vêm em ordem não decrescente. Para cada requisição, informe quantas requisições, incluindo ela mesma, chegaram durante os últimos w milissegundos, ou seja, em um horário estritamente maior que o horário dela menos w. Retorne uma contagem por requisição.
Exemplos
Input: times = [0, 400, 900, 1000, 1400], w = 1000
Output: [1, 2, 3, 3, 3]
Por quê: em 1000, a requisição do horário 0 tem exatamente w de idade e deixa de contar
Input: times = [5, 5, 5], w = 1
Output: [1, 2, 3]
Por quê: horários iguais caem todos na mesma janela
Input: times = [], w = 50
Output: []
Por quê: edge case: nenhuma requisição
Dicas
0 / 3
Quando uma requisição fica velha demais para uma chegada, ela fica velha demais para todas as chegadas seguintes também, porque os horários nunca diminuem.
As requisições antigas saem pela frente e as novas entram por trás, o que é exatamente “primeiro a entrar, primeiro a sair”.
Mantenha uma fila de horários. Para cada chegada, adicione o horário dela no fim e então remova horários da frente enquanto o horário da frente for no máximo o horário da chegada menos w. O tamanho da fila é a resposta para essa chegada.
- Tempo-alvo
- O(n)
- Espaço-alvo
- O(n)
Restrições
- times are in non-decreasing order
Solução
Como os horários nunca diminuem, as requisições expiram na mesma ordem em que chegaram, então as que ainda estão dentro da janela sempre formam uma sequência no início de uma fila. Cada chegada entra no fim, e os horários expirados saem pela frente até que o mais antigo restante seja recente o bastante. Cada horário é adicionado uma vez e removido no máximo uma vez, então o trabalho total é linear mesmo quando uma única chegada remove muitos. O tempo é O(n) e o espaço é O(n), atingido quando todas as requisições caem dentro de uma única janela.
from collections import deque
def recent_counts(times, w):
window, out = deque(), []
for t in times:
window.append(t)
while window[0] <= t - w: # too old now, and for every later arrival
window.popleft()
out.append(len(window))
return out
print(recent_counts([0, 400, 900, 1000, 1400], 1000)) # -> [1, 2, 3, 3, 3]
print(recent_counts([5, 5, 5], 1)) # -> [1, 2, 3]
print(recent_counts([], 50)) # -> []Travou na ideia, e não no código? O básico de filas explica isso.