Watch 6 video solutions for Design Auction System, a medium level problem involving Hash Table, Design, Heap (Priority Queue). This walkthrough by CodeWithMeGuys has 414 views views. Want to try solving it yourself? Practice on FleetCode or read the detailed text solution.
You are asked to design an auction system that manages bids from multiple users in real time.
Each bid is associated with a userId, an itemId, and a bidAmount.
Implement the AuctionSystem class:​​​​​​​
AuctionSystem(): Initializes the AuctionSystem object.void addBid(int userId, int itemId, int bidAmount): Adds a new bid for itemId by userId with bidAmount. If the same userId already has a bid on itemId, replace it with the new bidAmount.void updateBid(int userId, int itemId, int newAmount): Updates the existing bid of userId for itemId to newAmount. It is guaranteed that this bid exists.void removeBid(int userId, int itemId): Removes the bid of userId for itemId. It is guaranteed that this bid exists.int getHighestBidder(int itemId): Returns the userId of the highest bidder for itemId. If multiple users have the same highest bidAmount, return the user with the highest userId. If no bids exist for the item, return -1.
Example 1:
Input:
["AuctionSystem", "addBid", "addBid", "getHighestBidder", "updateBid", "getHighestBidder", "removeBid", "getHighestBidder", "getHighestBidder"]
[[], [1, 7, 5], [2, 7, 6], [7], [1, 7, 8], [7], [2, 7], [7], [3]]
Output:
[null, null, null, 2, null, 1, null, 1, -1]
Explanation
AuctionSystem auctionSystem = new AuctionSystem(); // Initialize the Auction system
Constraints:
1 <= userId, itemId <= 5 * 1041 <= bidAmount, newAmount <= 1095 * 104 total calls to addBid, updateBid, removeBid, and getHighestBidder.updateBid and removeBid, the bid from the given userId for the given itemId will be valid.Problem Overview: Design a system that manages auction bids efficiently. You need to support operations such as placing a bid, updating or removing a bid, and retrieving the highest bidder. The system must keep bids ordered by value while allowing fast updates when the same bidder changes their bid.
Approach 1: Brute Force List Scan (O(n) time per query, O(n) space)
The simplest design stores all bids in a list or array. Each new bid is appended or updated by scanning the list for the bidder. When the highest bid is required, iterate through all stored bids and track the maximum value. This approach is straightforward but inefficient because every lookup or ranking operation requires a full scan. Time complexity becomes O(n) per query with O(n) space, which does not scale when the number of bidders grows.
Approach 2: Hash Table + Heap (Priority Queue) (O(log n) updates, O(n) space)
A more practical solution uses a hash table to store the latest bid for each bidder and a heap (priority queue) to track the highest bid. The heap stores pairs like (bidAmount, bidderId). When a bidder updates their bid, push the new value to the heap and update the hash map. While retrieving the top bid, discard stale entries whose value no longer matches the hash table. This keeps insertion and update operations at O(log n), while lookups remain efficient.
Approach 3: Hash Table + Ordered Set (O(log n) per operation)
The cleanest design uses a hash table combined with an ordered set (such as TreeSet in Java or balanced BST structures). The hash table maps bidderId → bidAmount so updates can be located instantly. The ordered set stores pairs sorted by bid amount (and optionally bidder id for tie-breaking). When a bidder updates their bid, remove the old pair from the ordered set and insert the new one. Retrieving the highest bidder becomes a constant-time lookup of the last element in the ordered structure. Each modification costs O(log n) time and the total space remains O(n).
Recommended for interviews: The Hash Table + Ordered Set design is typically expected. The brute-force version shows you understand the requirements, but interviewers want to see how you maintain ordering while supporting fast updates. Combining direct lookup from a hash table with ordered retrieval from a balanced tree demonstrates solid system design and data structure selection.
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Brute Force List Scan | O(n) per query | O(n) | Small datasets or quick prototype implementation |
| Hash Table + Heap (Priority Queue) | O(log n) updates, amortized O(log n) retrieval | O(n) | When frequent highest-bid queries are needed with simple priority tracking |
| Hash Table + Ordered Set | O(log n) per operation | O(n) | Best general solution when bids must stay fully ordered with efficient updates |