Leilão de oferta pública inicial

Aug 16 2020

Transcrição da imagem:

Uma empresa se registra para um IPO. Todas as ações estão disponíveis no site para licitação durante um período de tempo chamado janela de licitação. No final da janela de licitação, uma lógica de leilão é usada para decidir quantas ações disponíveis vão para qual licitante até que todas as ações tenham sido alocadas, ou todos os licitantes tenham recebido as ações pelas quais licitaram, o que ocorrer primeiro.

Os lances chegam dos usuários na forma de [userid, #shares, biding price, timestamp] até que a janela de lances seja fechada.

A lógica do leilão atribui ações da seguinte forma:

  1. O licitante com o preço mais alto obtém o número de ações que ele ofereceu

  2. Se vários licitantes tiverem licitado ao mesmo preço, são atribuídas ações aos licitantes pela ordem em que colocam as suas licitações (as primeiras licitações primeiro)

Liste os IDs de usuário de todos os usuários que não receberam nem 1 compartilhamento depois que todos os compartilhamentos foram alocados.

Entrada

  • bids
    list de listas de ints representando [userid, #shares, $bid, timestamp]
  • totalShares
    # total de ações a serem distribuídas.

Façam

distribua ações entre os licitantes e retorne IDs de usuário dos licitantes que obtiveram 0 ações.

Lógica de distribuição de compartilhamento:

  1. licitante com a oferta mais alta obtém todas as ações pelas quais licitou e, em seguida,
  2. se houver empates no preço de oferta de $, atribua ações ao licitante anterior.

Sinto que a solução que encontrei é relativamente simples. Parece passar em todos os casos extremos que posso imaginar.

Pergunta

Encontrei uma situação questionável:
o preço e os horários do lance são os mesmos e não há ações suficientes para todos os licitantes, ou seja: bidsé [[0,2,10,0], [1,2,10,0]]e totalSharesé 2. Não está claro se 1 compartilhamento deve ser dado a cada um, ou se o id de usuário 0 apenas recebe os dois.

Código

Minha solução pode ser otimizada de qualquer maneira?

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

Respostas

2 RootTwo Aug 18 2020 at 09:39

Use o nome da função fornecido no problema:

def getUnallottedUsers(bids, totalShares):

O problema não fornece nenhuma informação sobre a probabilidade de haver ações suficientes para todos os licitantes, então IMO o primeiro for-loop é um exemplo de otimização prematura.

Use constantes em vez de "números mágicos". Use nomes significativos. Dê uma olhada no PEP8 sobre convenções de formatação comuns. Essas coisas ajudam muito a tornar o código legível.

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

Responda à pergunta que foi feita: "A função deve retornar uma lista de números inteiros, cada um com um id para os licitantes que não recebem ações, classificados em ordem crescente "

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

Todos juntos:

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

Ou use um iterador:

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

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