4
\$\begingroup\$

enter image description here

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.

Input

  • 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
\$\endgroup\$
2
  • 3
    \$\begingroup\$ 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. \$\endgroup\$
    – Peilonrayz
    Aug 16 '20 at 4:31
  • \$\begingroup\$ @Peilonrayz thanks, added \$\endgroup\$
    – Grshh
    Aug 16 '20 at 15:25
2
\$\begingroup\$

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)
\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.