Subasta de oferta pública inicial

Aug 16 2020

Transcripción de la imagen:

Una empresa se registra para una oferta pública inicial. Todas las acciones están disponibles en el sitio web para ofertar durante un período de tiempo llamado ventana de oferta. Al final de la ventana de licitación, se utiliza una lógica de subasta para decidir cuántas acciones disponibles van a cada postor hasta que se hayan asignado todas las acciones o todos los postores hayan recibido las acciones por las que ofertaron, lo que suceda primero.

Las ofertas llegan de los usuarios en forma de [ID de usuario, número de acciones, precio de oferta, marca de tiempo] hasta que se cierra la ventana de oferta.

La lógica de la subasta asigna acciones de la siguiente manera:

  1. El postor con el precio más alto obtiene el número de acciones por las que oferta.

  2. Si varios postores han ofertado al mismo precio, se asignan acciones a los postores en el orden en que presentan sus ofertas (las primeras ofertas primero)

Enumere los ID de usuario de todos los usuarios que no obtuvieron ni 1 recurso compartido después de que se hayan asignado todos los recursos compartidos.

Aporte

  • lista de ofertas
    de listas de enteros que representan [ID de usuario, # acciones, $ oferta, marca de tiempo]
  • totalShares
    # total de acciones a distribuir.

Que hacer

Distribuya acciones entre los postores y devuelva los ID de usuario de los postores que obtuvieron 0 acciones.

Compartir lógica de distribución:

  1. el postor con la oferta más alta obtiene todas las acciones por las que oferta y luego
  2. si hay empates en el precio de oferta de $, asigne acciones al postor anterior.

Siento que la solución que se me ocurrió es relativamente simple. Parece pasar todos los casos extremos que puedo pensar.

Pregunta

Encontré una situación cuestionable:
el precio de la oferta y los tiempos son los mismos y no hay suficientes acciones para todos los postores, es decir, bidses [[0,2,10,0], [1,2,10,0]]y totalShareses 2. No está claro si se debe dar 1 recurso compartido a cada uno, o si el ID de usuario 0 solo obtiene ambos.

Código

¿Se puede optimizar mi solución de todos modos?

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

Respuestas

2 RootTwo Aug 18 2020 at 09:39

Utilice el nombre de función dado en el problema:

def getUnallottedUsers(bids, totalShares):

El problema no proporciona ninguna información sobre la probabilidad de que haya suficientes acciones para todos los postores, por lo que, en mi opinión, el primer ciclo for es un ejemplo de optimización prematura.

Utilice constantes en lugar de "números mágicos". Utilice nombres significativos. Eche un vistazo a PEP8 sobre convenciones de formato comunes. Estas cosas contribuyen en gran medida a hacer que el código sea legible.

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 la pregunta que se le hizo: "La función debe devolver una lista de números enteros, cada uno de ellos una identificación para aquellos postores que no reciben acciones, ordenados de forma ascendente "

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

O usa un iterador:

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

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