Skip to content

Google Shopping Price Retrieval

Level: L3-L5 Topics: Binary Search, Sorted Containers, System Design

Problem Statement

You are building a price lookup system for an online shopping platform. Products have multiple offers from different sellers, each with a price.

Implement a data structure that supports the following operations:

void AddOffer(int offer_id, int product_id, double price)
    // Add a new offer for the given product.

void RemoveOffer(int offer_id)
    // Remove an existing offer by its ID.

Offer QueryClosestOffer(int product_id, double target_price)
    // Return the offer for the given product whose price is closest
    // to the target price. If two offers are equally close, return
    // the one with the lower price.

Background & Constraints

  • Each offer_id is globally unique.
  • A product can have many offers (potentially thousands).
  • Multiple offers for the same product can have the same price.
  • QueryClosestOffer must be efficient — it will be called frequently.
  • The system starts empty and offers are added/removed dynamically.

Examples

AddOffer(1, 100, 25.00)    // Product 100: offer 1 at $25
AddOffer(2, 100, 30.00)    // Product 100: offer 2 at $30
AddOffer(3, 100, 22.00)    // Product 100: offer 3 at $22
AddOffer(4, 200, 50.00)    // Product 200: offer 4 at $50

QueryClosestOffer(100, 27.00)
→ Offer 1 (price $25, distance 2) — offer 2 is $30 (distance 3), so $25 wins

QueryClosestOffer(100, 27.50)
→ Offer 1 (price $25, distance 2.5) — offer 2 is $30 (distance 2.5), tie broken by lower price

RemoveOffer(1)

QueryClosestOffer(100, 27.00)
→ Offer 2 (price $30, distance 3) — now closest remaining offer

Hints & Common Pitfalls

  • Data structure choice: For each product, maintain offers in a sorted structure (by price). A balanced BST, sorted list, or skip list allows O(log M) closest-price queries where M is the number of offers for that product.

  • Finding closest price: In a sorted set, use floor and ceiling operations to find the two candidates closest to the target price, then compare distances.

  • Offer removal: You need to look up an offer by offer_id (to find which product it belongs to and its price), then remove it from the product's sorted structure. Maintain a hash map from offer_id to (product_id, price) for O(1) lookup.

  • Handling duplicate prices: Multiple offers can have the same price. Your sorted structure must support duplicates. A TreeMap<Double, List<Offer>> or a SortedList of (price, offer_id) pairs works.

  • Common mistake: Using a hash map alone without sorted access — this makes QueryClosestOffer O(M) instead of O(log M).

Follow-Up Questions

  1. UpdatePrice: Add an operation UpdatePrice(int offer_id, double new_price). How do you implement this efficiently? Is it just remove + re-add, or can you do better?

  2. Thread safety: If AddOffer, RemoveOffer, and QueryClosestOffer are called concurrently from multiple threads, what synchronization is needed? How do you minimize contention? Consider per-product locks vs. global locks vs. lock-free approaches.

  3. Distributed system: Scale this to hundreds of billions of offers across thousands of products. The data does not fit on a single machine. How do you partition the data? How do you handle QueryClosestOffer when the product's offers may be spread across multiple shards? Consider partitioning by product_id for locality.

  4. Range queries: Add support for QueryOffersInRange(product_id, min_price, max_price) that returns all offers within a price range. How does this affect your data structure choice?

  5. Analytics: How would you efficiently answer "What is the median offer price for product X?" or "What are the P10 and P90 prices?" without scanning all offers?