Quick Overview

This question evaluates proficiency in data structures, event-driven simulation, numerical aggregation of spatially varying fields, and time-based state tracking for mutable entities.

Design a Balloon Festival Simulator

Company: Optiver

Role: Software Engineer

Category: Coding & Algorithms

Difficulty: medium

Interview Round: Online Assessment

Implement a class BalloonFestival with the following API and rules. Goal Track hot air balloons (yours and competitors), evolving wind fields, and balloon stability over time. When inspected at a timestamp, return the sorted names of your team’s balloons that are stable and flying at or above the highest stable competitor balloon. Initialization init(yourBalloonNames: list[str]) - Registers the set of balloon names that belong to your team; all other names that appear later are competitors. - Each balloon name is unique. - Constraint: 1 ≤ len(yourBalloonNames) < 2^20. Operations BalloonAscended(timestamp: float, balloonName: str, altitude: float) -> bool - Marks a balloon as ascended to the given altitude and updates its state. - Balloons are stable by default upon ascending. - Returns True if the state was updated successfully; otherwise False. BalloonDescended(timestamp: float, balloonName: str) -> bool - Marks a balloon as descended to the ground and resets its stability to the default. - Returns True on success; otherwise False. SetWindSpeed(timestamp: float, altitude: float, windSpeed: float) -> bool - Updates the wind speed centered at the given altitude. - Constraints: 0 < altitude < 2^15, 0 ≤ windSpeed < 2^5. - Returns True on success; otherwise False. InspectBalloons(timestamp: float) -> list[str] - Returns the sorted names of your team’s balloons that are stable at the given timestamp and whose altitudes are ≥ the highest stable competitor balloon at that timestamp. If none qualify, return []. Stability Rules - A balloon becomes immediately unstable if the wind speed at its altitude exceeds 15 m/s. - An unstable balloon regains stability only after it has remained at an altitude where the wind speed is ≤ 15 m/s for at least 300 seconds (inclusive). Wind Model - Wind from multiple defined altitudes adds cumulatively. - Let WindSpeedAtAltitude be the wind defined at WindAltitude, and h be a balloon’s current altitude. - The contribution from that wind source at altitude h is: WindSpeed(h) = WindSpeedAtAltitude / (1 + ((h - WindAltitude) / 100)^ 2) - The total wind speed at altitude h is the sum of contributions from all defined wind sources at the inspection time. Requirements - Design data structures and algorithms to support the above operations correctly and efficiently over many events.

Overview: This question evaluates proficiency in data structures, event-driven simulation, numerical aggregation of spatially varying fields, and time-based state tracking for mutable entities.

Implement a simulator for a hot air balloon festival. You will write a function that processes a sequence of timestamped operations on a virtual system. Some balloons belong to your team; all other balloon names that appear are competitors. When inspected at a timestamp, the simulator must return the **sorted names** of your team’s balloons that are: 1) **Stable** at that timestamp, and 2) Flying at an altitude **greater than or equal to** the altitude of the **highest stable competitor** balloon at that timestamp. If no competitor balloon is stable, then every stable, airborne balloon of yours qualifies. --- ### Operations The system supports the following operations (given in non-decreasing timestamp order): - `BalloonAscended(timestamp, balloonName, altitude) -> bool` - Marks a balloon as airborne at `altitude`. - On ascent, the balloon is **stable by default**, but it becomes **immediately unstable** if the wind speed at that altitude is > 15 m/s. - Returns `False` if the balloon is already airborne; otherwise `True`. - `BalloonDescended(timestamp, balloonName) -> bool` - Marks a balloon as on the ground (not airborne). - Returns `False` if the balloon is not currently airborne; otherwise `True`. - `SetWindSpeed(timestamp, altitude, windSpeed) -> bool` - Sets/overwrites the wind source centered at `altitude` to have strength `windSpeed`. - Returns `False` if constraints are violated; otherwise `True`. - `InspectBalloons(timestamp) -> list[str]` - Returns the sorted list of your team balloon names that qualify at `timestamp`. If an operation’s timestamp is **less** than the timestamp of the previous processed operation, it is considered invalid and has **no effect**: - It returns `False` for boolean-returning operations. - It returns `[]` for `InspectBalloons`. --- ### Stability rules - A balloon becomes **immediately unstable** if total wind speed at its altitude is **> 15**. - An unstable balloon becomes stable again only after it has continuously remained at an altitude where wind speed is **≤ 15** for **at least 300 seconds (inclusive)**. --- ### Wind model Wind consists of multiple sources. A wind source is defined by `(WindAltitude, WindSpeedAtAltitude)`. The contribution of one source at altitude `h` is: `contrib(h) = WindSpeedAtAltitude / (1 + ((h - WindAltitude) / 100)^2)` The **total wind speed** at altitude `h` is the **sum** of contributions from all currently defined wind sources. `SetWindSpeed` overwrites any existing source at the same `WindAltitude`. --- ### What you must implement Write `solution(yourBalloonNames, operations)`. - `yourBalloonNames` is `list[str]`. - `operations` is a list of tuples. Each tuple begins with the operation name string: - `("BalloonAscended", timestamp, balloonName, altitude)` - `("BalloonDescended", timestamp, balloonName)` - `("SetWindSpeed", timestamp, altitude, windSpeed)` - `("InspectBalloons", timestamp)` Return a list of outputs corresponding to each operation in order (booleans for the first three, lists for `InspectBalloons`).

Constraints

  • 1 ≤ len(yourBalloonNames) < 2^20
  • Operations are intended to be given in non-decreasing timestamp order; if an operation has timestamp < previous processed timestamp, it must be treated as invalid with no effect
  • For this problem, altitudes are integers in meters
  • 0 < altitude < 2^15 (i.e., 1..32767) for both balloons and wind sources
  • 0 ≤ windSpeed < 2^5 (i.e., 0..31)
  • Unstable balloons regain stability after 300 seconds (inclusive) continuously in wind ≤ 15 m/s

Examples

Input: (["Alpha","Bravo"], [("BalloonAscended", 0, "Alpha", 1000), ("BalloonAscended", 0, "Bravo", 500), ("InspectBalloons", 10)])

Expected Output: [True, True, ["Alpha", "Bravo"]]

Explanation: No competitors exist; both balloons are stable and airborne, so both are returned sorted.

Input: (["A","B"], [("BalloonAscended", 0, "A", 1000), ("BalloonAscended", 0, "Rival", 1200), ("InspectBalloons", 1), ("BalloonAscended", 2, "B", 1500), ("InspectBalloons", 3)])

Expected Output: [True, True, [], True, ["B"]]

Explanation: At t=1 the highest stable competitor is at 1200 so A(1000) doesn't qualify. After B ascends to 1500, B qualifies at t=3.

Hints

  1. Track when an unstable balloon enters a safe-wind condition and schedule the earliest time it could become stable again (e.g., with a min-heap).
  2. To find the highest stable competitor efficiently, consider a heap with lazy deletion (store versions and discard stale entries).

Loading coding console...

Show the approach

Approach

The solution is an event-driven simulator that keeps a full wind field and a per-balloon stability state machine.

Wind model. A kernel array is precomputed: kernel[d] = 1/(1+(d/100)^2). A wind source (center, speed) contributes speed * kernel[h-center] at altitude h, so the total field is just a weighted sum of sources. wind_field[h] is materialized for every integer altitude 1..32767, and safe_flag[h] records whether that altitude is <= 15 m/s. SetWindSpeed overwrites a source, computes the delta, and adds delta * kernel across all altitudes, flipping any safe_flag that crosses 15 (an EPS guards the float comparison).

Stability state machine. Each Balloon tracks airborne, alt, stable, safe_start, and a ver counter. On ascent it is stable unless its altitude is unsafe. When wind makes an altitude unsafe, balloons there are marked unstable (mark_unstable); when it becomes safe, a 300-second regain_heap timer starts. advance_time(ts) pops due timers and re-stabilizes a balloon only if it is still airborne, unstable, and at a safe altitude.

Lazy invalidation. Both the regain_heap and the competitor max-heap (comp_heap, keyed by -alt) store the balloon's ver at push time; any state change bumps ver, so stale heap entries are skipped on pop instead of being deleted.

Inspect. It finds the highest stable competitor altitude via comp_heap, then returns your sorted balloons that are airborne, stable, and at altitude >= threshold (or all stable airborne ones if no competitor is stable). Out-of-order timestamps short-circuit to False/[]. This is correct because the field and flags are always kept consistent with the current sources.

Space complexity:
O(H + B + S): two float arrays of size H≈32768 (`wind_field`, `safe_flag`) plus the size-2H `kernel`, B `Balloon` objects and the `alt_to_balloons` index, and S scheduled regain/competitor entries across the two heaps.