공모 경매

Question

이미지 전사 :

회사가 IPO에 등록합니다. 입찰 창이라고하는 기간 동안 입찰을 위해 웹 사이트에서 모든 주식을 사용할 수 있습니다. 입찰 기간이 끝날 때 경매 로직을 사용하여 모든 주식이 할당되거나 모든 입찰자가 입찰 한 주식을 수령 할 때까지 어느 입찰자에게 어떤 가용 주식을 보낼지 결정합니다.

입찰은 입찰 창이 닫힐 때까지 [사용자 ID, # 공유, 입찰 가격, 타임 스탬프] 형식으로 사용자로부터 도착합니다.

경매 로직은 다음과 같이 주식을 할당합니다.

1. 가장 높은 가격을 가진 입찰자는 입찰 한 주식 수를받습니다.

2. 여러 입찰자가 동일한 가격으로 입찰 한 경우 입찰자에게 입찰 한 순서대로 주식이 할당됩니다 (가장 빠른 입찰부터)

모든 공유가 할당 된 후 하나의 공유도 얻지 못한 모든 사용자의 사용자 ID를 나열하십시오.

입력

• 
  [userid, # sharing, $ bid, timestamp]를 나타내는 int 목록의 입찰 목록
• totalShares
  분배 할 총 공유 수입니다.

할 것

입찰자에게 주식을 분배하고 0 주를 얻은 입찰자의 사용자 ID를 반환합니다.

분배 로직 공유 :

1. 가장 높은 제안을 가진 입찰자는 그들이 입찰 한 모든 주식을 얻습니다.
2. $ 입찰 가격에 동점이 있으면 이전 입찰자에게 주식을 할당합니다.

내가 생각 해낸 해결책은 비교적 간단하다고 느낍니다. 내가 생각할 수있는 모든 엣지 케이스를 통과 한 것 같습니다.

질문

나는 의심 상황을 발견 :
입찰 가격과 시간은 동일하며이 모든 입찰자에 대한 충분한 공유하지 않습니다 즉 : bids있습니다 [[0,2,10,0], [1,2,10,0]]및 totalShares입니다 2. 각각에 1 개의 공유를 제공해야하는지 아니면 사용자 ID 0이 둘 다 가져와야하는지 확실하지 않습니다.

암호

어쨌든 내 솔루션을 최적화 할 수 있습니까?

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

문제에 주어진 함수 이름을 사용하십시오.

def getUnallottedUsers(bids, totalShares):

이 문제는 모든 입찰자에게 충분한 지분이있을 가능성에 대한 정보를 제공하지 않으므로 IMO의 첫 번째 for-loop는 조기 최적화의 예입니다.

"매직 넘버"대신 상수를 사용하십시오. 의미있는 이름을 사용하십시오. 일반적인 형식 지정 규칙에 대한 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)