Design auction system

Hash Table Design Heap (Priority Queue) Ordered Set

42.0% acceptance

Mar 15, 2026

Design an auction system that manages bids from multiple users in real time. AuctionSystem(): Initializes the AuctionSystem object. void addBid(int userId, int itemId, int bidAmount): Adds a new bid. If same userId already has a bid on itemId, replace it. void updateBid(int userId, int itemId, int newAmount): Updates existing bid. Guaranteed to exist. void removeBid(int userId, int itemId): Removes the bid. Guaranteed to exist. int getHighestBidder(int itemId): Returns userId of highest bidder. Ties broken by highest userId. -1 if no bids.

Solution

Rust

Time O(2^n)

Space O(n)

LeetCode

solution.rs

use std::collections::{HashMap, BTreeSet};

struct AuctionSystem {
  // itemId -> set of (bidAmount, userId) for quick max lookup
  item_bids: HashMap<i32, BTreeSet<(i32, i32)>>,
  // (userId, itemId) -> bidAmount
  user_bids: HashMap<(i32, i32), i32>,
}

impl AuctionSystem {

  fn new() -> Self {
    AuctionSystem {
      item_bids: HashMap::new(),
      user_bids: HashMap::new(),
    }
  }

  fn add_bid(&mut self, user_id: i32, item_id: i32, bid_amount: i32) {
    // If user already has a bid on this item, remove it first
    if let Some(&old_amount) = self.user_bids.get(&(user_id, item_id)) {
      self.item_bids.get_mut(&item_id).unwrap().remove(&(old_amount, user_id));
    }
    self.user_bids.insert((user_id, item_id), bid_amount);
    self.item_bids.entry(item_id).or_insert_with(BTreeSet::new).insert((bid_amount, user_id));
  }

  fn update_bid(&mut self, user_id: i32, item_id: i32, new_amount: i32) {
    let old_amount = self.user_bids[&(user_id, item_id)];
    self.item_bids.get_mut(&item_id).unwrap().remove(&(old_amount, user_id));
    self.user_bids.insert((user_id, item_id), new_amount);
    self.item_bids.get_mut(&item_id).unwrap().insert((new_amount, user_id));
  }

  fn remove_bid(&mut self, user_id: i32, item_id: i32) {
    let old_amount = self.user_bids.remove(&(user_id, item_id)).unwrap();
    self.item_bids.get_mut(&item_id).unwrap().remove(&(old_amount, user_id));
  }

  fn get_highest_bidder(&self, item_id: i32) -> i32 {
    match self.item_bids.get(&item_id) {
      Some(set) if !set.is_empty() => {
        let &(_, user_id) = set.iter().next_back().unwrap();
        user_id
      }
      _ => -1,
    }
  }
}