On this page

Design an Online Auction System

Most LLD case studies have one concurrency hotspot hidden among a dozen ordinary features. An auction turns that around. Concurrency is the problem. In the last minute of a popular auction, hundreds of bids arrive for the same object, each one reading "what's the current price?" and trying to write "now it's mine". Every interesting rule (minimum increment, closing time, anti-sniping) is checked against that same contended state, at the same instant.

So the interview tends to go like this. Five minutes to model auctions and bids, five minutes on validation, and then the interviewer leans in: "Two people bid at the same millisecond. Walk me through what happens." This page builds the design so that question has a crisp answer, and shows two correct answers: a lock-free compare-and-set (Java) and a lock per auction (Python), with the trade-offs between them.

The scope is one process with in-memory state. A distributed auction house adds sharding by auction id and a durable bid log. The class design below is what runs inside each shard.

1. Requirements

Clarifying questions

QuestionAnswer we assume
Auction format?English (ascending, open) auction. Highest bid at close wins and pays its own bid
Minimum increment?Pluggable: fixed, or tiered by current price
Reserve price?Optional and hidden. Below it at close means unsold
Can the seller bid?No
Can the leader raise their own bid?Yes, but it isn't an "outbid" event
How does an auction end?At its end time. Variant: a bid in the last 2 minutes extends it (anti-sniping)
Can the seller cancel?Only before the first bid
Notifications?Outbid, extended, won, sold, unsold
Payment?Charge the winner on close. If it fails, a second-chance offer (an extension)
Proxy (automatic) bidding?An extension

Functional requirements

  1. A seller creates an auction: starting price, optional reserve, start and end times, increment and end-time policies.
  2. Bidders place bids. A bid is accepted only if the auction is running, it's not from the seller, and it meets the minimum (the start price, or the current highest plus the increment).
  3. Bidders who lose the lead are notified.
  4. At the end time the auction closes exactly once. The highest bid at or above the reserve wins and is charged.
  5. With anti-sniping enabled, a bid inside the closing window extends the end time.

Non-functional requirements

  • No lost bids. If a bid is reported accepted, it's in the history and the final result accounts for it.
  • No bid after close. A bid is either accepted before the close or rejected.
  • Settlement exactly once, even with several schedulers sweeping.
  • Validation and end-time rules are swappable. The clock is injected.

2. Entities

EntityKindNotes
AuctionEntity, aggregate rootseller, start price, reserve, start time, policies, and the contended state
AuctionStateImmutable valuehighest bid, current end time, phase. Replaced as a whole
BidImmutable valuebidder, amount, time, and the bid it beat
IncrementPolicyStrategyminimum step from the current price
EndTimePolicyStrategyfixed end, or anti-sniping extension
AuctionResultValueoutcome, winner, price, paid
AuctionObserverObserveronBid, onExtended, onClosed
PaymentGatewayPortidempotent charge
AuctionServiceFacadecreate, bid, sweep-and-settle, fan out events

Two modelling choices carry the design.

Everything a bid can change lives in one immutable object. A bid can change the highest bid, the end time (anti-sniping) and, by racing the closer, effectively the phase. If those were three separate fields, you'd need a lock to update them together. As one immutable AuctionState, a single atomic reference swap updates all three at once. That's what makes the lock-free version possible.

The bid history is a chain. In an ascending auction every accepted bid becomes the new highest bid. So Bid.previous (the bid it beat) gives the full, correctly ordered history for free. We don't need a separate list appended after the CAS, which would be a second write that could interleave out of order. The chain also gives you "the runner-up" for second-chance offers.

classDiagram
    class AuctionService {
        +create(seller, start, reserve, startsAt, endsAt, inc, end) Auction
        +placeBid(auctionId, bidderId, amount) Bid
        +closeExpired() int
        +subscribe(observer)
    }
    class Auction {
        +id
        +sellerId
        +startingPriceCents
        +reservePriceCents
        +startsAt
        -state AtomicReference~AuctionState~
        +result AuctionResult
        +minimumNextBid(state) long
        +placeBid(bidder, amount, now) AuctionState
        +tryClose(now) boolean
        +cancel()
    }
    class AuctionState {
        +highest Bid
        +endsAt
        +phase Phase
    }
    class Bid {
        +bidderId
        +amountCents
        +at
        +previous Bid
    }
    class IncrementPolicy {
        <<interface>>
        +minIncrementCents(current) long
    }
    class EndTimePolicy {
        <<interface>>
        +endAfterBid(currentEnd, bidAt) Instant
    }
    class AuctionObserver {
        <<interface>>
        +onBid(auction, bid, outbidBidder)
        +onExtended(auction, newEnd)
        +onClosed(auction, result)
    }
    class PaymentGateway {
        <<interface>>
        +charge(user, cents, key) boolean
    }
    class AuctionResult {
        +outcome
        +winnerId
        +priceCents
        +paid
    }
    AuctionService o-- "*" Auction
    AuctionService o-- "*" AuctionObserver
    AuctionService --> PaymentGateway
    Auction --> IncrementPolicy
    Auction --> EndTimePolicy
    Auction *-- AuctionState
    Auction --> AuctionResult
    AuctionState --> Bid : highest
    Bid --> Bid : previous
    IncrementPolicy <|.. FixedIncrement
    IncrementPolicy <|.. TieredIncrement
    EndTimePolicy <|.. FixedEnd
    EndTimePolicy <|.. AntiSniping
    AuctionObserver <|.. Inbox

3. Lifecycle

stateDiagram-v2
    [*] --> SCHEDULED : created
    SCHEDULED --> RUNNING : start time reached
    SCHEDULED --> CANCELLED : seller cancels
    RUNNING --> RUNNING : bid accepted, end may extend
    RUNNING --> CANCELLED : seller cancels, no bids yet
    RUNNING --> CLOSED : end time reached, closer wins the CAS
    CLOSED --> SOLD : highest at or above reserve, winner charged
    CLOSED --> UNSOLD : no bids or reserve not met
    SOLD --> [*]
    UNSOLD --> [*]
    CANCELLED --> [*]

SCHEDULED isn't stored. It's derived as now < startsAt, so nothing has to "start" an auction. CLOSED is stored, because the transition must happen exactly once and bids must see it. SOLD/UNSOLD live in AuctionResult, written once by whichever caller won the close.

4. Key flows

A bid, lock-free

sequenceDiagram
    participant B as Bidder
    participant S as AuctionService
    participant A as Auction
    participant R as AtomicReference
    participant O as Observers
    B->>S: placeBid A1, bob, 1100
    S->>A: placeBid bob, 1100, now
    A->>R: get, snapshot s
    A->>A: running, before end, 1100 at least 1000 + 100
    A->>A: next = Bid bob 1100 beating ann, end from policy
    A->>R: compareAndSet s to next
    R-->>A: true
    A-->>S: replaced state s
    S->>O: onBid bob 1100, outbid ann

Two bids at the same millisecond

sequenceDiagram
    participant X as Bid X 1200
    participant R as State ref
    participant Y as Bid Y 1300
    X->>R: get, highest 1100
    Y->>R: get, highest 1100
    X->>R: CAS from 1100-state to 1200-state
    R-->>X: true
    Y->>R: CAS from 1100-state to 1300-state
    R-->>Y: false, state changed
    Y->>R: get again, highest 1200
    Y->>Y: 1300 at least 1200 + 100, still valid
    Y->>R: CAS from 1200-state to 1300-state
    R-->>Y: true
    Note over X,Y: Had Y bid 1250, the retry would reject it as below 1300

Close and settle

sequenceDiagram
    participant K as Scheduler
    participant S as AuctionService
    participant A as Auction
    participant P as PaymentGateway
    participant O as Observers
    K->>S: closeExpired
    S->>A: tryClose now
    A->>A: CAS RUNNING to CLOSED, only one caller succeeds
    A-->>S: true
    S->>S: highest 1600 at least reserve 1500
    S->>P: charge ann 1600, key A1 win
    P-->>S: ok
    S->>O: onClosed SOLD ann 1600

5. Patterns, and why

PatternWhereWhyRejected alternative
Immutable snapshot + CASAuctionState in an AtomicReferenceValidate and publish atomically without blockingsynchronized everywhere, which is valid and is the Python version. See below
StrategyIncrementPolicy, EndTimePolicyIncrements and closing rules vary by category and marketplaceFlags such as antiSnipingEnabled inside placeBid
ObserverAuctionObserver, InboxNotifications, proxy bidding, analytics and watchers all react to bidsThe service calling an email client inline
Persistent (linked) historyBid.previousHistory that's ordered by constructionA list appended after the CAS, which can be reordered between threads
FacadeAuctionServiceOne place for settlement and fan-outCallers settling auctions themselves
Injected clockSupplier<Instant>Closing and anti-sniping depend on timeInstant.now() in Auction

Why is anti-sniping a Strategy and not a subclass AntiSnipingAuction? The rule is one function, "given the current end and the bid time, what's the new end?". Passing it in keeps Auction closed for modification. It also composes: a marketplace can use tiered increments with fixed ends for one category and anti-sniping for another, which would need four subclasses.

Why no State pattern? There are three stored phases, and every check is "is it RUNNING?". The tricky part is atomicity, not behaviour that varies by state.

6. The code

Each file is complete, runnable, and ends with asserts. The Java main runs a 16-thread lost-update test and a 1000-round bid-versus-close race. Save the Python as online_auction.py for the tests.

import java.time.*;
import java.util.*;
import java.util.concurrent.*;
import java.util.concurrent.atomic.*;
import java.util.function.Supplier;

/** An accepted bid. `previous` is the bid it beat, so the leader chain is the bid history. */
record Bid(String bidderId, long amountCents, Instant at, Bid previous) {}

enum Phase { RUNNING, CLOSED, CANCELLED }

/** Immutable snapshot of everything a bid can change. Replaced whole with one CAS. */
record AuctionState(Bid highest, Instant endsAt, Phase phase) {}

enum Outcome { SOLD, UNSOLD }

record AuctionResult(Outcome outcome, String winnerId, long priceCents, boolean paid) {}

class AuctionException extends RuntimeException {
    AuctionException(String message) { super(message); }
}

interface IncrementPolicy { long minIncrementCents(long currentCents); }

final class FixedIncrement implements IncrementPolicy {
    private final long cents;
    FixedIncrement(long cents) { this.cents = cents; }
    public long minIncrementCents(long current) { return cents; }
}

/** Bigger prices, bigger steps: under 10.00 step 0.50, under 100.00 step 1.00, else 5.00. */
final class TieredIncrement implements IncrementPolicy {
    public long minIncrementCents(long current) { return current < 1000 ? 50 : current < 10000 ? 100 : 500; }
}

interface EndTimePolicy { Instant endAfterBid(Instant currentEnd, Instant bidAt); }

final class FixedEnd implements EndTimePolicy {
    public Instant endAfterBid(Instant currentEnd, Instant bidAt) { return currentEnd; }
}

/** A bid in the last `window` pushes the end to bidAt + `extension`, so sniping stops paying off. */
final class AntiSniping implements EndTimePolicy {
    private final Duration window, extension;
    AntiSniping(Duration window, Duration extension) { this.window = window; this.extension = extension; }
    public Instant endAfterBid(Instant currentEnd, Instant bidAt) {
        if (Duration.between(bidAt, currentEnd).compareTo(window) >= 0) return currentEnd;
        Instant pushed = bidAt.plus(extension);
        return pushed.isAfter(currentEnd) ? pushed : currentEnd;
    }
}

final class Auction {
    final String id, sellerId; final long startingPriceCents, reservePriceCents; final Instant startsAt;
    private final IncrementPolicy increments; private final EndTimePolicy endPolicy;
    private final AtomicReference<AuctionState> state;
    volatile AuctionResult result;                            // written once, by whoever closed it

    Auction(String id, String sellerId, long startingPriceCents, long reservePriceCents, Instant startsAt, Instant endsAt,
            IncrementPolicy increments, EndTimePolicy endPolicy) {
        if (!startsAt.isBefore(endsAt)) throw new AuctionException("must end after it starts");
        this.id = id; this.sellerId = sellerId; this.startingPriceCents = startingPriceCents;
        this.reservePriceCents = reservePriceCents; this.startsAt = startsAt;
        this.increments = increments; this.endPolicy = endPolicy;
        this.state = new AtomicReference<>(new AuctionState(null, endsAt, Phase.RUNNING));
    }

    AuctionState state() { return state.get(); }

    long minimumNextBid(AuctionState s) {
        return s.highest() == null ? startingPriceCents
                                   : s.highest().amountCents() + increments.minIncrementCents(s.highest().amountCents());
    }

    /** Lock-free: validate against a snapshot, publish with CAS, retry if another bid got in first. */
    AuctionState placeBid(String bidderId, long amountCents, Instant now) {
        if (bidderId.equals(sellerId)) throw new AuctionException("sellers cannot bid on their own item");
        if (now.isBefore(startsAt)) throw new AuctionException("auction has not started");
        while (true) {
            AuctionState s = state.get();
            if (s.phase() != Phase.RUNNING || !now.isBefore(s.endsAt())) throw new AuctionException("auction is closed");
            long min = minimumNextBid(s);
            if (amountCents < min) throw new AuctionException("bid must be at least " + min);
            Bid bid = new Bid(bidderId, amountCents, now, s.highest());
            AuctionState next = new AuctionState(bid, endPolicy.endAfterBid(s.endsAt(), now), Phase.RUNNING);
            if (state.compareAndSet(s, next)) return s;       // the state we replaced
        }
    }

    /** Exactly one caller ever gets true, so settlement runs once. */
    boolean tryClose(Instant now) {
        while (true) {
            AuctionState s = state.get();
            if (s.phase() != Phase.RUNNING || now.isBefore(s.endsAt())) return false;
            if (state.compareAndSet(s, new AuctionState(s.highest(), s.endsAt(), Phase.CLOSED))) return true;
        }
    }

    void cancel() {
        while (true) {
            AuctionState s = state.get();
            if (s.phase() != Phase.RUNNING) throw new AuctionException("auction already finished");
            if (s.highest() != null) throw new AuctionException("cannot cancel after the first bid");
            if (state.compareAndSet(s, new AuctionState(null, s.endsAt(), Phase.CANCELLED))) return;
        }
    }
}

interface AuctionObserver {
    default void onBid(Auction a, Bid bid, String outbidBidderId) {}
    default void onExtended(Auction a, Instant newEnd) {}
    default void onClosed(Auction a, AuctionResult result) {}
}

interface PaymentGateway { boolean charge(String userId, long cents, String idempotencyKey); }

final class AuctionService {
    private final Map<String, Auction> auctions = new ConcurrentHashMap<>();
    private final List<AuctionObserver> observers = new CopyOnWriteArrayList<>();
    private final AtomicLong ids = new AtomicLong();
    private final Supplier<Instant> clock; private final PaymentGateway payments;

    AuctionService(Supplier<Instant> clock, PaymentGateway payments) { this.clock = clock; this.payments = payments; }

    void subscribe(AuctionObserver o) { observers.add(o); }
    Auction get(String id) {
        Auction a = auctions.get(id);
        if (a == null) throw new AuctionException("unknown auction " + id);
        return a;
    }

    Auction create(String sellerId, long startCents, long reserveCents, Instant startsAt, Instant endsAt,
                   IncrementPolicy inc, EndTimePolicy end) {
        Auction a = new Auction("A" + ids.incrementAndGet(), sellerId, startCents, reserveCents, startsAt, endsAt, inc, end);
        auctions.put(a.id, a);
        return a;
    }

    Bid placeBid(String auctionId, String bidderId, long amountCents) {
        Auction a = get(auctionId);
        AuctionState before = a.placeBid(bidderId, amountCents, clock.get());
        AuctionState after = a.state();
        // notify outside any critical section; a newer bid may already exist, so report our own
        Bid mine = findOwn(after.highest(), bidderId, amountCents);
        String outbid = before.highest() == null || before.highest().bidderId().equals(bidderId) ? null : before.highest().bidderId();
        for (AuctionObserver o : observers) safely(() -> o.onBid(a, mine, outbid));
        if (mine != null && after.endsAt().isAfter(before.endsAt()))
            for (AuctionObserver o : observers) safely(() -> o.onExtended(a, after.endsAt()));
        return mine;
    }

    /** Run from a scheduler. Returns how many auctions this call settled. */
    int closeExpired() {
        Instant now = clock.get(); int n = 0;
        for (Auction a : auctions.values()) {
            if (!a.tryClose(now)) continue;
            n++;
            Bid top = a.state().highest();
            AuctionResult r;
            if (top == null || top.amountCents() < a.reservePriceCents) {
                r = new AuctionResult(Outcome.UNSOLD, null, 0, false);
            } else {
                boolean paid = payments.charge(top.bidderId(), top.amountCents(), a.id + ":win");
                r = new AuctionResult(Outcome.SOLD, top.bidderId(), top.amountCents(), paid);
            }
            a.result = r;
            for (AuctionObserver o : observers) safely(() -> o.onClosed(a, r));
        }
        return n;
    }

    private static Bid findOwn(Bid from, String bidderId, long amount) {
        for (Bid b = from; b != null; b = b.previous())
            if (b.bidderId().equals(bidderId) && b.amountCents() == amount) return b;
        return null;
    }

    private static void safely(Runnable r) {
        try { r.run(); } catch (RuntimeException e) { System.err.println("observer failed: " + e); }
    }
}

/** Example observer: per-user inbox of notifications. */
final class Inbox implements AuctionObserver {
    final Map<String, List<String>> messages = new ConcurrentHashMap<>();
    private void tell(String user, String msg) { messages.computeIfAbsent(user, k -> new CopyOnWriteArrayList<>()).add(msg); }
    public void onBid(Auction a, Bid bid, String outbid) { if (outbid != null) tell(outbid, "outbid on " + a.id + " at " + bid.amountCents()); }
    public void onExtended(Auction a, Instant end) { tell(a.sellerId, a.id + " extended to " + end); }
    public void onClosed(Auction a, AuctionResult r) {
        if (r.outcome() == Outcome.SOLD) { tell(r.winnerId(), "won " + a.id + " for " + r.priceCents()); tell(a.sellerId, a.id + " sold for " + r.priceCents()); }
        else tell(a.sellerId, a.id + " did not sell");
    }
}

final class FakeGateway implements PaymentGateway {
    final Map<String, Long> charges = new ConcurrentHashMap<>();
    public boolean charge(String user, long cents, String key) { charges.putIfAbsent(key, cents); return true; }
}

public class Main {
    static final Instant T0 = Instant.parse("2026-11-10T12:00:00Z");
    static Instant now = T0;

    static void check(boolean ok, String what) { if (!ok) throw new AssertionError(what); }
    static boolean rejected(Runnable r) { try { r.run(); return false; } catch (AuctionException e) { return true; } }

    public static void main(String[] args) throws Exception {
        FakeGateway g = new FakeGateway();
        AuctionService s = new AuctionService(() -> now, g);
        Inbox inbox = new Inbox(); s.subscribe(inbox);
        Auction a = s.create("sam", 1000, 1500, T0, T0.plus(Duration.ofHours(1)), new FixedIncrement(100), new FixedEnd());

        check(rejected(() -> s.placeBid(a.id, "sam", 5000)), "seller cannot bid");
        check(rejected(() -> s.placeBid(a.id, "ann", 900)), "below starting price");
        s.placeBid(a.id, "ann", 1000);
        check(rejected(() -> s.placeBid(a.id, "bob", 1050)), "below minimum increment");
        s.placeBid(a.id, "bob", 1100);
        s.placeBid(a.id, "ann", 1600);
        check(inbox.messages.get("ann").equals(List.of("outbid on " + a.id + " at 1100")), "ann told she was outbid");
        check(inbox.messages.get("bob").size() == 1, "bob told once");

        now = T0.plus(Duration.ofMinutes(59));
        check(s.closeExpired() == 0, "not yet");
        now = T0.plus(Duration.ofHours(1));
        check(rejected(() -> s.placeBid(a.id, "bob", 9999)), "bids at the end time are late");
        check(s.closeExpired() == 1 && s.closeExpired() == 0, "settled exactly once");
        check(a.result.equals(new AuctionResult(Outcome.SOLD, "ann", 1600, true)), "winner " + a.result);
        check(g.charges.get(a.id + ":win") == 1600, "winner charged");

        // reserve not met
        Auction cheap = s.create("sam", 1000, 5000, now, now.plus(Duration.ofMinutes(10)), new TieredIncrement(), new FixedEnd());
        s.placeBid(cheap.id, "ann", 1000);
        now = now.plus(Duration.ofMinutes(10)); s.closeExpired();
        check(cheap.result.outcome() == Outcome.UNSOLD && !g.charges.containsKey(cheap.id + ":win"), "reserve not met");

        // anti-sniping: a bid in the last 2 minutes pushes the end out to bid + 2 minutes
        Instant end = now.plus(Duration.ofMinutes(30));
        Auction snipe = s.create("sam", 1000, 0, now, end, new FixedIncrement(100), new AntiSniping(Duration.ofMinutes(2), Duration.ofMinutes(2)));
        now = end.minusSeconds(30);
        s.placeBid(snipe.id, "eve", 1000);
        check(snipe.state().endsAt().equals(end.plusSeconds(90)), "extended to bid + 2 min");
        now = end; s.closeExpired();
        check(snipe.state().phase() == Phase.RUNNING, "still open after the original end");
        now = end.plusSeconds(90); s.closeExpired();
        check(snipe.result.winnerId().equals("eve"), "closes at the extended time");

        noLostBids();
        bidRacingClose();
        System.out.println("online-auction: all checks passed");
    }

    /** 16 threads hammer one auction. Every accepted bid must survive in the history chain. */
    static void noLostBids() throws Exception {
        Auction a = new Auction("A", "sam", 100, 0, T0, T0.plus(Duration.ofDays(1)), new FixedIncrement(1), new FixedEnd());
        ExecutorService pool = Executors.newFixedThreadPool(16);
        CountDownLatch go = new CountDownLatch(1);
        AtomicInteger accepted = new AtomicInteger();
        List<Future<?>> fs = new ArrayList<>();
        for (int t = 0; t < 16; t++) {
            String bidder = "u" + t;
            fs.add(pool.submit(() -> {
                go.await();
                for (int i = 0; i < 2000; i++) {
                    long amount = a.minimumNextBid(a.state()) + ThreadLocalRandom.current().nextInt(3);
                    if (!rejected(() -> a.placeBid(bidder, amount, T0.plusSeconds(1)))) accepted.incrementAndGet();
                }
                return null;
            }));
        }
        go.countDown();
        for (Future<?> f : fs) f.get();
        pool.shutdown();
        int chain = 0;
        for (Bid b = a.state().highest(); b != null; b = b.previous()) {
            chain++;
            if (b.previous() != null) check(b.amountCents() >= b.previous().amountCents() + 1, "history strictly increasing");
        }
        check(chain == accepted.get(), "no lost updates: chain " + chain + " vs accepted " + accepted.get());
    }

    /** A bid stamped before the end races the closer. An accepted bid must be the one that wins. */
    static void bidRacingClose() throws Exception {
        ExecutorService pool = Executors.newFixedThreadPool(2);
        for (int i = 0; i < 1000; i++) {
            Instant end = T0.plusSeconds(60);
            Auction a = new Auction("A", "sam", 100, 0, T0, end, new FixedIncrement(10), new FixedEnd());
            a.placeBid("ann", 100, T0);
            CyclicBarrier b = new CyclicBarrier(2);
            Future<Boolean> bid = pool.submit(() -> { b.await(); return !rejected(() -> a.placeBid("bob", 200, end.minusMillis(1))); });
            Future<Boolean> close = pool.submit(() -> { b.await(); return a.tryClose(end); });
            boolean bidOk = bid.get(); boolean closed = close.get();
            check(closed && a.state().phase() == Phase.CLOSED, "closer always succeeds");
            check(a.state().highest().bidderId().equals(bidOk ? "bob" : "ann"), "accepted bid is never lost to the close");
        }
        pool.shutdown();
    }
}
from __future__ import annotations

import threading
from dataclasses import dataclass
from enum import Enum
from itertools import count
from typing import Callable, Protocol


class AuctionError(Exception):
    pass


@dataclass(frozen=True)
class Bid:
    """An accepted bid. `previous` is the bid it beat, so the leader chain is the bid history."""
    bidder_id: str
    amount_cents: int
    at: float
    previous: Bid | None


class Phase(Enum):
    RUNNING = 1; CLOSED = 2; CANCELLED = 3


class Outcome(Enum):
    SOLD = 1; UNSOLD = 2


@dataclass(frozen=True)
class AuctionResult:
    outcome: Outcome
    winner_id: str | None
    price_cents: int
    paid: bool


class IncrementPolicy(Protocol):
    def min_increment_cents(self, current: int) -> int: ...


class FixedIncrement:
    def __init__(self, cents: int) -> None:
        self._cents = cents

    def min_increment_cents(self, current: int) -> int:
        return self._cents


class TieredIncrement:
    def min_increment_cents(self, current: int) -> int:
        return 50 if current < 1000 else 100 if current < 10000 else 500


class EndTimePolicy(Protocol):
    def end_after_bid(self, current_end: float, bid_at: float) -> float: ...


class FixedEnd:
    def end_after_bid(self, current_end: float, bid_at: float) -> float:
        return current_end


class AntiSniping:
    """A bid in the last `window` seconds pushes the end to bid_at + `extension`."""

    def __init__(self, window: float, extension: float) -> None:
        self._window, self._extension = window, extension

    def end_after_bid(self, current_end: float, bid_at: float) -> float:
        if current_end - bid_at >= self._window:
            return current_end
        return max(current_end, bid_at + self._extension)


class Auction:
    def __init__(self, id: str, seller_id: str, starting_cents: int, reserve_cents: int,
                 starts_at: float, ends_at: float, increments: IncrementPolicy, end_policy: EndTimePolicy) -> None:
        if starts_at >= ends_at:
            raise AuctionError("must end after it starts")
        self.id, self.seller_id = id, seller_id
        self.starting_cents, self.reserve_cents, self.starts_at = starting_cents, reserve_cents, starts_at
        self._increments, self._end_policy = increments, end_policy
        self._lock = threading.Lock()          # Python has no CAS on objects, so: one lock per auction
        self.highest: Bid | None = None        # the three fields below are guarded by _lock
        self.ends_at = ends_at
        self.phase = Phase.RUNNING
        self.result: AuctionResult | None = None

    def minimum_next_bid(self) -> int:
        h = self.highest
        return self.starting_cents if h is None else h.amount_cents + self._increments.min_increment_cents(h.amount_cents)

    def place_bid(self, bidder_id: str, amount_cents: int, now: float) -> tuple[Bid | None, Bid, float]:
        """Returns (bid it beat, new bid, end time before this bid)."""
        if bidder_id == self.seller_id:
            raise AuctionError("sellers cannot bid on their own item")
        if now < self.starts_at:
            raise AuctionError("auction has not started")
        with self._lock:                       # validate and update in one critical section
            if self.phase is not Phase.RUNNING or now >= self.ends_at:
                raise AuctionError("auction is closed")
            minimum = self.minimum_next_bid()
            if amount_cents < minimum:
                raise AuctionError(f"bid must be at least {minimum}")
            beaten, old_end = self.highest, self.ends_at
            self.highest = Bid(bidder_id, amount_cents, now, beaten)
            self.ends_at = self._end_policy.end_after_bid(self.ends_at, now)
            return beaten, self.highest, old_end

    def try_close(self, now: float) -> bool:
        """Exactly one caller ever gets True, so settlement runs once."""
        with self._lock:
            if self.phase is not Phase.RUNNING or now < self.ends_at:
                return False
            self.phase = Phase.CLOSED
            return True

    def cancel(self) -> None:
        with self._lock:
            if self.phase is not Phase.RUNNING:
                raise AuctionError("auction already finished")
            if self.highest is not None:
                raise AuctionError("cannot cancel after the first bid")
            self.phase = Phase.CANCELLED


class AuctionObserver:
    def on_bid(self, a: Auction, bid: Bid, outbid_bidder_id: str | None) -> None: ...

    def on_extended(self, a: Auction, new_end: float) -> None: ...

    def on_closed(self, a: Auction, result: AuctionResult) -> None: ...


class PaymentGateway(Protocol):
    def charge(self, user_id: str, cents: int, idempotency_key: str) -> bool: ...


class AuctionService:
    def __init__(self, clock: Callable[[], float], payments: PaymentGateway) -> None:
        self._clock, self._payments = clock, payments
        self._auctions: dict[str, Auction] = {}
        self._observers: list[AuctionObserver] = []
        self._ids = count(1)

    def subscribe(self, o: AuctionObserver) -> None:
        self._observers.append(o)

    def get(self, auction_id: str) -> Auction:
        if auction_id not in self._auctions:
            raise AuctionError(f"unknown auction {auction_id}")
        return self._auctions[auction_id]

    def create(self, seller_id: str, starting_cents: int, reserve_cents: int, starts_at: float, ends_at: float,
               increments: IncrementPolicy, end_policy: EndTimePolicy) -> Auction:
        a = Auction(f"A{next(self._ids)}", seller_id, starting_cents, reserve_cents, starts_at, ends_at,
                    increments, end_policy)
        self._auctions[a.id] = a
        return a

    def place_bid(self, auction_id: str, bidder_id: str, amount_cents: int) -> Bid:
        a = self.get(auction_id)
        beaten, bid, old_end = a.place_bid(bidder_id, amount_cents, self._clock())
        # notify after the lock is released, so observers may bid again (proxy bidding does)
        outbid = beaten.bidder_id if beaten and beaten.bidder_id != bidder_id else None
        self._each(lambda o: o.on_bid(a, bid, outbid))
        if a.ends_at > old_end:
            self._each(lambda o: o.on_extended(a, a.ends_at))
        return bid

    def close_expired(self) -> int:
        """Run from a scheduler. Returns how many auctions this call settled."""
        now, n = self._clock(), 0
        for a in list(self._auctions.values()):
            if not a.try_close(now):
                continue
            n += 1
            top = a.highest
            if top is None or top.amount_cents < a.reserve_cents:
                result = AuctionResult(Outcome.UNSOLD, None, 0, False)
            else:
                paid = self._payments.charge(top.bidder_id, top.amount_cents, f"{a.id}:win")
                result = AuctionResult(Outcome.SOLD, top.bidder_id, top.amount_cents, paid)
            a.result = result
            self._each(lambda o: o.on_closed(a, result))
        return n

    def _each(self, fn: Callable[[AuctionObserver], None]) -> None:
        for o in list(self._observers):
            try:
                fn(o)
            except Exception as e:             # one broken observer must not break bidding
                print("observer failed:", e)


class Inbox(AuctionObserver):
    def __init__(self) -> None:
        self.messages: dict[str, list[str]] = {}
        self._lock = threading.Lock()

    def tell(self, user: str, msg: str) -> None:
        with self._lock:
            self.messages.setdefault(user, []).append(msg)

    def on_bid(self, a: Auction, bid: Bid, outbid: str | None) -> None:
        if outbid:
            self.tell(outbid, f"outbid on {a.id} at {bid.amount_cents}")

    def on_extended(self, a: Auction, new_end: float) -> None:
        self.tell(a.seller_id, f"{a.id} extended to {new_end}")

    def on_closed(self, a: Auction, r: AuctionResult) -> None:
        if r.outcome is Outcome.SOLD:
            assert r.winner_id is not None
            self.tell(r.winner_id, f"won {a.id} for {r.price_cents}")
            self.tell(a.seller_id, f"{a.id} sold for {r.price_cents}")
        else:
            self.tell(a.seller_id, f"{a.id} did not sell")


class FakeGateway:
    def __init__(self) -> None:
        self.charges: dict[str, int] = {}

    def charge(self, user_id: str, cents: int, idempotency_key: str) -> bool:
        self.charges.setdefault(idempotency_key, cents)
        return True


class FakeClock:
    def __init__(self) -> None:
        self.now = 0.0

    def __call__(self) -> float:
        return self.now


def rejected(fn: Callable[[], object]) -> bool:
    try:
        fn()
        return False
    except AuctionError:
        return True


def demo() -> None:
    clock, g = FakeClock(), FakeGateway()
    s = AuctionService(clock, g)
    inbox = Inbox()
    s.subscribe(inbox)
    a = s.create("sam", 1000, 1500, 0, 3600, FixedIncrement(100), FixedEnd())
    assert rejected(lambda: s.place_bid(a.id, "sam", 5000))
    assert rejected(lambda: s.place_bid(a.id, "ann", 900))
    s.place_bid(a.id, "ann", 1000)
    assert rejected(lambda: s.place_bid(a.id, "bob", 1050))
    s.place_bid(a.id, "bob", 1100)
    s.place_bid(a.id, "ann", 1600)
    assert inbox.messages["ann"] == [f"outbid on {a.id} at 1100"]

    clock.now = 3600
    assert rejected(lambda: s.place_bid(a.id, "bob", 9999))
    assert s.close_expired() == 1 and s.close_expired() == 0
    assert a.result == AuctionResult(Outcome.SOLD, "ann", 1600, True) and g.charges[f"{a.id}:win"] == 1600

    end = clock.now + 1800
    snipe = s.create("sam", 1000, 0, clock.now, end, FixedIncrement(100), AntiSniping(120, 120))
    clock.now = end - 30
    s.place_bid(snipe.id, "eve", 1000)
    assert snipe.ends_at == end + 90
    clock.now = end
    s.close_expired()
    assert snipe.phase is Phase.RUNNING
    clock.now = end + 90
    s.close_expired()
    assert snipe.result is not None and snipe.result.winner_id == "eve"
    print("online-auction: demo checks passed")


if __name__ == "__main__":
    demo()
// online-auction.ts — run with: npx tsx online-auction.ts
class AuctionError extends Error {}

/** An accepted bid. `previous` is the bid it beat, so the leader chain is the bid history. */
interface Bid { readonly bidderId: string; readonly amountCents: number; readonly at: number; readonly previous: Bid | null }

enum Phase { RUNNING = "RUNNING", CLOSED = "CLOSED", CANCELLED = "CANCELLED" }
enum Outcome { SOLD = "SOLD", UNSOLD = "UNSOLD" }
interface AuctionResult { outcome: Outcome; winnerId: string | null; priceCents: number; paid: boolean }

interface IncrementPolicy { minIncrementCents(currentCents: number): number }
class FixedIncrement implements IncrementPolicy {
  constructor(private cents: number) {}
  minIncrementCents(): number { return this.cents; }
}
class TieredIncrement implements IncrementPolicy {
  minIncrementCents(c: number): number { return c < 1000 ? 50 : c < 10000 ? 100 : 500; }
}

interface EndTimePolicy { endAfterBid(currentEnd: number, bidAt: number): number }
class FixedEnd implements EndTimePolicy {
  endAfterBid(currentEnd: number): number { return currentEnd; }
}
/** A bid in the last `windowMs` pushes the end to bidAt + `extensionMs`. */
class AntiSniping implements EndTimePolicy {
  constructor(private windowMs: number, private extensionMs: number) {}
  endAfterBid(currentEnd: number, bidAt: number): number {
    if (currentEnd - bidAt >= this.windowMs) return currentEnd;
    return Math.max(currentEnd, bidAt + this.extensionMs);
  }
}

class Auction {
  highest: Bid | null = null;
  phase = Phase.RUNNING;
  result: AuctionResult | null = null;
  constructor(readonly id: string, readonly sellerId: string, readonly startingCents: number,
              readonly reserveCents: number, readonly startsAt: number, public endsAt: number,
              private increments: IncrementPolicy, private endPolicy: EndTimePolicy) {
    if (startsAt >= endsAt) throw new AuctionError("must end after it starts");
  }

  minimumNextBid(): number {
    const h = this.highest;
    return h === null ? this.startingCents : h.amountCents + this.increments.minIncrementCents(h.amountCents);
  }

  /** Synchronous validate-and-update: on Node's event loop nothing can interleave. */
  placeBid(bidderId: string, amountCents: number, now: number): { beaten: Bid | null; bid: Bid; oldEnd: number } {
    if (bidderId === this.sellerId) throw new AuctionError("sellers cannot bid on their own item");
    if (now < this.startsAt) throw new AuctionError("auction has not started");
    if (this.phase !== Phase.RUNNING || now >= this.endsAt) throw new AuctionError("auction is closed");
    const min = this.minimumNextBid();
    if (amountCents < min) throw new AuctionError(`bid must be at least ${min}`);
    const beaten = this.highest, oldEnd = this.endsAt;
    this.highest = { bidderId, amountCents, at: now, previous: beaten };
    this.endsAt = this.endPolicy.endAfterBid(this.endsAt, now);
    return { beaten, bid: this.highest, oldEnd };
  }

  tryClose(now: number): boolean {
    if (this.phase !== Phase.RUNNING || now < this.endsAt) return false;
    this.phase = Phase.CLOSED;
    return true;
  }

  cancel(): void {
    if (this.phase !== Phase.RUNNING) throw new AuctionError("auction already finished");
    if (this.highest) throw new AuctionError("cannot cancel after the first bid");
    this.phase = Phase.CANCELLED;
  }
}

interface AuctionObserver {
  onBid?(a: Auction, bid: Bid, outbidBidderId: string | null): void;
  onExtended?(a: Auction, newEnd: number): void;
  onClosed?(a: Auction, r: AuctionResult): void;
}

interface PaymentGateway { charge(userId: string, cents: number, idempotencyKey: string): Promise<boolean> }

class AuctionService {
  private readonly auctions = new Map<string, Auction>();
  private readonly observers: AuctionObserver[] = [];
  private nextId = 1;
  constructor(private clock: () => number, private payments: PaymentGateway) {}

  subscribe(o: AuctionObserver): void { this.observers.push(o); }
  get(id: string): Auction {
    const a = this.auctions.get(id);
    if (!a) throw new AuctionError(`unknown auction ${id}`);
    return a;
  }

  create(sellerId: string, startingCents: number, reserveCents: number, startsAt: number, endsAt: number,
         inc: IncrementPolicy, end: EndTimePolicy): Auction {
    const a = new Auction(`A${this.nextId++}`, sellerId, startingCents, reserveCents, startsAt, endsAt, inc, end);
    this.auctions.set(a.id, a);
    return a;
  }

  placeBid(auctionId: string, bidderId: string, amountCents: number): Bid {
    const a = this.get(auctionId);
    const { beaten, bid, oldEnd } = a.placeBid(bidderId, amountCents, this.clock());
    const outbid = beaten && beaten.bidderId !== bidderId ? beaten.bidderId : null;
    this.each((o) => o.onBid?.(a, bid, outbid));
    if (a.endsAt > oldEnd) this.each((o) => o.onExtended?.(a, a.endsAt));
    return bid;
  }

  /** Call from setInterval. The phase flips synchronously before the first await, so a second sweep skips it. */
  async closeExpired(): Promise<number> {
    const now = this.clock();
    const closing = [...this.auctions.values()].filter((a) => a.tryClose(now));
    for (const a of closing) {
      const top = a.highest;
      let r: AuctionResult;
      if (!top || top.amountCents < a.reserveCents) {
        r = { outcome: Outcome.UNSOLD, winnerId: null, priceCents: 0, paid: false };
      } else {
        const paid = await this.payments.charge(top.bidderId, top.amountCents, `${a.id}:win`);
        r = { outcome: Outcome.SOLD, winnerId: top.bidderId, priceCents: top.amountCents, paid };
      }
      a.result = r;
      this.each((o) => o.onClosed?.(a, r));
    }
    return closing.length;
  }

  private each(fn: (o: AuctionObserver) => void): void {
    for (const o of [...this.observers]) {
      try { fn(o); } catch (e) { console.error("observer failed:", e); }
    }
  }
}

class Inbox implements AuctionObserver {
  readonly messages = new Map<string, string[]>();
  private tell(user: string, msg: string): void { this.messages.set(user, [...(this.messages.get(user) ?? []), msg]); }
  onBid(a: Auction, bid: Bid, outbid: string | null): void { if (outbid) this.tell(outbid, `outbid on ${a.id} at ${bid.amountCents}`); }
  onExtended(a: Auction, end: number): void { this.tell(a.sellerId, `${a.id} extended to ${end}`); }
  onClosed(a: Auction, r: AuctionResult): void {
    if (r.outcome === Outcome.SOLD) { this.tell(r.winnerId!, `won ${a.id} for ${r.priceCents}`); this.tell(a.sellerId, `${a.id} sold for ${r.priceCents}`); }
    else this.tell(a.sellerId, `${a.id} did not sell`);
  }
}

class FakeGateway implements PaymentGateway {
  readonly charges = new Map<string, number>();
  async charge(_user: string, cents: number, key: string): Promise<boolean> {
    await new Promise((r) => setTimeout(r, 1)); // a slow network call
    if (!this.charges.has(key)) this.charges.set(key, cents);
    return true;
  }
}

function assert(cond: unknown, msg: string): asserts cond { if (!cond) throw new Error("FAILED: " + msg); }
function rejected(fn: () => unknown): boolean { try { fn(); return false; } catch (e) { return e instanceof AuctionError; } }

let now = 0;
const MIN = 60_000;

async function main(): Promise<void> {
  const g = new FakeGateway();
  const s = new AuctionService(() => now, g);
  const inbox = new Inbox();
  s.subscribe(inbox);
  const a = s.create("sam", 1000, 1500, 0, 60 * MIN, new FixedIncrement(100), new FixedEnd());
  assert(rejected(() => s.placeBid(a.id, "sam", 5000)), "seller cannot bid");
  assert(rejected(() => s.placeBid(a.id, "ann", 900)), "below start");
  s.placeBid(a.id, "ann", 1000);
  assert(rejected(() => s.placeBid(a.id, "bob", 1050)), "below increment");
  s.placeBid(a.id, "bob", 1100);
  s.placeBid(a.id, "ann", 1600);
  assert(inbox.messages.get("ann")?.join() === `outbid on ${a.id} at 1100`, "outbid notice");

  now = 60 * MIN;
  assert(rejected(() => s.placeBid(a.id, "bob", 9999)), "late bid");
  const [first, second] = await Promise.all([s.closeExpired(), s.closeExpired()]); // two overlapping sweeps
  assert(first + second === 1, "settled exactly once");
  assert(a.result?.winnerId === "ann" && a.result.priceCents === 1600 && g.charges.get(`${a.id}:win`) === 1600, "winner");

  const end = now + 30 * MIN;
  const snipe = s.create("sam", 1000, 0, now, end, new FixedIncrement(100), new AntiSniping(2 * MIN, 2 * MIN));
  now = end - 30_000;
  s.placeBid(snipe.id, "eve", 1000);
  assert(snipe.endsAt === end + 90_000, "extended");
  now = end;
  await s.closeExpired();
  assert(snipe.phase === Phase.RUNNING, "still open");
  now = end + 90_000;
  await s.closeExpired();
  assert(snipe.result?.winnerId === "eve", "closed at the extended end");

  const t = new TieredIncrement();
  assert([999, 1000, 10000].map((c) => t.minIncrementCents(c)).join() === "50,100,500", "tiers");
  console.log("online-auction: all checks passed");
}

main();
export {}; // makes this file a module, so names do not clash with DOM globals

Run: javac -d out Main.java && java -ea -cp out Main, python online_auction.py, npx tsx online-auction.ts (strict-mode clean).

7. Concurrency

The shared state

Per auction there's one contended thing: (highest bid, end time, phase). Everything else is either immutable (seller, start price, policies) or written once by a single winner (result).

Option A: compare-and-set (Java)

placeBid reads a snapshot, validates against it, builds the next snapshot, and publishes it with compareAndSet(snapshot, next). If another bid published first, the CAS fails and the loop re-validates against the new state. That retry-with-revalidation is the whole point. A bid of 1250 that was valid against 1100 is correctly rejected once 1200 has landed with a 100 increment.

Properties worth stating:

  • Lock-free. A thread never waits for another thread that holds a lock. A failed CAS means somebody else made progress.
  • No lost updates. The noLostBids test has 16 threads each attempt 2000 bids. Then it walks the history chain and asserts that its length equals the number of placeBid calls that returned successfully, and that it's strictly increasing. Any lost update would break the count.
  • ABA isn't a problem. Every successful CAS installs a new AuctionState object, and compareAndSet compares references, so an old state can never come back.
  • Cost under heavy contention. In a bidding frenzy most CAS attempts fail and retry. Each retry is cheap (a few allocations) and bids are rejected quickly once they're below the new minimum, so this stays fast. If it ever didn't, the lock version wouldn't be faster: it serialises the same work.

Option B: a lock per auction (Python)

CPython has no compare-and-set on object references, so the Python version holds auction._lock across validate-and-update. It's simpler to read and equally correct. The lock is per auction, so bids on different auctions never contend. Say this in the interview: "One lock per auction, never a global lock. The critical section is a few comparisons and one allocation, and I/O never happens inside it." The Python tests run the same lost-update and close-race checks, with an 8-thread hammer and a microsecond switch interval.

Which one to pick? In Java, either. CAS shows depth, a lock is easier to extend. If the interviewer adds rules that read other mutable state (a per-bidder credit limit, say), a lock is usually the right call, because CAS only covers what fits in one reference.

Bid versus close

The closer uses the same atomic state. tryClose CASes RUNNING → CLOSED only when now ≥ endsAt. Now consider a bid stamped one millisecond before the end that races the closer:

  • If the bid's CAS lands first, the closer's CAS is based on the post-bid state, so the bid is included in the result.
  • If the close lands first, the bid's CAS fails, the retry sees CLOSED, and the bid is rejected.

There's no third outcome. The bidRacingClose test runs this 1000 times and checks that an accepted bid is always the winning bid. The same CAS gives exactly-once settlement. Only one tryClose ever returns true, so even overlapping sweepers (the Python and TS tests run several) charge the winner once. The idempotency key A1:win is the belt to that pair of braces, for retries after a crash.

A subtle point: the bid's now is read before the CAS loop. A bid that arrives at 11:59:59.999 and wins its CAS a microsecond after noon is still accepted, because it was valid when it arrived. That's the right semantics, and it's the reason the end-time check uses the bid's timestamp, not a fresh clock read inside the loop.

Anti-sniping inside the same CAS

The extended end time is part of AuctionState, so a bid and its extension publish atomically. If the extension were a separate field, a closer could read "end = noon" between a late bid and its extension, close the auction, and leave the accepted bid's extension pointing at a closed auction.

Observers run outside the critical section

Notifications are sent after the CAS (or, in Python, after releasing the lock). That matters for two reasons. A slow email provider must not slow down bidding. And proxy bidding (below) places a new bid from inside a notification, which would deadlock on a non-reentrant lock if we notified while holding it. The cost is that observers can receive notifications for one auction slightly out of order under heavy contention. Each Bid carries its amount and time, so consumers can order them.

TypeScript

Auction.placeBid is synchronous, so it's atomic on the event loop. closeExpired is async because payment is. The phase flips to CLOSED synchronously inside tryClose, before the first await, so the TS test's two overlapping sweeps settle exactly once. That ordering is the TS equivalent of "the CAS happens before the I/O".

8. The interviewer adds...

"Proxy bidding: I tell you my maximum and you bid for me"

A proxy is an observer that responds to being outbid by placing the minimum bid needed, up to its secret maximum. It uses only the public API:

class ProxyBidder(AuctionObserver):
    """Bids the minimum needed to stay on top, up to a private maximum. Built only on the public API."""

    def __init__(self, service: AuctionService, auction_id: str, bidder_id: str, max_cents: int) -> None:
        self._service, self._auction_id = service, auction_id
        self.bidder_id, self.max_cents = bidder_id, max_cents
        service.subscribe(self)
        self._respond()

    def on_bid(self, a: Auction, bid: Bid, outbid: str | None) -> None:
        if a.id == self._auction_id and bid.bidder_id != self.bidder_id:
            self._respond()

    def _respond(self) -> None:
        a = self._service.get(self._auction_id)
        need = a.minimum_next_bid()
        if need <= self.max_cents and (a.highest is None or a.highest.bidder_id != self.bidder_id):
            try:
                self._service.place_bid(self._auction_id, self.bidder_id, need)
            except AuctionError:
                pass                           # someone outbid us in between, or it closed: on_bid will call again

Tested: a proxy with a 2000 max opens at 1000, answers a manual 1200 with 1250, and gives up when a manual 1990 makes the next minimum 2040. Two proxies (2000 and 1500 max) bid against each other until the 1500 proxy runs out, leaving the 2000 proxy leading at 1500.

Two caveats are worth raising. Two proxies fighting produce one bid per step through the notification chain. eBay-style systems collapse this in one step: the higher maximum wins at the lower maximum plus one increment, capped at the higher maximum. That's a pure function you'd put in the service, still validated by the same CAS. Also, the recursion depth is bounded by (max − current) / increment. A production system queues proxy responses instead of recursing.

"The winner didn't pay"

The history chain makes the runner-up a walk back through previous, skipping everyone who has already failed to pay:

/** The winner didn't pay: offer the item to the best remaining bidder at their own highest bid. */
final class SecondChance {
    private final Auction auction; private final PaymentGateway payments;
    private final Set<String> failed = new HashSet<>();          // everyone who already didn't pay
    SecondChance(Auction auction, PaymentGateway payments) { this.auction = auction; this.payments = payments; }

    Optional<Bid> runnerUp() {
        for (Bid b = auction.state().highest(); b != null; b = b.previous())   // history chain, newest first
            if (!failed.contains(b.bidderId()) && b.amountCents() >= auction.reservePriceCents) return Optional.of(b);
        return Optional.empty();
    }

    synchronized AuctionResult settle() {
        AuctionResult r = auction.result;
        if (r == null || r.outcome() != Outcome.SOLD || r.paid()) return r;
        failed.add(r.winnerId());
        Optional<Bid> next = runnerUp();
        if (next.isEmpty()) return auction.result = new AuctionResult(Outcome.UNSOLD, null, 0, false);
        Bid b = next.get();
        boolean paid = payments.charge(b.bidderId(), b.amountCents(), auction.id + ":offer:" + b.bidderId());
        return auction.result = new AuctionResult(Outcome.SOLD, b.bidderId(), b.amountCents(), paid);
    }
}
// In closeExpired, after a failed charge: r = new SecondChance(a, payments).settle(), retried until paid or UNSOLD.

Tested: with bids ann 1000, bob 1300, ann 1400, cat 1500, a failed charge for cat offers the item to ann at 1400. If ann also fails, it goes to bob at 1300. Each offer has its own idempotency key. Note that the runner-up pays their own bid, not the winner's.

"Watchers get an 'ending soon' reminder"

A sweep with a "sent" set, reading the auction's current end time so anti-sniping extensions are respected. No core changes:

/** "Ending soon" reminders for watchers, sent once per auction. A sweep plus a set: no core changes. */
class EndingSoonReminder {
  private readonly watchers = new Map<string, Set<string>>(); // auctionId -> userIds
  private readonly sent = new Set<string>();                  // auctionId:userId
  constructor(private service: AuctionService, private leadMs: number,
              private send: (userId: string, msg: string) => void) {}

  watch(auctionId: string, userId: string): void {
    this.service.get(auctionId); // fail fast on unknown ids
    this.watchers.set(auctionId, (this.watchers.get(auctionId) ?? new Set()).add(userId));
  }

  sweep(now: number): void {
    for (const [auctionId, users] of this.watchers) {
      const a = this.service.get(auctionId);
      if (a.phase !== Phase.RUNNING || a.endsAt - now > this.leadMs) continue; // reads the *current* end
      for (const u of users) {
        const key = `${auctionId}:${u}`;
        if (!this.sent.has(key)) { this.sent.add(key); this.send(u, `${auctionId} ends soon at ${a.minimumNextBid()}`); }
      }
    }
  }
}

Tested: nothing at 49 minutes, one reminder each for two watchers at 50 minutes, and no duplicates on the next sweep.

9. Tests

import random
import sys
import threading
from concurrent.futures import ThreadPoolExecutor

from online_auction import (Auction, AuctionService, FakeClock, FakeGateway, FixedEnd, FixedIncrement,
                            Outcome, Phase, TieredIncrement, rejected)

sys.setswitchinterval(1e-6)


def test_tiered_increments():
    inc = TieredIncrement()
    assert [inc.min_increment_cents(c) for c in (999, 1000, 9999, 10000)] == [50, 100, 100, 500]


def test_cancel_only_before_first_bid():
    a = Auction("A", "sam", 100, 0, 0, 60, FixedIncrement(10), FixedEnd())
    a.place_bid("ann", 100, 1)
    assert rejected(a.cancel)
    b = Auction("B", "sam", 100, 0, 0, 60, FixedIncrement(10), FixedEnd())
    b.cancel()
    assert b.phase is Phase.CANCELLED and rejected(lambda: b.place_bid("ann", 100, 1))


def test_unsold_when_reserve_not_met():
    clock, g = FakeClock(), FakeGateway()
    s = AuctionService(clock, g)
    a = s.create("sam", 100, 5000, 0, 60, FixedIncrement(10), FixedEnd())
    s.place_bid(a.id, "ann", 4000)
    clock.now = 60
    s.close_expired()
    assert a.result.outcome is Outcome.UNSOLD and not g.charges


def test_no_lost_bids_under_contention():
    a = Auction("A", "sam", 100, 0, 0, 10**9, FixedIncrement(1), FixedEnd())
    accepted = []
    barrier = threading.Barrier(8)

    def hammer(bidder: str) -> None:
        barrier.wait()
        for _ in range(2000):
            amount = a.minimum_next_bid() + random.randint(0, 2)
            if not rejected(lambda: a.place_bid(bidder, amount, 1)):
                accepted.append(amount)

    with ThreadPoolExecutor(8) as pool:
        list(pool.map(hammer, [f"u{i}" for i in range(8)]))
    chain, b = [], a.highest
    while b:
        chain.append(b.amount_cents)
        b = b.previous
    assert len(chain) == len(accepted), "an accepted bid vanished"
    assert chain == sorted(chain, reverse=True) and len(set(chain)) == len(chain)
    assert chain[0] == max(accepted)


def test_bid_racing_close():
    for _ in range(500):
        a = Auction("A", "sam", 100, 0, 0, 60, FixedIncrement(10), FixedEnd())
        a.place_bid("ann", 100, 0)
        barrier = threading.Barrier(2)
        out = {}

        def bid():
            barrier.wait()
            out["bid"] = not rejected(lambda: a.place_bid("bob", 200, 59.999))

        def close():
            barrier.wait()
            out["closed"] = a.try_close(60)

        ts = [threading.Thread(target=bid), threading.Thread(target=close)]
        for t in ts: t.start()
        for t in ts: t.join()
        assert out["closed"] and a.phase is Phase.CLOSED
        assert a.highest.bidder_id == ("bob" if out["bid"] else "ann")


def test_concurrent_closers_settle_once():
    clock, g = FakeClock(), FakeGateway()
    s = AuctionService(clock, g)
    a = s.create("sam", 100, 0, 0, 60, FixedIncrement(10), FixedEnd())
    s.place_bid(a.id, "ann", 100)
    clock.now = 60
    with ThreadPoolExecutor(8) as pool:
        assert sum(pool.map(lambda _: s.close_expired(), range(8))) == 1


if __name__ == "__main__":
    for name, fn in list(globals().items()):
        if name.startswith("test_"):
            fn()
            print("ok", name)

The concurrency tests check invariants, not interleavings. "Accepted count equals history length" catches lost updates however they happen. "An accepted bid racing the close is always the winner" catches every ordering of the close race. "Eight concurrent closers settle once" catches double charging. Pure-policy tests (tiers, anti-sniping arithmetic) are separate, cheap, and need no threads.

10. Common mistakes

  1. Read, check, write without atomicity. if (amount > highest) highest = amount in two steps is the bug the whole problem is built around.
  2. Several separate atomics (AtomicLong highest, AtomicReference endsAt). Each one is atomic, but together they aren't. Validation needs a consistent view of both.
  3. CAS without re-validating on retry. Retrying the same write after a failed CAS skips the increment check against the new leader.
  4. Closing with a plain phase = CLOSED write. A bid validated just before can still land after it, which gives a bid accepted after close.
  5. Settling in the scheduler without an exactly-once guard. Two scheduler instances charge the winner twice.
  6. Notifying under the lock. It slows bidding to the speed of the email provider, and it deadlocks the moment an observer bids.
  7. Floating-point money. Increments of 0.10 drift. Use cents.
  8. A global lock. It's correct, but it serialises every auction on the site behind the hottest one.

11. Interview follow-ups

How would you scale this to millions of auctions? Shard by auction id. Each auction's state lives on exactly one node, which keeps the in-process CAS or lock. Bids route by id. The bid history goes to an append-only log for durability. The class design is unchanged, because each shard runs the code above.

How would the database version look? UPDATE auctions SET highest = :amount, highest_bidder = :b, ends_at = :end, version = version + 1 WHERE id = :id AND version = :v AND phase = 'RUNNING'. If zero rows changed, re-read and re-validate. It's the same optimistic loop with a version column instead of a reference.

How is a sealed-bid (Vickrey) auction different? Bids are hidden, so there's no increment rule and no outbid notifications. Each bidder gets one bid. At close, the highest bidder wins and pays the second-highest bid. You'd model it as a different BidRule (one bid per bidder, any amount ≥ start) and a different settlement strategy. The close-once CAS is unchanged.

What if two bids tie? With a positive increment they can't both be accepted: whichever CAS lands first sets the leader, and the other re-validates and fails the new minimum. Earliest bid wins, which is what most rules say. Watch out for an increment policy that returns 0. The check is amount >= highest + increment, so a zero step would accept an equal bid and hand the lead to the later bidder. Policies should return at least one cent.

How do you stop shill bidding? Block seller-linked accounts from bidding (a validation strategy that checks an account graph), rate-limit bid retractions, and flag bidders who repeatedly bid on one seller's items and never win. These are validation rules plus offline analysis, not changes to the concurrency core.

Should anti-sniping extend from the bid time or from the old end? From the bid time (bidAt + extension), never earlier than the current end. Adding the extension to the old end stacks up: ten bids in the last minute push the close out by twenty minutes. Measuring from the bid time gives everyone exactly extension to respond to the latest bid, and no more.