How do I practice coding and algorithm questions?

Use PracHub's coding console to write, test, and debug your solutions in Python or JavaScript. View hints, test against sample inputs, and compare with official solutions.

What difficulty level is this coding question?

This is a hard difficulty Coding & Algorithms question, commonly asked during Onsite rounds at OpenAI.

What role is this question designed for?

This question is commonly asked for Machine Learning Engineer candidates at OpenAI during technical interviews.

Search Monster Battle Strategies | OpenAI Coding Question

Quick Overview

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).

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).

Part 1: Duel Between Two Monsters

Two monsters fight until one is permanently defeated. Each monster is given as (hp, attack, revive_hp). In every round, monster A attacks first. If monster B is still alive after that attack, it attacks back. When a monster's health becomes <= 0, it dies unless it still has an unused revive and revive_hp > 0; in that case it immediately revives with revive_hp health. Because the revive is immediate, a monster revived by A's attack is still allowed to counterattack in that same round. Return which monster wins the duel.

Constraints

1 <= hp, attack <= 10^18
0 <= revive_hp <= 10^18
Each monster may revive at most once

Loading coding console...

Examples

Input: ((10, 4, 0), (9, 3, 0))

Expected Output: 'A'

Explanation: A needs 3 hits to defeat B, while B needs 4 hits to defeat A.

Input: ((7, 3, 5), (10, 4, 0))

Expected Output: 'A'

Explanation: Both sides need 4 attacks to finish the other permanently, so A wins because it attacks first.

Input: ((1, 100, 0), (1, 1, 1))

Expected Output: 'B'

Explanation: A kills B's first life instantly, but B revives immediately and still attacks back that round, defeating A.

Input: ((5, 5, 5), (5, 5, 5))

Expected Output: 'A'

Explanation: Each monster effectively has two one-hit lives, so the first attacker wins.

Part 2: Fixed-Order Team Battle

Two teams of monsters battle until one side has no monsters left. Each monster is (hp, attack, revive_hp). Team B fights in the input order. In this version, Team A also uses a fixed input order: when Team A's current monster dies, the next monster in Team A's list enters. Within a round, Team A's active monster attacks first; if Team B's active monster is still alive after that attack, it attacks back. A monster that reaches health <= 0 is removed unless it still has an unused revive, in which case it immediately returns with revive_hp health. Health, revive usage, and survival all persist across consecutive opponents. Return the winning team.

Constraints

0 <= len(team_a), len(team_b) <= 2 * 10^5
1 <= hp, attack <= 10^18 for every monster
0 <= revive_hp <= 10^18 for every monster
Both teams must be simulated in order; do not reorder monsters

Examples

Input: ([(10, 4, 0)], [(9, 3, 0)])

Expected Output: 'A'

Explanation: This is the same as a single duel, and Team A wins.

Input: ([(5, 5, 0), (10, 3, 0)], [(6, 2, 0), (8, 4, 0)])

Expected Output: 'A'

Explanation: A1 beats B1, loses to B2 after weakening it, and A2 finishes B2.

Input: ([(10, 3, 0), (10, 3, 0)], [(15, 5, 0)])

Expected Output: 'B'

Explanation: The single Team B monster defeats both Team A monsters in sequence.

Input: ([(4, 3, 5)], [(6, 4, 2)])

Expected Output: 'A'

Explanation: Revives matter on both sides; Team A still wins because of the first-attack advantage.

Input: ([], [(1, 1, 0)])

Expected Output: 'B'

Explanation: Edge case: Team A starts with no monsters.

Hints

For a duel between the current two monsters, you can compute the winner from the number of hits needed instead of simulating round by round.
When one monster survives a duel, update its remaining health after exactly the number of counterattacks it actually suffered.

Part 3: Winning Strategy with Dynamic Choices

Now Team A may choose which alive monster to send whenever it needs a new active monster. Team B's order is still fixed by the input. Also assume Team A may choose any alive monster as its initial fighter. Once chosen, that monster continues fighting until it is knocked out or Team B is eliminated. Combat rules are unchanged: Team A attacks first each round, revives happen immediately, and a monster revived by A's attack may still counterattack in that round. Return whether Team A has some sequence of choices that leads to victory. Your solution should search reachable battle states efficiently and memoize repeated states.

Constraints

0 <= len(team_a), len(team_b) <= 6
1 <= hp, attack <= 20 for every monster
0 <= revive_hp <= 20 for every monster
An exact state-search solution with memoization is expected

Examples

Input: ([(10, 4, 0)], [(9, 3, 0)])

Expected Output: True

Explanation: With only one choice, Team A simply wins the duel.

Input: ([(6, 5, 0), (10, 2, 0)], [(7, 1, 0), (12, 5, 0)])

Expected Output: True

Explanation: Choosing the second Team A monster first is winning; after it softens the second enemy, the first monster can finish the battle.

Input: ([(5, 2, 0), (5, 2, 0)], [(8, 3, 0), (8, 3, 0)])

Expected Output: False

Explanation: No matter which monster Team A sends first, Team B eventually survives with enough health to win.

Input: ([(4, 3, 5), (8, 2, 0)], [(6, 4, 2), (7, 3, 0)])

Expected Output: True

Explanation: Revives create more possible states, but Team A can still force a win.

Input: ([], [(1, 1, 0)])

Expected Output: False

Explanation: Edge case: Team A has no monster to send.

Hints

A full state must capture every monster's current health and whether its revive is still unused.
From a decision state, picking one Team A monster leads to a deterministic sequence of fights until that chosen monster dies or Team B is gone.