IPO Share Allocation With Bids
You are given a collection of bids for shares in an IPO and the total number of shares available. Allocate the shares according to bid price and submission time, then return the user IDs of bidders who receive no shares.
Bid Format
Each bid is represented by a comma-separated string in the following format:
"userId,requestedShares,bidPrice,timestamp"
userId is the unique identifier of the bidder.requestedShares is the number of shares requested.bidPrice is the price offered per share.timestamp is the time at which the bid was submitted.
Allocation Rules
- Bids with a higher
bidPrice are processed before bids with a lower price.
- All bidders offering the same price form one allocation group.
- Within a group, bidders are ordered by increasing
timestamp.
- If two bids have the same price and timestamp, the bidder with the smaller
userId is processed first.
- Shares are distributed within the group using round-robin allocation. Each bidder who still needs shares receives one share during each round.
- Round-robin allocation continues until every bid in the group is satisfied or no shares remain.
- After completing a price group, allocation continues with the next lower bid price.
Return the user IDs of all bidders who receive zero shares. The returned user IDs must be sorted in increasing order.
Method Signature
List<Integer> getUnallottedUsers(List<String> bids, int totalShares)
bids contains the IPO bids in the format "userId,requestedShares,bidPrice,timestamp".totalShares is the total number of shares available for allocation.- The method returns the user IDs of bidders who receive no shares, sorted in increasing order.
Constraints
1 ≤ bids.size() ≤ 100,000- Each entry in
bids contains exactly four comma-separated integers.
1 ≤ userId ≤ 1,000,000,000- All
userId values are unique.
1 ≤ requestedShares ≤ 1,000,000,0001 ≤ bidPrice ≤ 1,000,000,0000 ≤ timestamp ≤ 1,000,000,0000 ≤ totalShares ≤ 1,000,000,000
Examples
Example 1
getUnallottedUsers(bids = ["21,4,15,3", "8,2,20,1", "13,3,15,2"], totalShares = 5)
Output: []
User 8 has the highest bid price and receives both requested shares. Users 13 and 21 have the same bid price, so they are processed in increasing timestamp order. User 13 comes before user 21.
The remaining three shares are distributed in the order 13, 21, 13. User 13 receives two shares and user 21 receives one share. Since every bidder receives at least one share, the result is an empty list.
Example 2
getUnallottedUsers(bids = ["4,2,30,5", "9,4,25,2", "2,3,25,1", "7,1,10,4"], totalShares = 4)
Output: [7]
User 4 has the highest bid price and receives both requested shares. Two shares remain.
Users 2 and 9 have the next highest bid price. User 2 has the earlier timestamp, so the remaining shares are distributed in the order 2, 9. User 7 receives no shares because all available shares have already been allocated.
Therefore, the only completely unallotted bidder is user 7.
Example 3
getUnallottedUsers(bids = ["15,5,40,10", "3,2,35,4", "11,1,20,7"], totalShares = 0)
Output: [3, 11, 15]
No shares are available, so every bidder receives zero shares. The user IDs are returned in increasing order.
Example 4
getUnallottedUsers(bids = ["10,3,50,8", "5,3,50,8", "14,3,50,3"], totalShares = 2)
Output: [10]
All three bidders offer the same bid price. User 14 has the earliest timestamp and receives the first share.
Users 5 and 10 have the same timestamp. Since user 5 has the smaller user ID, user 5 receives the second share. User 10 receives no shares.