Design a Balloon Festival Simulator
Company: Optiver
Role: Software Engineer
Category: Coding & Algorithms
Difficulty: medium
Interview Round: Take-home Project
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.
Quick Answer: 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
- 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).
- To find the highest stable competitor efficiently, consider a heap with lazy deletion (store versions and discard stale entries).