Spread bid-ask após cada oferta
A missão
Problema
Um quadro de cotações recebe ofertas no formato ("buy", price) ou ("sell", price). Nada é negociado neste quadro, então toda oferta permanece. Depois de cada oferta, informe o spread: o menor preço de venda menos o maior preço de compra. Quando algum dos lados ainda não tiver ofertas, informe None. Retorne a lista de resultados.
Exemplos
Input: quotes = [("buy", 100), ("sell", 105), ("buy", 102), ("sell", 104), ("buy", 99)]
Output: [None, 5, 3, 2, 2]
Por quê: a melhor compra sobe para 102 e a melhor venda cai para 104, e a compra baixa em 99 não muda nada
Input: quotes = [("sell", 50), ("sell", 40)]
Output: [None, None]
Por quê: ninguém ofereceu um preço de compra ainda
Input: quotes = [("buy", 12), ("sell", 10)]
Output: [None, -2]
Por quê: edge case: nada é negociado aqui, então um quadro cruzado simplesmente mostra um spread negativo
Dicas
0 / 3
Só dois preços importam depois de cada oferta: a maior compra e a menor venda. Varrer de novo todas as ofertas a cada vez é quadrático.
O lado da compra precisa do seu máximo sob demanda e o lado da venda, do seu mínimo, enquanto os dois lados não param de crescer. Um heap por lado dá cada resposta em tempo constante.
Insira os preços de compra em um max-heap e os de venda em um min-heap. Depois de cada oferta, se os dois heaps não estiverem vazios, informe o topo do heap de venda menos o topo do heap de compra; caso contrário, informe None.
- Tempo-alvo
- O(n log n)
- Espaço-alvo
- O(n)
Solução
O quadro são duas metades com uma fronteira entre elas, que é o formato que o padrão de dois heaps resolve: um max-heap para o lado da compra, para que a maior compra fique no topo, e um min-heap para o lado da venda, para que a menor venda fique no topo. Cada oferta é uma inserção no seu próprio lado, e o spread lê só os dois topos. O heapq do Python é um min-heap, então os preços de compra são guardados negados, o que transforma a diferença em uma soma dos dois topos. Cada oferta custa O(log n), então o tempo é O(n log n) e o espaço é O(n).
import heapq
def spreads(quotes):
bids, asks = [], [] # bids: max-heap of negated prices, asks: min-heap
reports = []
for side, price in quotes:
if side == "buy":
heapq.heappush(bids, -price)
else:
heapq.heappush(asks, price)
# lowest sell minus highest buy; bids are stored negated
reports.append(asks[0] + bids[0] if bids and asks else None)
return reports
print(spreads([("buy", 100), ("sell", 105), ("buy", 102), ("sell", 104), ("buy", 99)])) # -> [None, 5, 3, 2, 2]
print(spreads([("sell", 50), ("sell", 40)])) # -> [None, None]
print(spreads([("buy", 12), ("sell", 10)])) # -> [None, -2]Travou na ideia, e não no código? O básico de heaps explica isso.