Full Interview Question: Coding - Monster Battle System

Problem Overview: Design and implement a battle simulation system where two teams of monsters fight each other in a turn-based combat. Each team has a list of monsters, and each monster has health points and attack power. The battle continues until one of the teams is completely eliminated.

Problem Statement: Given two teams of monsters, each with a list of monsters, where each monster has health points (hp) and attack power (attack), implement a function to simulate the battle between the two teams. The battle is turn-based, and each monster attacks the monster with the lowest health points in the opposing team. If there is a tie, the monster with the lowest index is chosen. The battle continues until one of the teams is completely eliminated.

Examples:

1. Team 1: [[7, 2], [5, 4], [8, 7]] (hp, attack) Team 2: [[3, 1], [4, 3], [5, 2]] (hp, attack) Output: 1 (Team 1 wins)

2. Team 1: [[1, 1], [2, 2], [3, 3]] (hp, attack) Team 2: [[10, 10], [20, 20], [30, 30]] (hp, attack) Output: 2 (Team 2 wins)

Constraints:

• 1 <= len(teams) <= 100
• 1 <= len(teams[i]) <= 100
• 1 <= hp, attack <= 10^9
• The total number of monsters in both teams will not exceed 1000.

Hints:

1. Use a priority queue (min-heap) to efficiently select the monster with the lowest health points in the opposing team.
2. Keep track of the current team's turn and alternate between the two teams.
3. After each attack, update the health points of the attacked monster and check if it's eliminated.

Solution: `python import heapq

class Monster: def init(self, hp, attack): self.hp = hp self.attack = attack

def __repr__(self):
    return f"({self.hp}, {self.attack})"

def is_eliminated(monsters): return all(monster.hp <= 0 for monster in monsters)

def find_weakest(monsters): min_heap = [] for i, monster in enumerate(monsters): heapq.heappush(min_heap, (monster.hp, i)) return min_heap[0][1]

def battle(teams): team1, team2 = teams while not is_eliminated(team1) and not is_eliminated(team2): weakest_idx_team2 = find_weakest(team2) weakest_team2 = team2[weakest_idx_team2] strongest_idx_team1 = max(range(len(team1)), key=lambda i: team1[i].attack) strongest_team1 = team1[strongest_idx_team1] weakest_team2.hp -= strongest_team1.attack if weakest_team2.hp <= 0: team2.remove(weakest_team2) if is_eliminated(team2): return 1 weakest_idx_team1 = find_weakest(team1) weakest_team1 = team1[weakest_idx_team1] strongest_idx_team2 = max(range(len(team2)), key=lambda i: team2[i].attack) strongest_team2 = team2[strongest_idx_team2] weakest_team1.hp -= strongest_team2.attack if weakest_team1.hp <= 0: team1.remove(weakest_team1) if is_eliminated(team1): return 2 return 1 if not is_eliminated(team1) else 2

Example usage:

team1 = [Monster(7, 2), Monster(5, 4), Monster(8, 7)] team2 = [Monster(3, 1), Monster(4, 3), Monster(5, 2)] print(battle([team1, team2])) # Output: 1 `

Explanation: This solution uses a custom Monster class to represent each monster with its health points and attack power. The is_eliminated function checks if a team is completely eliminated. The find_weakest function uses a min-heap to find the monster with the lowest health points in the opposing team. The battle function simulates the turn-based combat between the two teams, alternating between each team's turn and attacking the weakest monster in the opposing team. The battle continues until one of the teams is completely eliminated, and the function returns the