Amazon: Clearing Price of Each Sponsored Products Auction

Hard
591.

Amazon: Clearing Price of Each Sponsored Products Auction

Sponsored ads are sold in auctions. This exercise uses a textbook generalised second-price rule. A bid is eligible when bid >= reserve_price. Each eligible bid's ad rank is bid × quality_score. The winner has the highest ad rank; a tie goes to the lower advertiser_id.

The winner pays just enough to keep its position: if there is a runner-up (the best ad rank among the other eligible bids), the price is FLOOR(runner_up_rank / winner_quality_score) + 1, but never more than the winner's own bid and never less than the reserve price. A winner with no other eligible bid pays the reserve price. Return auction_id, advertiser_id (the winner) and price_paid for every auction with at least one eligible bid, in any order.

A practice scenario set at Amazon: the tables and data are invented, and this is not a question from, or endorsed by, Amazon.

Tables

Table: Auction

ColumnType
auction_idint
keywordvarchar
reserve_priceint

Primary key: auction_id.

One row per ad slot auction; prices are in paise per click.

Table: AdBid

ColumnType
auction_idint
advertiser_idint
bidint
quality_scoreint

Primary key (together): auction_id, advertiser_id.

One bid per advertiser per auction; quality_score runs from 1 to 10.

Example

The rows may come back in any order; the columns must be the ones shown, in that order.

Auction

auction_idkeywordreserve_price
1wireless earbuds500
2running shoes800
3steel bottle300
4yoga mat1000

AdBid

auction_idadvertiser_idbidquality_score
11112006
11215004
11345010
2119005
21410005
21510005
3127003
3162809
4139008

Output

auction_idadvertiser_idprice_paid
1111001
2141000
312300
Read the hints, the editorial and the reference solution
-- Write your MySQL query below

Sign in to write, run and submit queries

A free account — no card, no trial clock. You come straight back here.

Run your query to see its result next to the expected one, example by example.

Amazon: Clearing Price of Each Sponsored Products Auction

Sponsored ads are sold in auctions. This exercise uses a textbook generalised second-price rule. A bid is eligible when bid >= reserve_price.

  • Difficulty: Hard
  • Topics: Window Functions, Joins, Conditional Logic
  • Dialect: MySQL
  • Problem: #591

Problem statement

Sponsored ads are sold in auctions. This exercise uses a textbook generalised second-price rule. A bid is eligible when bid >= reserve_price. Each eligible bid's ad rank is bid × quality_score. The winner has the highest ad rank; a tie goes to the lower advertiser_id.

The winner pays just enough to keep its position: if there is a runner-up (the best ad rank among the other eligible bids), the price is FLOOR(runner_up_rank / winner_quality_score) + 1, but never more than the winner's own bid and never less than the reserve price. A winner with no other eligible bid pays the reserve price. Return auction_id, advertiser_id (the winner) and price_paid for every auction with at least one eligible bid, in any order.

A practice scenario set at Amazon: the tables and data are invented, and this is not a question from, or endorsed by, Amazon.

Tables

Table: Auction

ColumnType
auction_idint
keywordvarchar
reserve_priceint

Primary key: auction_id.

One row per ad slot auction; prices are in paise per click.

Table: AdBid

ColumnType
auction_idint
advertiser_idint
bidint
quality_scoreint

Primary key: auction_id, advertiser_id.

One bid per advertiser per auction; quality_score runs from 1 to 10.

Examples

Example 1

Auction

auction_idkeywordreserve_price
1wireless earbuds500
2running shoes800
3steel bottle300
4yoga mat1000

AdBid

auction_idadvertiser_idbidquality_score
11112006
11215004
11345010
2119005
21410005
21510005
3127003
3162809
4139008

Output

auction_idadvertiser_idprice_paid
1111001
2141000
312300

How to solve Amazon: Clearing Price of Each Sponsored Products Auction

Three things are needed per auction: the eligible bids, the winner and the runner-up. A CTE joins each bid to its auction, drops bids under the reserve (an ineligible bid must not become the runner-up and inflate the price) and numbers the rest with ROW_NUMBER() ordered by ad rank descending and then advertiser_id. That tie-break makes position 1 the winner the rules name, and position 2 the runner-up — even when the two have equal ad rank.

Self-joining the CTE — position 1 as w, position 2 as r with a LEFT JOIN — puts the winner and the runner-up on one row, and an auction with a single eligible bid keeps a NULL runner-up, which the CASE maps to the reserve price. Otherwise the price is the smallest bid that would still beat the runner-up, runner_rank DIV winner_quality + 1, then clamped: GREATEST with the reserve and LEAST with the winner's bid. When the runner-up's rank equals the winner's, the formula exceeds the bid by one and the clamp brings it back to the bid.

The alternative finds the winner with NOT EXISTS (no eligible bid beats it under the same two-level rule) and the runner-up's rank with a correlated MAX over the other eligible bids; a NULL MAX makes the whole clamped expression NULL (both GREATEST and LEAST return NULL when an argument is NULL), and COALESCE turns it into the reserve price. Both read each auction's bids a constant number of times.

Reference solution (MySQL)

WITH eligible AS (
  SELECT b.auction_id, b.advertiser_id, b.bid, b.quality_score, a.reserve_price,
         b.bid * b.quality_score AS ad_rank,
         ROW_NUMBER() OVER (PARTITION BY b.auction_id
                            ORDER BY b.bid * b.quality_score DESC, b.advertiser_id) AS pos
  FROM AdBid b
  JOIN Auction a ON a.auction_id = b.auction_id
  WHERE b.bid >= a.reserve_price
)
SELECT w.auction_id, w.advertiser_id,
       CASE WHEN r.ad_rank IS NULL THEN w.reserve_price
            ELSE LEAST(w.bid, GREATEST(w.reserve_price, r.ad_rank DIV w.quality_score + 1)) END AS price_paid
FROM eligible w
LEFT JOIN eligible r ON r.auction_id = w.auction_id AND r.pos = 2
WHERE w.pos = 1

Another way

SELECT w.auction_id, w.advertiser_id,
       COALESCE(LEAST(w.bid, GREATEST(a.reserve_price, FLOOR((
         SELECT MAX(o.bid * o.quality_score) FROM AdBid o
         WHERE o.auction_id = w.auction_id AND o.advertiser_id <> w.advertiser_id AND o.bid >= a.reserve_price
       ) / w.quality_score) + 1)), a.reserve_price) AS price_paid
FROM AdBid w JOIN Auction a ON a.auction_id = w.auction_id
WHERE w.bid >= a.reserve_price
  AND NOT EXISTS (
    SELECT 1 FROM AdBid o WHERE o.auction_id = w.auction_id AND o.bid >= a.reserve_price
      AND (o.bid * o.quality_score > w.bid * w.quality_score
           OR (o.bid * o.quality_score = w.bid * w.quality_score AND o.advertiser_id < w.advertiser_id)))

← Amazon: Straight-Line Distance Driven on Each Delivery Route · Amazon: First Day Each Seller Breached the 60-Day Order Defect Rate →