新規株式公開オークション

Aug 16 2020

画像の文字起こし:

会社がIPOに登録します。すべての株式は、入札ウィンドウと呼ばれる期間中に入札するためにWebサイトで利用できます。入札ウィンドウの最後に、オークションロジックを使用して、すべての株式が割り当てられるまで、またはすべての入札者が入札した株式を受け取るまで、利用可能な株式の数を決定します。

入札は、入札ウィンドウが閉じるまで、[ユーザーID、#シェア、入札価格、タイムスタンプ]の形式でユーザーから届きます。

オークションロジックは、次のように株式を割り当てます。

  1. 最高価格の入札者は、入札した株式数を取得します

  2. 複数の入札者が同じ価格で入札した場合、入札者には、入札した順序で株式が割り当てられます(最も早い入札が最初に)。

すべての共有が割り当てられた後、1つの共有も取得しなかったすべてのユーザーのユーザーIDを一覧表示します。

入力


  • [userid、#shares、$ bid、timestamp]を表すintのリストの入札リスト
  • totalShares
    配布される株式の総数。

Todo

入札者間で株式を分配し、0株を取得した入札者のユーザーIDを返します。

共有配布ロジック:

  1. オファーが最も高い入札者は、入札したすべての株式を取得してから、
  2. $入札価格に同点がある場合は、以前の入札者に株式を割り当てます。

私が思いついた解決策は比較的簡単だと思います。私が考えることができるすべてのエッジケースを通過するようです。

質問

疑わしい状況を見つけました。
入札価格と時間は同じであり、すべての入札者に十分なシェアがありません。つまり、bidsis[[0,2,10,0], [1,2,10,0]]totalSharesis2です。それぞれに1つの共有を与える必要があるのか​​、それともユーザーID0が両方を取得するだけなのかは不明です。

コード

とにかく私のソリューションを最適化できますか?

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

回答

2 RootTwo Aug 18 2020 at 09:39

問題で指定された関数名を使用します。

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

尋ねられた質問に答えてください:「関数は整数のリストを返す必要があります。各整数は、株式を受け取らない入札者のIDで、昇順ソートされています。」

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)