Enchère d'introduction en bourse

Aug 16 2020

Transcription d'images :

Une entreprise s'inscrit pour une introduction en bourse. Toutes les actions sont disponibles sur le site Web pour enchérir pendant une période appelée la fenêtre d'enchères. À la fin de la fenêtre d'enchères, une logique d'enchères est utilisée pour décider combien d'actions disponibles vont à quel enchérisseur jusqu'à ce que toutes les actions aient été attribuées, ou que tous les enchérisseurs aient reçu les actions pour lesquelles ils ont offert, selon la première éventualité.

Les enchères arrivent des utilisateurs sous la forme [ID utilisateur, # partages, prix de l'enchère, horodatage] jusqu'à la fermeture de la fenêtre d'enchères.

La logique d'enchères attribue les parts comme suit :

  1. L'enchérisseur avec le prix le plus élevé obtient le nombre d'actions pour lesquelles il a enchéri

  2. Si plusieurs enchérisseurs ont enchéri au même prix, les enchérisseurs se voient attribuer des parts dans l'ordre dans lequel ils placent leurs offres (les premières offres en premier)

Répertoriez les ID utilisateur de tous les utilisateurs qui n'ont même pas obtenu 1 partage après que tous les partages aient été alloués.

Saisir

  • bids
    liste de listes d'entiers représentant [userid, # partages, $bid, timestamp]
  • totalShares
    nombre total d'actions à distribuer.

Faire

répartir les actions entre les enchérisseurs et renvoyer les ID utilisateur des enchérisseurs qui ont obtenu 0 action.

Partager la logique de distribution :

  1. l'enchérisseur avec l'offre la plus élevée obtient toutes les actions pour lesquelles il a enchéri, puis
  2. s'il y a des liens dans le prix de l'offre en $, attribuez des actions au premier enchérisseur.

J'ai l'impression que la solution que j'ai trouvée est relativement simple. Il semble passer tous les cas extrêmes auxquels je peux penser.

Question

J'ai trouvé une situation douteuse :
le prix et les heures de l'enchère sont les mêmes et il n'y a pas assez de parts pour tous les enchérisseurs, c'est-à-dire : bidsest [[0,2,10,0], [1,2,10,0]]et totalSharesest 2. Il n'est pas clair si 1 partage doit être attribué à chacun, ou si l'ID utilisateur 0 obtient simplement les deux.

Code

Ma solution peut-elle être optimisée de toute façon ?

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

Réponses

2 RootTwo Aug 18 2020 at 09:39

Utilisez le nom de fonction donné dans le problème :

def getUnallottedUsers(bids, totalShares):

Le problème ne fournit aucune information sur la probabilité qu'il y ait suffisamment de parts pour tous les soumissionnaires, donc la première boucle for de l'OMI est un exemple d'optimisation prématurée.

Utilisez des constantes au lieu de "nombres magiques". Utilisez des noms significatifs. Jetez un œil à PEP8 sur les conventions de formatage courantes. Ces éléments contribuent grandement à rendre le code lisible.

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

Répondez à la question posée : "La fonction doit renvoyer une liste d'entiers, chacun un identifiant pour les enchérisseurs qui ne reçoivent aucune part, triés par ordre croissant "

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

Tous ensemble:

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 utilisez un itérateur :

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

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