# Initial public offering auction

Image transcription:

A company registers for an IPO. All shares are available on the website for bidding during a time frame called the bidding window. At the end of the bidding window an auction logic is used to decide how many available shares go to which bidder until all shares have been allocated, or all the bidders have received the shares they bid for, whichever comes first.

The bids arrive from users in the form of [userid, # shares, bidding price, timestamp] until the bidding window is closed.

The auction logic assigns shares as follows:

1. The bidder with the highest price gets the # of shares they bid for

2. If multiple bidders have bid at the same price, the bidders are assigned shares in the order in which they places their bids (earliest bids first)

List the userids of all the users who didn't get even 1 share after all shares have been allocated.

• bids
list of lists of ints representing [userid, # shares, $bid, timestamp] • totalShares total # of shares to be distributed. ## Todo distribute shares amongst bidders and return userids of bidders that got 0 shares. Share distribution logic: 1. bidder with highest offer gets all the shares they bid for, and then 2. if there are ties in$ bid price, assign shares to earlier bidder.

I feel like the solution I came up with is relatively simple. It seems to pass all edge cases I can think of.

## Question

I have found a questionable situation:
Bid price and times are the same and there aren't enough shares for all bidders ie: bids is [[0,2,10,0], [1,2,10,0]] and totalShares is 2. It's unclear if 1 share should be given to each, or if userid 0 just gets both.

## Code

Can my solution be optimized in anyway?

def getUnallocatesUsers(bids, totalShares):
s = 0
for b in bids:
s += b[1]
if totalShares >= s: return []  # no losers because enough shares to go around

bids.sort(key = lambda x: (-x[2],x[3]))  # sort by highest bid, then timestamp for ties
losers = []
for b in bids:
if totalShares <= 0: losers.append(b[0])
else:
totalShares -= b[1]
return losers

• Please can you convert the image to text. Images are fairly inaccessible for our users that are blind. Additionally the image currently is illegible to me due to the resizing. Thank you. Aug 16 '20 at 4:31
• @Peilonrayz thanks, added Aug 16 '20 at 15:25

## 1 Answer

Use the function name given in the problem:

def getUnallottedUsers(bids, totalShares):


The problem doesn't provide any information about the likelihood of there being enough shares for all bidders, so IMO the first for-loop is an example of premature optimization.

Use constants instead of "magic numbers". Use meaningful names. Take a look at PEP8 about common formatting conventions. These things go a long way in making code readable.

USERID = 0
SHARES = 1
PRICE = 2
TIME = 3

bids.sort(key=lambda bid:(-bid[PRICE], bid[TIME]))

for index, bid in enumerate(bids):
totalShares -= bid[SHARES]

if totalShares <= 0:
break


Answer the question that was asked: "The function must return a list of integers, each an id for those bidders who receive no shares, sorted ascending"

return sorted(bid[USERID] for bid in bids[index + 1:])


All together:

USERID = 0
SHARES = 1
PRICE = 2
TIME = 3

def getUnallottedUsers(bids, totalShares):
bids.sort(key=lambda bid:(-bid[PRICE], bid[TIME]))

for index, bid in enumerate(bids):
totalShares -= bid[SHARES]

if totalShares <= 0:
break

return sorted(bid[USERID] for bid in bids[index + 1:])


Or use an iterator:

    bids = iter(bids)
while totalShares > 0:
price = next(bid)[PRICE]
totalShares -= price

return sorted(bid[USERID] for bid in bids)