Share Allocation by Price
MediumSimulation ยท Two Sigma
Given bids, where each bid is [bid_id, shares, price, time], and total_shares available, return the number of shares each bid receives, in the order the bids are given.
Handle price levels from highest to lowest. If the remaining shares cover every bid at a level in full, each of them gets all it asked for. Otherwise the remaining shares are dealt out one at a time, cycling through the bids at that level ordered by time (ties by bid_id) and skipping any bid that already has what it asked for, until the shares run out. Lower prices then get nothing.
Example 1
- Input:
- bids = [[1, 5, 10, 1], [2, 2, 10, 2], [3, 4, 10, 3]], total_shares = 8
- Output:
- [3, 2, 3]
- Explanation
- Eleven shares are wanted at price 10. Bid 2 is full after two rounds, so the last two shares go to bids 1 and 3.
Example 2
- Input:
- bids = [[7, 3, 20, 5], [8, 6, 15, 1], [9, 4, 15, 2], [4, 5, 10, 1]], total_shares = 11
- Output:
- [3, 4, 4, 0]
Example 3
- Input:
- bids = [[5, 3, 9, 2], [2, 3, 9, 2]], total_shares = 1
- Output:
- [0, 1]
- Explanation
- The times are equal, so bid 2 comes before bid 5 and gets the only share.
Constraints
0 <= bids.length <= 10^5bid_idvalues are distinct integers1 <= shares <= 10^91 <= price <= 10^90 <= time <= 10^90 <= total_shares <= 10^14