Optiver OA Coding Interview Question: Squirrel Research Hide and Retrieve Nuts

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.

This Optiver OA problem is a simulation and data-structure design task. You need to model locations with multiple levels, hide nuts from the deepest level upward, and retrieve them from the highest reachable level with weight-based ordering and tie-breaking by id. The tricky parts are expiration handling, capacity limits, and the rule that the lightest nut from an upper level falls down when a lower level is accessed. A practical solution usually combines per-level heaps, level capacity tracking, and careful state updates for each hide and retrieve operation.