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

Simulate Turn-Based Monster Battles | OpenAI Coding Question

Quick Overview

This question evaluates the ability to implement a turn-based battle simulation with correct state management, turn semantics, knockout handling, damage computation, tie-breaking, and performance-aware move selection and type-effectiveness logic.

Simulate Turn-Based Monster Battles

Company: OpenAI

Role: Machine Learning Engineer

Category: Coding & Algorithms

Difficulty: medium

Interview Round: Onsite

Simulate a turn-based battle between two teams of monsters. Base problem: - Team A and Team B are ordered lists of monsters. - Each monster has at least `hp` and `atk`. - Team A attacks first. - On each action, the active attacker deals damage equal to its `atk` to the opposing active monster. - If a monster's HP drops to `0` or below, it is removed immediately and the next monster on that team becomes active. - Turns alternate after every action, even if an attack causes a knockout. - The battle ends when one team has no monsters left. Return: - Winner: `A`, `B`, or `Draw` if your rules allow it - Remaining HP of the winner's current active monster - Total number of attacks Common follow-ups: 1. Add monster types and a type-effectiveness table. Damage becomes `floor(atk * multiplier)` with minimum damage `1`. 2. Give each monster multiple moves. On each turn, the attacker chooses the move that yields the highest current damage against the defender; break ties by smallest move index. 3. Optimize repeated battles when a monster may have a very large move list, so scanning all moves every turn is too slow. This question tests simulation correctness, turn semantics, state updates after knockouts, tie-breaking, and incremental optimization.

Quick Answer: This question evaluates the ability to implement a turn-based battle simulation with correct state management, turn semantics, knockout handling, damage computation, tie-breaking, and performance-aware move selection and type-effectiveness logic.

Part 1: Base Turn-Based Monster Battle Simulation

Simulate a battle between two ordered teams of monsters. Each monster is represented as [hp, atk]. Team A attacks first. On each action, the active attacker deals damage equal to its atk to the opposing active monster. If a monster's HP becomes 0 or less, it is removed immediately and the next monster on that team becomes active. Turns still alternate after every action, even after a knockout. The battle ends when one team has no monsters left. Return the winner, the remaining HP of the winner's current active monster, and the total number of attacks. If both teams are empty at the start, return a draw.

Constraints

0 <= len(team_a), len(team_b) <= 10^5
Each monster is [hp, atk] with 1 <= hp, atk <= 10^4
The total number of attacks in the simulated battle will not exceed 2 * 10^5

Examples

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

Expected Output: ('A', 3, 3)

Explanation: A attacks first and wins after 3 total attacks.

Loading coding console...

Part 2: Battle Simulation with Monster Types and Effectiveness

Simulate the same battle as in Part 1, but now each monster is [hp, atk, type_id]. Damage dealt by an attacker is floor(atk * multiplier), where multiplier comes from type_chart[attacker_type][defender_type]. Damage has a minimum of 1, even if the multiplier is 0. Team A attacks first, knockouts remove monsters immediately, and turns still alternate after every action.

Constraints

0 <= len(team_a), len(team_b) <= 10^5
Each monster is [hp, atk, type_id] with 1 <= hp, atk <= 10^4
0 <= type_id < len(type_chart)
type_chart is a square matrix of non-negative multipliers
The total number of attacks in the simulated battle will not exceed 2 * 10^5

Examples

Input: ([[10, 4, 0]], [[10, 4, 1]], [[1.0, 2.0], [0.5, 1.0]])

Expected Output: ('A', 8, 3)

Explanation: Type 0 is strong against type 1, so A deals 8 damage per hit and wins.

Input: ([[3, 5, 0]], [[2, 1, 1]], [[0.0, 0.0], [1.0, 1.0]])

Expected Output: ('A', 2, 3)

Explanation: A's multiplier is 0, but minimum damage is still 1.

Input: ([[5, 2, 1], [7, 3, 0]], [[4, 4, 0], [6, 2, 1]], [[1.0, 2.0], [0.5, 1.0]])

Expected Output: ('A', 6, 5)

Explanation: Type effects matter across multiple monster switches.

Input: ([], [], [[1.0]])

Expected Output: ('Draw', 0, 0)

Explanation: Both teams are empty at the start.

Hints

Write a small helper to compute damage from one active monster to the other.
Even if the type multiplier is 0, the damage rule still forces at least 1 damage.

Part 3: Battle Simulation with Multiple Moves and Best-Move Selection

Now each monster is [hp, atk, type_id, moves]. The monster's type_id is used when defending. Each move is [power, move_type]. On each turn, the attacker chooses the move that produces the highest current damage against the defender. Damage is floor(attacker_atk * move_power * type_chart[move_type][defender_type]) with minimum 1. If several moves tie for best damage, choose the one with the smallest move index. Team A attacks first, knockouts remove monsters immediately, and turns still alternate after every action.

Constraints

0 <= len(team_a), len(team_b) <= 10^5
Each monster is [hp, atk, type_id, moves] with 1 <= hp, atk <= 10^4
Each moves list is non-empty
Each move is [power, move_type] with 1 <= power <= 10^4 and 0 <= move_type < len(type_chart)
0 <= type_id < len(type_chart)
The total number of attacks in the simulated battle will not exceed 2 * 10^5
The total number of moves across both teams will not exceed 2 * 10^5

Examples

Input: ([[10, 2, 0, [[1, 0], [2, 1]]]], [[6, 1, 1, [[1, 1]]]], [[1.0, 2.0], [0.5, 1.0]])

Expected Output: ('A', 9, 3)

Explanation: A has two equally strong moves against the defender, so the smaller index is chosen. A still wins in 3 attacks.

Input: ([[12, 2, 0, [[2, 0], [2, 1]]]], [[5, 1, 2, [[1, 2]]], [5, 1, 1, [[1, 1]]]], [[1.0, 2.0, 0.5], [0.5, 1.0, 2.0], [2.0, 0.5, 1.0]])

Expected Output: ('A', 11, 3)

Explanation: A should use a different best move against the first and second defenders.

Input: ([[3, 5, 0, [[1, 0]]]], [[2, 1, 1, [[1, 1]]]], [[0.0, 0.0], [1.0, 1.0]])

Expected Output: ('A', 2, 3)

Explanation: Minimum damage 1 still applies after move power and type multiplier are combined.

Input: ([], [[7, 3, 0, [[1, 0]]]], [[1.0]])

Expected Output: ('B', 7, 0)

Explanation: If Team A is empty, Team B wins immediately.

Hints

For each turn, compare all moves of the active attacker against the current defender's type.
Tie-breaking is by smallest move index, so keep both the best damage and the index while scanning moves.

Part 4: Optimize Repeated Battles with Large Move Lists

You are given a reusable monster catalog, a type-effectiveness table, and many independent battle queries. Each catalog monster is [hp, atk, type_id, moves], where moves is a non-empty list of [power, move_type]. A battle query contains two ordered teams of catalog indices. Each referenced monster starts each query with full HP. Battle rules are the same as Part 3: Team A attacks first, on each turn the attacker chooses the move with the highest current damage against the defender, ties break by smallest move index, damage is floor(atk * power * multiplier) with minimum 1, knockouts remove monsters immediately, and turns still alternate after every action. Because the same monster may appear in many queries and may have a huge move list, scanning all moves on every turn is too slow. Return the result for every query.

Constraints

1 <= len(type_chart) <= 20
0 <= len(monster_catalog) <= 10^5
Each catalog monster is [hp, atk, type_id, moves] with 1 <= hp, atk <= 10^4
Each moves list is non-empty
Each move is [power, move_type] with 1 <= power <= 10^4 and 0 <= move_type < len(type_chart)
0 <= type_id < len(type_chart)
The sum of move counts across the whole catalog will not exceed 2 * 10^5
All battle indices are valid catalog indices
The total number of simulated attacks across all battle queries will not exceed 2 * 10^5

Examples

Input: ([[10, 2, 0, [[1, 0], [2, 1]]], [6, 1, 1, [[1, 1]]], [5, 3, 0, [[1, 0]]]], [[1.0, 2.0], [0.5, 1.0]], [([0], [1]), ([2], [1])])

Expected Output: [('A', 9, 3), ('A', 5, 1)]

Explanation: The same defender appears in two different battles, and the precomputed best damage makes each turn fast.

Input: ([[12, 2, 0, [[2, 0], [2, 1]]], [5, 1, 2, [[1, 2]]], [5, 1, 1, [[1, 1]]]], [[1.0, 2.0, 0.5], [0.5, 1.0, 2.0], [2.0, 0.5, 1.0]], [([0], [1, 2]), ([1, 2], [0])])

Expected Output: [('A', 11, 3), ('B', 9, 4)]

Explanation: The same strong monster is reused in multiple queries against different team orders.

Input: ([[3, 5, 0, [[1, 0]]], [2, 1, 1, [[1, 1]]]], [[0.0, 0.0], [1.0, 1.0]], [([0], [1]), ([1], [0])])

Expected Output: [('A', 2, 3), ('B', 1, 4)]

Explanation: Minimum damage 1 must still be respected in every query.

Input: ([[7, 3, 0, [[1, 0]]]], [[1.0]], [([], []), ([0], []), ([], [0])])

Expected Output: [('Draw', 0, 0), ('A', 7, 0), ('B', 7, 0)]

Explanation: Edge cases with empty teams should be handled without any attacks.

Hints

The best move against a defender depends only on the attacker's move list and the defender's type, not on the defender's current HP.
Precompute, for each catalog monster and each defender type, the best damage it can deal. Then each turn becomes an O(1) lookup.