Questions / Quant development, Trading system components
Lazy deletion in a bid heap
Orders 2 and 3 are cancelled by removing them from live only. What does best() print?
import heapq
bids, live = [], {}
def add(oid, px, qty):
live[oid] = qty
heapq.heappush(bids, (-px, oid))
def best():
while bids and bids[0][1] not in live:
heapq.heappop(bids) # lazy deletion
return -bids[0][0] if bids else None
add(1, 99.5, 100); add(2, 100.0, 50); add(3, 100.0, 70); add(4, 99.0, 10)
del live[2]; del live[3]
print(best())Answer it in the app It's free. You get hints, a second try if you miss, and a follow-up question.
Show the answer and worked solution
Answer: 99.5 price
- The heap top is (−100.0, 2), not live: pop.
- Next (−100.0, 3): pop.
- Top is now 99.5.
Interview shortcut. Skip dead tops: 100.0 is gone, so 99.5.
Takeaway. Lazy deletion keeps cancels O(1) and cleans up at read time.
In the app this has a follow-up where one thing about the setup changes. Try the follow-up.