progress

~/problems / Order books / Order books and matching engines

IPO share allocation

On a phone? Coding is easier on a laptop: email this problem to yourself . Meanwhile: quiz this topic or fight a boss.

medium assessment 2 levels ~40 min Two SigmaPoint72

Level 1 Who gets no IPO shares

When a company goes public, its bank collects bids from investors and then hands out a fixed number of new shares. You are writing the allocation step.

Write unfilled_bidders(bids, shares) -> list[str].

  • Each bid is a tuple (user, quantity, price, timestamp): user wants up to quantity shares and will pay price for each. Every user bids once, and no two bids share a timestamp.
  • Higher prices first. Every bidder at the highest price is served before anyone at a lower price gets a share.
  • Round-robin within a price. The bidders at one price take turns in timestamp order, earliest first. Each turn gives one share. When the last bidder has had a turn, the next round starts again with the earliest one. A bidder who has their full quantity drops out of the rounds.
  • When every bidder at a price has their full quantity, the remaining shares move on to the next lower price. When the shares run out, allocation stops. Shares nobody wants are simply left over.
  • Return the users who received no shares at all, sorted.
bids = [("ann", 5, 10, 3), ("bob", 2, 12, 5), ("cat", 4, 10, 1), ("dan", 3, 10, 2), ("eve", 1, 9, 4)]
unfilled_bidders(bids, 6)    # ["eve"]
unfilled_bidders(bids, 4)    # ["ann", "eve"]
unfilled_bidders(bids, 20)   # []

With 6 shares, bob is alone at price 12 and takes his 2. The 4 left go to price 10, where the order is cat, dan, ann: round 1 gives each of them one share, and round 2 gives cat the last one. Nothing reaches eve at price 9. With 4 shares, the 2 left after bob go to cat and dan. With 20, everyone is filled and 5 shares are left over.

Constraints: up to 10^5 bids. quantity, price and shares are integers in 1..10^9 (shares may also be 0), and timestamps are distinct integers in 0..10^9. User names are distinct non-empty strings. The quantities at one price can add up to more than 32 bits hold.

Shares and quantities run into the billions, so handing out shares one at a time is far too slow for some of the tests.

⭐ Bonus: a speed test with 10^5 bids earns a star in O(n log n) time.

Level 2 unlocks when level 1 passes.

Topic: Order books and matching engines. Price levels, price-time priority, partial fills, cancels.

0:00
Ctrl ' run · Ctrl ↵ submit
esc