SWE / QSE OA — IPO Share Allocation

Allocate IPO shares to bidders by descending price. Single bidders receive their requested amount up to remaining supply; tied price groups are allocated round-robin by timestamp until supply or group demand is exhausted. Requirements Input is a list of bids and a total share supply. Each bid includes at least bidder id, bid price, requested share count, and timestamp. Allocate shares under these rules: Process price groups from highest bid price to lowest. If the current highest-price group has one bidder, allocate that bidder the requested number of shares, capped by remaining supply. If the current highest-price group has multiple bidders, sort that group by timestamp and distribute shares round-robin, one share per active bidder per pass. Once a bidder receives all requested shares, remove that bidder from the active round-robin group. Stop when all shares are allocated or all eligible bidders in processed groups are exhausted. Return a list of bidder ids or unallocated bidder ids as specified by the prompt variant; clarify the exact return shape before coding. Notes The performance-sensitive implementation sorts bids once, then groups by price. Re-sorting inside the allocation loop can time out. The phrase "whichever comes first" matters: check exhaustion both when entering and leaving the queue / deque loop. A queue over the timestamp-sorted tied group is enough for the round-robin allocation; a heap is usually unnecessary after grouping. A common failure is starting the tied-price allocation before sorting that group by timestamp; verify tie ordering before entering the simulation loop. Preparation Implement the allocation in three phases: sort, group by price, allocate each group. Write tests for partial fill, exact fill, one bidder at the top price, tied timestamps sorted deterministically, and supply exhausted mid-cycle. Practice explaining why one global sort is sufficient and where the round-robin loop terminates.