Google OA 面试真题解析：按商品价格查找最近报价

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

这道题考察的是如何为每个商品维护“可动态增删、并支持按价格最近值查询”的报价集合。典型做法是用两个映射：一个保存 offer_id 到 (product_id, price) 的反向索引，便于删除时快速定位；另一个按 product_id 维护有序结构（如平衡二叉搜索树、TreeMap、multiset 或跳表）来存储该商品下所有有效报价。查询时在有序结构中找到最接近目标价格的左右邻居，再比较差值决定返回哪一个 offer_id；如果没有任何报价则返回 -1。重点在于同时满足插入、删除和最近值查询的效率，并正确处理相同商品下多个报价、删除后失效以及边界情况。