Optiver OA 面试真题解析：Squirrel Research 隐藏与取回坚果问题

You are given a set of nut hiding locations and must implement a class that supports hiding and retrieving nuts.

Each location has a fixed number of levels. Nuts are hidden starting from the deepest level upward. A level can hold only a limited number of nuts, and a location becomes full when all of its levels are filled according to the given capacity rules.

Implement the following operations:

• __init__(locations: dict[string, integer]) Initializes the class with all available locations. The input map gives each location id and the number of levels it has.
• HideNut(timestamp: float, location_id: string, nut_id: string, nut_weight: float, time_to_expire: float) -> bool Attempts to hide a nut in the given location. Returns true if the operation succeeds, and false otherwise.
• RetrieveNut(timestamp: float, location_id: string, max_squirrel_capacity_in_nuts: integer) -> list[string] Attempts to retrieve nuts from a location. Returns a list of nut ids retrieved in order, or an empty list if the operation fails.

Rules:

• A nut_id is unique while the nut is hidden. If a nut is already hidden, the operation fails.
• If the location is full or invalid, hiding fails.
• If the location is empty or invalid, retrieval fails.
• Nuts are retrieved starting from the highest occupied level.
• Within a level, heavier nuts are retrieved first.
• If the highest level is occupied by less than 50% of its total capacity, the next lower level can also be reached.
• If there is a tie on weight, the nut with the smaller id is retrieved first.
• Every time a nut is taken out of a level that is not the topmost occupied level, the lightest nut from the level above falls into its place.
• If an expired nut is retrieved, it is immediately discarded.
• Retrieved and discarded nuts are removed from the location.
• Once retrieved, a nut_id may be used again to identify other nuts.

Timestamps are guaranteed to be globally increasing. Weights and timestamps are floating-point values with millisecond precision.

这道 Optiver OA 题本质上是一个“分层容器管理 + 优先队列 / 堆模拟”的设计题：每个 location 有若干层，坚果从最深层开始存放，检索时则从最高可达层开始，优先取更重的坚果，权重相同时按 id 字典序更小者优先。题目还引入了过期时间、容量判断、以及“上一层最轻坚果下落补位”的规则，因此实现时通常需要为每个位置维护每层的容量、当前数量、以及按权重排序的结构（如堆）来支持隐藏和取回操作。样例中 pineTree/oakTree 的过程展示了：隐藏会判断位置是否已满，retrieve 会按层级和重量顺序连续取出，并在遇到过期坚果时直接丢弃。