Google Coding Interview Question: Closest Offer per Product

In Google Shopping, we have products identified by a unique id.

Each product can have multiple offers associated with it, and each offer has a corresponding price.

Design a data structure to support the following operations:

• AddOffer(int64 offer_id, int64 product_id, double price) adds offer_id with the specified price for product_id.
• RemoveOffer(int64 offer_id) marks the offer as no longer valid.
• QueryClosestOffer(int64 product_id, double price) returns the id of an offer for the specified product whose price is closest to the query price.

Example:

AddOffer(offer1, product1, 2.3)
AddOffer(offer2, product1, 2.6)
QueryClosestOffer(product1, 2.5) -> offer2
QueryClosestOffer(product1, 2) -> offer1
RemoveOffer(offer2)
QueryClosestOffer(product1, 2.5) -> offer1
QueryClosestOffer(product2, 1) -> -1

This problem is about maintaining a dynamic set of offers per product, with fast insertion, deletion, and nearest-price lookup. A common solution is to keep a reverse map from offer_id to its product and price, plus a per-product ordered structure such as a balanced BST, TreeMap, multiset, or skip list. For a query, locate the nearest lower and higher prices around the target and compare their distances to decide which offer_id to return. If a product has no valid offers, return -1. The key challenge is supporting all three operations efficiently while handling multiple offers for the same product and invalidation correctly.