Spread compra-venta tras cada cotización
La misión
Problema
Un tablero de cotizaciones recibe cotizaciones de la forma ("buy", price) o ("sell", price). En este tablero no se cierra ninguna operación, así que todas las cotizaciones se quedan. Después de cada cotización, reporta el spread (diferencial): el precio de venta más bajo menos el precio de compra más alto. Si alguno de los dos lados todavía no tiene cotizaciones, reporta None. Devuelve la lista de reportes.
Ejemplos
Input: quotes = [("buy", 100), ("sell", 105), ("buy", 102), ("sell", 104), ("buy", 99)]
Output: [None, 5, 3, 2, 2]
Por qué: la mejor compra sube a 102 y la mejor venta baja a 104, y la compra de 99, más baja, no cambia nada
Input: quotes = [("sell", 50), ("sell", 40)]
Output: [None, None]
Por qué: nadie ha cotizado todavía un precio de compra
Input: quotes = [("buy", 12), ("sell", 10)]
Output: [None, -2]
Por qué: caso límite: aquí no se opera, así que un tablero cruzado simplemente muestra un spread negativo
Pistas
0 / 3
Después de cada cotización solo importan dos precios: la compra más alta y la venta más baja. Volver a recorrer todas las cotizaciones cada vez es cuadrático.
El lado de compra necesita su máximo bajo demanda y el lado de venta su mínimo, mientras ambos lados siguen creciendo. Un heap por lado da cada respuesta en tiempo constante.
Haz push de los precios de compra en un max-heap y de los de venta en un min-heap. Después de cada cotización, si ninguno de los dos heaps está vacío, reporta la cima del heap de venta menos la cima del heap de compra; si no, reporta None.
- Tiempo objetivo
- O(n log n)
- Espacio objetivo
- O(n)
Solución
El tablero son dos mitades con una frontera entre ellas, que es justo la forma que resuelve el patrón de dos heaps (montículos): un max-heap para el lado de compra, así que la compra más alta queda en la cima, y un min-heap para el lado de venta, así que la venta más baja queda en la cima. Cada cotización es un solo push en su propio lado, y el spread solo lee las dos cimas. El heapq de Python es un min-heap, así que los precios de compra se guardan negados, lo que convierte la diferencia en una suma de las dos cimas. Cada cotización cuesta O(log n), así que el tiempo es O(n log n) y el espacio es 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]¿Lo que te frena es la idea y no el código? Fundamentos del heap lo explica.