Đấu giá chào bán lần đầu ra công chúng
Phiên âm hình ảnh:
Một công ty đăng ký IPO. Tất cả các cổ phiếu có sẵn trên trang web để đấu giá trong một khung thời gian được gọi là cửa sổ đấu thầu. Vào cuối cửa sổ đặt giá thầu, logic đấu giá được sử dụng để quyết định có bao nhiêu cổ phiếu có sẵn sẽ được chuyển đến tay người đặt giá nào cho đến khi tất cả cổ phiếu được phân bổ hoặc tất cả những người đấu giá đã nhận được cổ phiếu mà họ đặt giá, tùy điều kiện nào đến trước.
Giá thầu đến từ người dùng dưới dạng [userid, # cổ phiếu, giá đấu thầu, dấu thời gian] cho đến khi cửa sổ đặt giá thầu đóng lại.
Logic đấu giá ấn định cổ phần như sau:
Người đặt giá cao nhất sẽ nhận được số cổ phiếu mà họ đấu giá
Nếu nhiều nhà thầu đặt giá thầu ở cùng một mức giá, thì những người đặt giá thầu sẽ được chuyển nhượng cổ phần theo thứ tự đặt giá thầu (trả giá sớm nhất trước)
Liệt kê các quyền sử dụng của tất cả những người dùng không nhận được dù chỉ 1 lượt chia sẻ sau khi tất cả các lượt chia sẻ đã được phân bổ.
Đầu vào
danh sách giá thầu của danh sách các int đại diện cho [userid, # cổ phiếu, $ giá thầu, dấu thời gian]- TotalShares
tổng số cổ phiếu được phân phối.
Làm
phân phối cổ phiếu giữa những người tham gia đấu giá và trả lại các quyền sử dụng của những người đấu giá có 0 cổ phiếu.
Chia sẻ logic phân phối:
- người đặt giá thầu với đề nghị cao nhất nhận được tất cả các cổ phần mà họ đặt giá thầu, và sau đó
- nếu có ràng buộc về giá đặt mua $, hãy chỉ định cổ phần cho người đặt giá thầu sớm hơn.
Tôi cảm thấy giải pháp mà tôi đưa ra tương đối đơn giản. Nó dường như vượt qua tất cả các trường hợp phức tạp mà tôi có thể nghĩ đến.
Câu hỏi
Tôi đã tìm thấy một tình huống đáng ngờ:
Giá dự thầu và thời gian đều giống nhau và không có đủ cổ phiếu cho tất cả các nhà thầu tức là: bidslà [[0,2,10,0], [1,2,10,0]]và totalShareslà 2. Không rõ liệu có nên trao 1 lượt chia sẻ cho mỗi người hay không, hay nếu userid 0 chỉ nhận được cả hai.
Mã
Giải pháp của tôi có thể được tối ưu hóa bằng cách nào không?
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
Trả lời
Sử dụng tên hàm đã cho trong bài toán:
def getUnallottedUsers(bids, totalShares):
Vấn đề không cung cấp bất kỳ thông tin nào về khả năng có đủ số lượt chia sẻ cho tất cả các nhà thầu, vì vậy IMO vòng lặp đầu tiên là một ví dụ về tối ưu hóa sớm.
Sử dụng hằng số thay vì "số ma thuật". Sử dụng tên có ý nghĩa. Hãy xem PEP8 về các quy ước định dạng phổ biến. Những điều này đi một chặng đường dài trong việc làm cho mã có thể đọc được.
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
Trả lời câu hỏi được đặt ra: "Hàm phải trả về danh sách các số nguyên, mỗi số là một id cho những người đặt giá thầu không nhận được cổ phiếu nào, được sắp xếp tăng dần "
return sorted(bid[USERID] for bid in bids[index + 1:])
Tất cả cùng nhau:
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:])
Hoặc sử dụng một trình lặp:
bids = iter(bids)
while totalShares > 0:
price = next(bid)[PRICE]
totalShares -= price
return sorted(bid[USERID] for bid in bids)