Pierwsza aukcja oferty publicznej

Question

Transkrypcja obrazu:

Firma rejestruje się w ofercie publicznej. Wszystkie akcje są dostępne na stronie internetowej do licytowania w okresie zwanym oknem licytacji. Pod koniec okresu licytacji logika aukcji jest używana do określenia, ile dostępnych akcji trafi do danego oferenta, aż wszystkie akcje zostaną przydzielone lub wszyscy oferenci otrzymają akcje, o które złożyli ofertę, w zależności od tego, co nastąpi wcześniej.

Oferty przychodzą od użytkowników w postaci [identyfikator użytkownika, liczba udziałów, cena licytacji, znacznik czasu] do zamknięcia okna licytacji.

Logika aukcji przypisuje akcje w następujący sposób:

1. Licytant z najwyższą ceną otrzymuje liczbę akcji, na które złożył ofertę

2. Jeśli wielu oferentów złożyło oferty po tej samej cenie, oferentom przypisuje się udziały w kolejności, w jakiej składają oferty (najpierw oferty najwcześniej)

Wymień identyfikatory wszystkich użytkowników, którzy nie otrzymali nawet 1 udziału po przydzieleniu wszystkich udziałów.

Wejście

• 
  lista ofert z listami int reprezentującymi [identyfikator użytkownika, # udostępnienia, $ bid, timestamp]
• totalShares
  łączna liczba udziałów do dystrybucji.

Do zrobienia

rozdziel udziały wśród oferentów i zwróć identyfikatory użytkowników oferentów, którzy otrzymali 0 udziałów.

Udostępnij logikę dystrybucji:

1. licytujący z najwyższą ofertą otrzymuje wszystkie akcje, o które licytuje, a następnie
2. jeśli istnieją remisy w cenie kupna $, przypisz akcje wcześniejszemu oferentowi.

Wydaje mi się, że rozwiązanie, które wymyśliłem, jest stosunkowo proste. Wydaje się, że mija wszystkie skrajne przypadki, które przychodzą mi do głowy.

Pytanie

Znalazłem wątpliwą sytuację:
cena kupna i terminy są takie same i nie ma wystarczającej liczby akcji dla wszystkich oferentów, tj. bidsJest [[0,2,10,0], [1,2,10,0]]i totalSharesjest 2. Nie jest jasne, czy każdemu należy przypisać 1 udział, czy też identyfikator użytkownika 0 otrzymuje oba.

Kod

Czy moje rozwiązanie można w jakikolwiek sposób zoptymalizować?

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

Użyj nazwy funkcji podanej w zadaniu:

def getUnallottedUsers(bids, totalShares):

Problem nie dostarcza żadnych informacji o prawdopodobieństwie wystąpienia wystarczającej liczby udziałów dla wszystkich oferentów, więc IMO pierwsza pętla for jest przykładem przedwczesnej optymalizacji.

Używaj stałych zamiast „magicznych liczb”. Używaj znaczących nazw. Zapoznaj się z PEP8 o wspólnych konwencjach formatowania. Te rzeczy znacznie wpływają na czytelność kodu.

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

Odpowiedz na zadane pytanie: „Funkcja musi zwrócić listę liczb całkowitych, z których każda stanowi identyfikator tych oferentów, którzy nie otrzymali udziałów, posortowanych rosnąco ”

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

Wszyscy razem:

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

Lub użyj iteratora:

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

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