Lowest-Bid Auction Service with Bounded Prices and Auction Removal

Design and implement a small auction service in which the lowest bid wins and which must report the current lowest bid quickly. It was described as a very simple object-oriented design question, and the reported implementation used a heap. Two interfaces had to be implemented, one for placing a bid and one for the bidding itself; their exact signatures were not reported. A natural reading is one call that records a bid on an auction and one that returns the auction's current lowest bid. Two follow-ups were asked: bid prices that fall within a known range, and removing auctions. The interface below is an assumption that makes the parts concrete. ```text place_bid("a1", "u7", 120) place_bid("a1", "u3", 95) place_bid("a1", "u5", 95) lowest_bid("a1") -> 95 by u3 (if the earlier of two equal bids wins) ``` ### Clarifying Questions - Is the lowest bid tracked per auction, across all auctions, or both? - When two bids have the same amount, which one wins? - Can a bidder bid again on the same auction, and does the new bid replace the old one or stand alongside it? - Are amounts whole numbers (for example, cents), and can a bid be withdrawn? ### Part 1 — Bids and the lowest bid Implement the service: record bids on auctions, and return an auction's current lowest bid. ```hint Which call is hot Compare how often each operation runs and what each one needs: the query only ever needs the smallest entry, never a fully sorted list. ``` #### What This Part Should Cover - Classes and their responsibilities, the interface signatures, and input validation - A data structure that returns the minimum quickly while bids keep arriving, with the cost of each operation - A deterministic tie rule, and the result for an auction with no bids ### Part 2 — Bounded bid prices Bid amounts are now known to fall within a fixed range. How do you use that to improve the complexity? ```hint What a small range allows Think about what a known, bounded range of integer prices lets you do that comparisons alone cannot. ``` #### What This Part Should Cover - A structure that exploits the bounded range, and the new cost of placing a bid and of the query - How the minimum and the tie rule are maintained as bids arrive and leave - The memory cost relative to the size of the range, and when the heap is still the better choice ### Part 3 — Removing auctions The service must also support removing an auction. Add the operation and keep the other operations correct and fast. ```hint When must removal happen Removing an arbitrary entry from a heap is expensive. Ask whether a removed auction's entries must disappear immediately, or only before they could be returned. ``` #### What This Part Should Cover - What happens to bids and queries that refer to a removed auction - How removal is implemented, its cost, and the memory held by entries that are no longer valid - Correctness of every lowest-bid query after removals ### What a Strong Answer Covers - Settles the scope of the query, the tie rule and the rebid policy before coding - Clean classes with a narrow interface and validated input - The correct cost of every operation in each variant, with a comparison of the heap, price buckets and deferred deletion - Tests for ties, empty auctions, removed auctions and boundary prices ### Follow-up Questions - A bidder can withdraw a single bid. How does your design handle that, and what does it cost? - Return the lowest `k` bids of an auction instead of only the lowest one. - Many requests place bids concurrently. How do you keep the lowest-bid query correct? - The price range is large but only a few prices are used. What do you use instead of one bucket per price?