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):userwants up toquantityshares and will paypricefor 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
quantitydrops 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.