Search Monster Battle Strategies
Company: OpenAI
Role: Machine Learning Engineer
Category: Coding & Algorithms
Difficulty: hard
Interview Round: Onsite
You are given two teams of monsters. Each monster has:
- `hp`: starting health
- `attack`: damage dealt per attack
- `revive_hp`: if greater than `0`, the monster may revive exactly once, immediately after its first defeat, with that much health
The battle is deterministic and follows these rules:
1. In the base version, one monster from Team A fights one monster from Team B.
2. In the full version, the teams fight until one side has no monsters left.
3. Team B's order is fixed by the input.
4. Whenever one of Team A's monsters dies, you may choose any still-alive monster from Team A to send next.
5. In each round, Team A's active monster attacks first. If Team B's active monster is still alive after taking damage, it attacks back.
6. When a monster's health becomes `<= 0`, it is removed unless it has an unused revive, in which case it immediately returns with `revive_hp` health.
Implement the following progressively harder parts:
- Simulate a fight between two individual monsters.
- Simulate a full battle for a fixed order of Team A.
- Compute whether Team A has a winning strategy when it can choose the next monster dynamically after each knockout.
Your final solution should explore all reachable battle states efficiently and avoid recomputing identical states multiple times.
Quick Answer: This question evaluates algorithmic problem-solving around deterministic simulation and state-space exploration, focusing on handling transient state (health and single-use revives), turn-based interactions, and optimal sequencing of choices; it tests Coding & Algorithms skills including state representation, search strategies, memoization, and complexity reasoning. It is commonly asked to gauge a candidate's ability to reason about reachable states and optimal strategies in adversarial systems, and sits at the intersection of conceptual understanding (state-space and game-theoretic reasoning) and practical implementation (efficient simulation and caching).