Twenty people bid ₹2,000 on the same brass lamp in the same millisecond. One of them is the highest bidder. The other nineteen are told the new minimum at once, and the auction doesn't end while someone is still typing.
Every online auction looks the same from the outside: a current price, a "bid at least" number, a countdown, and an email saying you've been outbid. Underneath sit three problems. Validation must happen in one step with the write, or two bidders both "beat" the same price. Time is a participant: the auction must close at its deadline even when nobody touches it. And notifications must reach the outbid without the bidding path waiting on an email server.
This lesson builds it in one process: a small state machine, bids validated under a per-auction lock, a deadline heap, a soft close against sniping, and listeners that hear about everything after the lock is released.
How the round runs#
"Design the bidding engine for an auction site. Sellers list an item with a starting price and a duration. The highest bid at the end wins if it meets the seller's reserve. Notify bidders when they're outbid. Popular items get many bids at once. Show me running code; payments and search are out of scope."
- 0–10 min — clarify: increments, reserve, the last minute, retries, cancelling
- 10–20 min — the states, then
Auction,Bidand the event - 20–35 min — the seams:
IncrementPolicyandAuctionListener - 35–60 min —
AuctionHouse: a lock per auction, a heap of deadlines - 60–75 min — a fake-clock demo: rejections, a retry, extensions, a 20-thread race
- 75–90 min — follow-ups: proxy bidding, many servers, fraud, a sealed-bid auction
Requirements and clarifying questions#
| You ask | They answer | What it changes |
|---|---|---|
| How much must a bid beat the current one by? | A step that grows with the price. | An IncrementPolicy, tiered by price |
| A minimum the seller will accept? | Yes, a hidden reserve. | The close decides SOLD or UNSOLD |
| What if someone bids in the last second? | Give others time to respond. | Soft close: a bid in the last 2 minutes moves the end to 2 minutes after it |
| Can the client retry a bid? | Yes, on a flaky network. | A client-made bid_id; a retry returns the same bid |
| Can sellers bid, or bidders raise themselves? | Neither. | Two validation rules |
| Can the seller cancel? | Only before the first bid. | cancel checks the seller and the bid list |
| Proxy (automatic) bidding? | Follow-up. | Nothing now |
Draw the life cycle before any code
List the states of an auction and what moves it between them. Which transitions happen because someone did something, and which happen because the clock moved?
One strong answer
- Scheduled → Open: the start time passes (clock)
- Open → Open: an accepted bid, maybe moving the end (person)
- Open → Sold: the end passes, top bid meets the reserve (clock)
- Open → Unsold: the end passes, no bids or below reserve (clock)
- → Cancelled: the seller cancels before any bid (person)
Three transitions are driven by time alone. So something must notice deadlines when nobody calls the auction, and every method must first bring the state up to date with the clock, because the timer may not have run yet.
%% title: Online auction: states and events stateDiagram-v2 [*] --> Scheduled Scheduled --> Open: start time passes Scheduled --> Cancelled: seller cancels Open --> Open: bid accepted / late bid extends the end Open --> Cancelled: seller cancels, no bids yet Open --> Sold: end time, top bid meets reserve Open --> Unsold: end time, no bids or below reserve Sold --> [*] Unsold --> [*] Cancelled --> [*]
The classes#
%% title: Online auction: the classes
classDiagram
class Auction {
+auction_id str
+seller str
+start_price int
+reserve int
+ends_at float
+state AuctionState
+bids list
+leader Bid
}
class Bid {
+bid_id str
+bidder str
+amount int
+at float
}
class AuctionState {
<<enumeration>>
SCHEDULED
OPEN
SOLD
UNSOLD
CANCELLED
}
class IncrementPolicy {
<<interface>>
+min_increment(current) int
}
class AuctionListener {
<<interface>>
+on_event(event)
}
class AuctionEvent {
+kind str
+auction_id str
+to str
+text str
}
class AuctionHouse {
-deadlines heap
+create(seller, title, start, reserve, starts_at, duration) Auction
+place_bid(bid_id, auction_id, bidder, amount) Bid
+cancel(auction_id, by)
+close_due() list
}
Auction "1" *-- "many" Bid
Auction --> AuctionState
AuctionHouse "1" o-- "many" Auction
AuctionHouse --> IncrementPolicy
AuctionHouse --> AuctionListener
AuctionListener ..> AuctionEvent
IncrementPolicy <|.. TieredIncrement
AuctionListener <|.. PrintNotifierThree decisions to say out loud:
- An auction keeps only accepted bids, each higher than the last, so the leader is always
bids[-1]and the history is the audit trail. - Each auction has its own lock. Bids on the lamp never wait for bids on the poster. The house lock guards only the dict and the deadline heap.
- Listeners get plain event objects after the lock is released.
The interfaces#
The clock, the states, the bid, the auction and the event:
# auction.py, part 1: time, bids, and the auction's life cycle
from __future__ import annotations
import heapq
import itertools
import threading
from abc import ABC, abstractmethod
from dataclasses import dataclass, field
from enum import Enum
class Clock(ABC):
@abstractmethod
def now(self) -> float: ... # seconds
class FakeClock(Clock):
def __init__(self, t: float = 0.0) -> None:
self.t = t
def now(self) -> float:
return self.t
class AuctionState(Enum):
SCHEDULED = "scheduled"
OPEN = "open"
SOLD = "sold"
UNSOLD = "unsold"
CANCELLED = "cancelled"
@dataclass(frozen=True)
class Bid:
bid_id: str # made by the client, so a retried request carries the same id
bidder: str
amount: int # whole rupees, never floats
at: float
@dataclass
class Auction:
auction_id: str
seller: str
title: str
start_price: int
reserve: int # hidden floor; below it the item doesn't sell
starts_at: float
ends_at: float # moves later on a late bid (soft close)
state: AuctionState = AuctionState.SCHEDULED
bids: list[Bid] = field(default_factory=list) # accepted bids only, each higher than the last
by_id: dict[str, Bid] = field(default_factory=dict) # bid_id -> bid, to answer retries
extensions: int = 0
lock: threading.Lock = field(default_factory=threading.Lock, repr=False)
@property
def leader(self) -> Bid | None:
return self.bids[-1] if self.bids else None
@dataclass(frozen=True)
class AuctionEvent:
kind: str # "outbid" | "extended" | "won" | "sold" | "unsold"
auction_id: str
to: str # a user id, or "watchers"
text: strThe two seams:
# part 2: the two seams: the minimum raise, and who hears about it
class IncrementPolicy(ABC):
@abstractmethod
def min_increment(self, current: int) -> int: ...
class TieredIncrement(IncrementPolicy):
"""The higher the price, the bigger the smallest step, so ₹1 raises can't stall a ₹50,000 item."""
TIERS = ((1_000, 50), (10_000, 200), (100_000, 1_000))
def min_increment(self, current: int) -> int:
for below, step in self.TIERS:
if current < below:
return step
return 5_000
class AuctionListener(ABC):
@abstractmethod
def on_event(self, event: AuctionEvent) -> None: ...
class PrintNotifier(AuctionListener):
"""Stands in for push, email and SMS."""
def on_event(self, event: AuctionEvent) -> None:
print(f" -> {event.to}: {event.kind}, {event.text}")With these tiers a ₹1,000 leader needs ₹1,200 to be beaten and a ₹4,800 leader needs ₹5,000.
The patterns, and why#
| Pattern | Where | Why it earns its place |
|---|---|---|
| State (an enum + one transition function) | AuctionState, _advance |
One function moves the state forward by time; the bid path checks the state first. |
| Observer | AuctionListener, AuctionEvent |
Outbid emails, the live price and the audit log subscribe; the auction knows none of them. |
| Strategy | IncrementPolicy |
Increment tables change by category. A new table is a new class. |
| Idempotency key | bid_id |
A retried bid returns the original instead of becoming a second one. |
| Heap with lazy deletion | the deadline heap | An extended auction gets a new entry; the old one is skipped when it pops. |
Concurrency and edge cases#
The race between bids is the one the interviewer is testing. Twenty bidders see "minimum ₹2,000" and all send ₹2,000. If validation and the append are separate steps, several pass the check. The fix: validate-then-append is one step under the auction's lock. The first thread appends; the other nineteen re-read the leader under the same lock, see a minimum of ₹2,200, and are rejected with that number.
The race between a bid and the deadline: a bid at 59:59.9, the closing timer at 60:00.0. Both take the auction lock, so one goes first. If the bid wins, the soft close pushes the end out and the timer's entry goes stale. If the timer wins, the bid sees SOLD. And because the bid path calls _advance first, a bid at 60:00.5 is rejected even if the timer hasn't run: the clock, not the timer, decides when an auction ends.
Lock order: a bid holds the auction lock, then briefly takes the house lock to push a deadline. close_due takes the house lock, pops, releases it, and only then takes auction locks. Nothing holds the house lock while waiting for an auction lock, so they can't deadlock.
- A bid exactly at the deadline: the end is exclusive;
now >= ends_atmeans closed - A retry after the close: it finds its
bid_idand returns the accepted bid; it was valid when it arrived - Endless extensions: two bots can extend forever; cap them (10 here)
- The leader raising their own bid: rejected; with proxy bidding it becomes "raise your maximum"
- The seller bidding from a second account: a fraud signal, not something this code can catch
- A listener that throws: caught per listener, so one broken sender doesn't stop the others
The code#
The house: create, bid, cancel, and close.
# part 3: the auction house: create, bid, close, with one lock per auction
class BidRejected(Exception): ...
class AuctionHouse:
def __init__(self, clock: Clock, increments: IncrementPolicy, snipe_window: float = 120.0, max_extensions: int = 10) -> None:
self.clock, self.increments = clock, increments
self.snipe_window, self.max_extensions = snipe_window, max_extensions
self.auctions: dict[str, Auction] = {}
self._listeners: list[AuctionListener] = []
self._deadlines: list[tuple[float, str]] = [] # min-heap of (ends_at, id); stale entries are skipped
self._mu = threading.Lock() # guards the dict and the heap; never held while taking an auction's lock
self._ids = itertools.count(1)
def subscribe(self, listener: AuctionListener) -> None:
self._listeners.append(listener)
def create(self, seller: str, title: str, start_price: int, reserve: int, starts_at: float, duration: float) -> Auction:
if start_price <= 0 or duration <= 0:
raise ValueError("start price and duration must be positive")
with self._mu:
a = Auction(f"A{next(self._ids)}", seller, title, start_price, reserve, starts_at, starts_at + duration)
self.auctions[a.auction_id] = a
heapq.heappush(self._deadlines, (a.ends_at, a.auction_id))
return a
def min_next_bid(self, a: Auction) -> int:
lead = a.leader
return a.start_price if lead is None else lead.amount + self.increments.min_increment(lead.amount)
def place_bid(self, bid_id: str, auction_id: str, bidder: str, amount: int) -> Bid:
a = self.auctions[auction_id]
events: list[AuctionEvent] = []
try:
with a.lock: # validate-then-append is one step per auction
if bid_id in a.by_id:
return a.by_id[bid_id] # a retried request: same answer, no second bid
now = self.clock.now()
self._advance(a, now, events) # the timer may not have closed it yet
if a.state is not AuctionState.OPEN:
raise BidRejected(f"auction is {a.state.value}")
if bidder == a.seller:
raise BidRejected("sellers can't bid on their own item")
prev = a.leader
if prev and prev.bidder == bidder:
raise BidRejected("you're already the highest bidder")
if amount < (need := self.min_next_bid(a)):
raise BidRejected(f"bid at least {need}")
bid = Bid(bid_id, bidder, amount, now)
a.bids.append(bid)
a.by_id[bid_id] = bid
if prev:
events.append(AuctionEvent("outbid", a.auction_id, prev.bidder, f"{bidder} bid {amount}"))
if a.ends_at - now < self.snipe_window and a.extensions < self.max_extensions:
a.ends_at, a.extensions = now + self.snipe_window, a.extensions + 1
with self._mu: # lock order: auction, then house; close_due never holds both
heapq.heappush(self._deadlines, (a.ends_at, a.auction_id))
events.append(AuctionEvent("extended", a.auction_id, "watchers", f"now ends at {a.ends_at:.0f}"))
return bid
finally:
self._publish(events) # runs after the lock is released, even when the bid is rejected
def cancel(self, auction_id: str, by: str) -> None:
a = self.auctions[auction_id]
with a.lock:
self._advance(a, self.clock.now(), [])
if by != a.seller or a.bids or a.state not in (AuctionState.SCHEDULED, AuctionState.OPEN):
raise BidRejected("only the seller can cancel, and only before the first bid")
a.state = AuctionState.CANCELLED # its heap entry is skipped when it comes up
def close_due(self) -> list[Auction]:
"""Called by a timer every second; returns the auctions this call closed."""
now = self.clock.now()
with self._mu:
due = []
while self._deadlines and self._deadlines[0][0] <= now:
due.append(heapq.heappop(self._deadlines)[1])
closed = []
for auction_id in due:
a, events = self.auctions[auction_id], []
with a.lock:
if self._advance(a, now, events): # a stale entry for an extended auction does nothing
closed.append(a)
self._publish(events)
return closed
def _advance(self, a: Auction, now: float, events: list[AuctionEvent]) -> bool:
"""Move the state forward by time alone. Caller holds a.lock. True if this call closed the auction."""
if a.state is AuctionState.SCHEDULED and now >= a.starts_at:
a.state = AuctionState.OPEN
if a.state is not AuctionState.OPEN or now < a.ends_at:
return False
lead = a.leader
if lead and lead.amount >= a.reserve:
a.state = AuctionState.SOLD
events.append(AuctionEvent("won", a.auction_id, lead.bidder, f"{a.title} for {lead.amount}"))
events.append(AuctionEvent("sold", a.auction_id, a.seller, f"to {lead.bidder} for {lead.amount}"))
else:
a.state = AuctionState.UNSOLD
events.append(AuctionEvent("unsold", a.auction_id, a.seller, "reserve not met" if lead else "no bids"))
return True
def _publish(self, events: list[AuctionEvent]) -> None:
for e in events:
for listener in self._listeners:
try:
listener.on_event(e)
except Exception:
pass # one broken listener must not stop the others (log it in real code)Two lines carry the design: _advance at the top of place_bid brings the state up to date before a bid is judged, and the finally publishes events only after the lock is released.
The demo runs on a fake clock, so the deadlines are exact:
# part 4: a poster auction with a soft close, a reserve that isn't met, and a 20-thread race
if __name__ == "__main__":
clock = FakeClock(0.0)
house = AuctionHouse(clock, TieredIncrement())
house.subscribe(PrintNotifier())
poster = house.create("meera", "1975 film poster", start_price=1_000, reserve=5_000, starts_at=0.0, duration=3_600)
def bid(a: Auction, bid_id: str, who: str, amount: int, at: float) -> None:
clock.t = at
try:
house.place_bid(bid_id, a.auction_id, who, amount)
print(f"t={at:.0f} {who} {amount}: accepted, ends at {a.ends_at:.0f}")
except BidRejected as e:
print(f"t={at:.0f} {who} {amount}: rejected, {e}")
bid(poster, "b1", "asha", 1_000, 10)
bid(poster, "b2", "ravi", 1_100, 20) # under the ₹200 step
bid(poster, "b3", "ravi", 1_200, 30)
bid(poster, "b3", "ravi", 1_200, 31) # the same request, retried
print("bids on record:", len(poster.bids)) # 2
bid(poster, "b4", "meera", 1_500, 40) # the seller
bid(poster, "b5", "asha", 4_800, 50)
bid(poster, "b6", "ravi", 5_000, 3_590) # 10 s left: the end moves to 3590 + 120
clock.t = 3_600
print("closed at 3600:", house.close_due()) # the original deadline is now a stale entry
bid(poster, "b7", "asha", 5_200, 3_700) # 10 s left again
clock.t = 3_820
print("closed at 3820:", [(a.auction_id, a.state.value) for a in house.close_due()])
bid(poster, "b8", "ravi", 6_000, 3_821)
stamps = house.create("meera", "stamp album", start_price=500, reserve=2_000, starts_at=4_000, duration=600)
bid(stamps, "s1", "ravi", 500, 3_990) # not open yet
bid(stamps, "s2", "ravi", 500, 4_100)
clock.t = 4_600
print("closed at 4600:", [(a.auction_id, a.state.value) for a in house.close_due()])
race = AuctionHouse(FakeClock(100.0), TieredIncrement())
lamp = race.create("dev", "brass lamp", start_price=2_000, reserve=2_000, starts_at=0.0, duration=3_600)
accepted: list[Bid] = []
rejected: list[str] = []
def rush(i: int) -> None:
try:
accepted.append(race.place_bid(f"r{i}", lamp.auction_id, f"user{i}", 2_000))
except BidRejected as e:
rejected.append(str(e))
ts = [threading.Thread(target=rush, args=(i,)) for i in range(20)]
for t in ts:
t.start()
for t in ts:
t.join()
print(len(accepted), "accepted,", len(rejected), "rejected:", set(rejected), "| bids on record:", len(lamp.bids))t=10 asha 1000: accepted, ends at 3600
t=20 ravi 1100: rejected, bid at least 1200
-> asha: outbid, ravi bid 1200
t=30 ravi 1200: accepted, ends at 3600
t=31 ravi 1200: accepted, ends at 3600
bids on record: 2
t=40 meera 1500: rejected, sellers can't bid on their own item
-> ravi: outbid, asha bid 4800
t=50 asha 4800: accepted, ends at 3600
-> asha: outbid, ravi bid 5000
-> watchers: extended, now ends at 3710
t=3590 ravi 5000: accepted, ends at 3710
closed at 3600: []
-> ravi: outbid, asha bid 5200
-> watchers: extended, now ends at 3820
t=3700 asha 5200: accepted, ends at 3820
-> asha: won, 1975 film poster for 5200
-> meera: sold, to asha for 5200
closed at 3820: [('A1', 'sold')]
t=3821 ravi 6000: rejected, auction is sold
t=3990 ravi 500: rejected, auction is scheduled
t=4100 ravi 500: accepted, ends at 4600
-> meera: unsold, reserve not met
closed at 4600: [('A2', 'unsold')]
1 accepted, 19 rejected: {'bid at least 2200'} | bids on record: 1Ravi's retried b3 returns the same bid: still two on record. Ravi's ₹5,000 with ten seconds left moves the end to 3710, so the deadline at 3600 closes nothing; Asha's ₹5,200 moves it to 3820, and the poster sells to her above the ₹5,000 reserve. The stamp album's ₹500 misses its reserve. Twenty threads bidding ₹2,000 on the lamp: one accepted, nineteen told the new minimum, ₹2,200.
Extending it: the follow-ups#
- "Add proxy bidding." A bidder sets a secret maximum and the system bids for them by the minimum step, up to it. Store
max_amountper bidder and settle each contest under the same lock, so the visible price lands one step above the lower maximum. A change insideplace_bid, not a new service. - "We have many servers." Give each auction one owner (partition by
auction_id) so the lock stays local; or make the append a conditional database write (UPDATE … WHERE id = :id AND price = :seen_price) and retry on zero rows. The heap becomes a scheduled-jobs table. - "A sealed-bid auction." Same states, different rules for "accept" and "pick the winner": hidden bids, and the top bidder pays their bid (or the second-highest price). Those two rules become strategies.
- "The winner never pays." A new state after
SOLD,AWAITING_PAYMENT, with a deadline; on expiry, offer the item to the next bidder above the reserve. The bid history already holds the list.
Common mistakes#
- Checking the amount, then appending, in two steps, so equal concurrent bids both win
- One global lock for every auction, so a hot item slows the whole site
- Trusting the timer alone, so a bid after the deadline but before the timer runs is accepted
- Sending emails inside the lock, so a slow mail server blocks every bidder
- Floats for money
- No idempotency key, so a mobile retry turns one bid into two
Online auction
Q1/3 Twenty threads bid ₹2,000 at the same moment on an auction whose minimum is ₹2,000. What makes exactly one of them win?
Answer & explanation
Answer: B
Under the auction's lock, the first thread appends ₹2,000; every later thread re-reads the leader under the same lock, sees a minimum of ₹2,200 and is rejected. A lock per auction keeps other auctions out of the queue.
Q2/3 The deadline is 3600. A bid arrives at 3601, and the closing timer hasn't run yet. What should happen?
Answer & explanation
Answer: C
The clock decides when an auction ends, not the timer. place_bid calls _advance first, which closes the auction as of now; the bid then sees SOLD or UNSOLD and is rejected.
Q3/3 A bid at 3590 extends the auction to 3710. What happens to the heap entry for 3600?
Answer & explanation
Answer: B
Lazy deletion: push a new (3710, id) entry and let the old one go stale. Popping it costs O(log n) and changes nothing, which is cheaper and simpler than finding and removing it.
New lessons by email
New lessons, side quests and case files as they ship, at most once a week. No spam, unsubscribe anytime.
Discussion · …
Public: everyone reading this lesson sees comments. Be kind and keep it on the material.