Two Sigma OA 面试真题解析：IPO Share Allocation 股份分配

1. IPO share allocation

An initial public offering (IPO) refers to the process of offering shares of a private corporation to the public in a new stock issuance. Public share issuance allows a company to raise capital from public investors. An IPO process can go through a typical auction, and an IPO price is not set before the auction.

Potential buyers are able to bid for the shares they want and the price they are willing to pay. The bidders who were willing to pay the highest price are then allocated the shares available.

Before the auction ends, potential buyers can submit bids containing: user id, number of shares, bidding price, timestamp.

Once all the bids are submitted, the allotted placement is assigned to the bidders from the highest bids down, until all of the allotted shares are assigned. The auction assigns shares in multiple rounds until shares are allocated or no more bids. In each round, it finds the bids with highest prices, assigns the shares, and removes the assigned bids:

• If the bid with the highest price has only one bidder, the bidder gets the shares he/she bids for, or whatever is left if the unallocated shares are less than the bid shares.
• If the bids with the highest price have multiple bidders, the bidders are assigned shares as follows: shares are distributed round robin style (i.e. one share per bidder in sequence until shares are all allocated) to bidders in the same price group, with the bidders sorted by timestamp. Once a bidder gets the number of shares they bid for, they are removed from the iterative process, which continues until all bidders are removed or the shares get exhausted, whichever comes first.

Find out all bidders (user IDs) with no share allocation.

Function Description

Complete the function getResults in the editor below.

The function must return a list of integers, each an id for those bidders who receive no shares, sorted ascending.

getResults has the following parameter(s):

• bids: a 2D array of arrays of integers, id, shares, price, timestamp
• totalShares: an integer, the total shares to allocate

这道题模拟的是 IPO 拍卖中的分配过程：先按出价高低分组，再在同一价格组内按时间戳升序进行轮转分配；如果同价组只有一个人，就直接分到他申请的数量或剩余股份。核心难点在于“分组 + 排序 + 轮转 + 动态删人”的过程要严格按规则执行，因此通常会先把 bids 按 price 降序、timestamp 升序整理好，再逐组处理，并用集合记录最终没有拿到任何股份的用户 ID。