Аукцион первичного публичного размещения

Question

Транскрипция изображения:

Компания регистрируется на IPO. Все акции доступны на веб-сайте для участия в торгах в течение периода, называемого окном торгов. В конце окна торгов используется логика аукциона, чтобы решить, сколько доступных акций будет отдано тому или иному участнику торгов до тех пор, пока все акции не будут распределены или все участники торгов не получат доли, за которые они сделали заявку, в зависимости от того, что наступит раньше.

Ставки поступают от пользователей в форме [идентификатор пользователя, количество акций, цена предложения, отметка времени] до закрытия окна торгов.

Логика аукциона распределяет акции следующим образом:

1. Участник торгов, предложивший самую высокую цену, получает количество акций, за которые он подал заявку.

2. Если несколько участников аукциона сделали заявку по одной и той же цене, участникам конкурса распределяются доли в том порядке, в котором они размещают свои заявки (сначала самые ранние заявки).

Перечислите идентификаторы всех пользователей, которые не получили ни одной доли после того, как все доли были распределены.

Ввод

• bids
  список списков целых чисел, представляющих [идентификатор пользователя, # доли, $ ставка, временная метка]
• totalShares
  общее количество распределяемых акций.

Делать

распределить акции среди участников аукциона и вернуть идентификаторы пользователей, получивших 0 акций.

Логика распределения доли:

1. участник торгов с наибольшим предложением получает все акции, за которые он подал заявку, а затем
2. если есть различия в цене предложения $, назначить акции более раннему участнику торгов.

Мне кажется, решение, которое я придумал, относительно простое. Кажется, он проходит все крайние случаи, о которых я могу думать.

Вопрос

Я обнаружил сомнительную ситуацию:
цена и время заявки одинаковы, и не хватает акций для всех участников, то есть: bidsесть [[0,2,10,0], [1,2,10,0]]и totalSharesесть 2. Неясно, следует ли отдавать каждому по 1 доле, или если идентификатор пользователя 0 получает и то, и другое.

Код

Можно ли как-нибудь оптимизировать мое решение?

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

Answer 1

Используйте имя функции, указанное в задаче:

def getUnallottedUsers(bids, totalShares):

Проблема не дает никакой информации о вероятности того, что акций будет достаточно для всех участников торгов, поэтому IMO первый цикл for является примером преждевременной оптимизации.

Используйте константы вместо «магических чисел». Используйте значащие имена. Взгляните на PEP8 об общих соглашениях о форматировании. Эти вещи имеют большое значение для обеспечения читабельности кода.

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

Ответьте на заданный вопрос: «Функция должна возвращать список целых чисел, каждое из которых является идентификатором для тех участников торгов, которые не получают акций, отсортированных по возрастанию ».

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

Все вместе:

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:])

Или используйте итератор:

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

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