Microorganism Eating Simulation: Largest Survivor After Left-to-Right Rounds
Company: OpenAI
Role: Software Engineer
Category: Coding & Algorithms
Difficulty: hard
Interview Round: Online Assessment
Several microorganisms are lined up in a row. Each one belongs to a family, identified by a letter, and has a size, a positive integer. A microorganism can eat a neighbor directly to its left or right if that neighbor belongs to a different family and is strictly smaller. The simulation runs in rounds until no microorganism can eat another. When it stops, return the largest microorganism as its family letter, one space and its size.
### Function Signature
```python
def largest_at_equilibrium(organisms: list[tuple[str, int]]) -> str:
```
`organisms[i]` is `(family, size)` for the `i`-th microorganism from the left.
### Rules
- In each round, the microorganisms take turns from left to right. After a turn, the next turn belongs to the microorganism immediately to the right of the one that just took its turn, in the row as it is at that moment. A microorganism that is eaten before its turn gets no turn.
- On its turn, a microorganism checks its left neighbor first and then its right neighbor, and eats the first one that is a valid target. If neither is a valid target, it does nothing.
- A neighbor is a valid target if it belongs to a different family, its current size is strictly smaller than the eater's current size, and it has not eaten during the current round.
- When a microorganism eats, its size grows by the size of the target, and the target is removed, so the microorganisms on either side of the gap become neighbors. These changes take effect at once, so later turns in the same round see the new sizes and neighbors.
- A microorganism eats at most once per round, on its own turn, and a microorganism that has eaten during a round cannot be eaten during that round. Because turns run from left to right, when a microorganism could be eaten by either neighbor, the left neighbor's turn comes first.
- The simulation stops after the first round in which nothing is eaten.
- Return the family letter, a single space and the size of the largest remaining microorganism, for example `"B 15"`.
### Constraints
- `1 <= len(organisms) <= 20`
- Each family is a single uppercase English letter from `"A"` to `"Z"`.
- `1 <= size <= 10^6` for every microorganism.
- The input guarantees that, when the simulation stops, exactly one microorganism has the maximum size.
### Examples
**Example 1**
```text
Input: organisms = [("A", 2), ("B", 5), ("C", 3), ("C", 4), ("A", 1)]
Output: "B 15"
```
Round 1: `A 2` cannot eat `B 5`. `B 5` checks its left neighbor first and eats `A 2`, becoming `B 7`. `C 3` cannot eat `B 7`, and its right neighbor `C 4` is the same family. `C 4` eats `A 1` and becomes `C 5`. The row is now `B 7, C 3, C 5`. Round 2: `B 7` eats `C 3` and becomes `B 10`; `C 5` cannot eat `B 10`. Round 3: `B 10` eats `C 5` and becomes `B 15`. Round 4: nothing is eaten, so the simulation stops.
**Example 2**
```text
Input: organisms = [("A", 1), ("B", 2), ("C", 10)]
Output: "C 13"
```
Round 1: `A 1` cannot eat `B 2`. `B 2` eats `A 1` and becomes `B 3`. On its turn, `C 10` cannot eat `B 3`, because `B 3` has eaten during this round. Round 2: `C 10` eats `B 3` and becomes `C 13`. Round 3: nothing is eaten.
**Example 3**
```text
Input: organisms = [("A", 5), ("A", 2), ("B", 2), ("B", 6)]
Output: "B 6"
```
Each pair of neighbors is either the same family or the same size, so nothing is eaten in round 1 and the largest microorganism is `B 6`.
Overview: Simulate a row of microorganisms in which each one may eat a strictly smaller neighbor from a different family, with rounds resolved from left to right, and report the family and size of the largest survivor at equilibrium. It tests precise rule-following, list mutation during iteration, and careful per-round bookkeeping.
Several microorganisms are lined up in a row. Each one belongs to a family, identified by a single uppercase letter, and has a size, which is a positive integer. A microorganism can eat a neighbor directly to its left or right if that neighbor belongs to a different family and is strictly smaller. The simulation runs in rounds until no microorganism can eat another. When it stops, return the largest microorganism as its family letter, one space and its size.
Implement `largest_at_equilibrium(organisms)`. `organisms[i]` is the pair `(family, size)` for the `i`-th microorganism from the left (Python: a tuple; JavaScript: a two-element array; Java: a `java.util.List<Object>` holding the `String` family and the integer size; C++: a `std::pair<std::string, int>`).
### Rules
- In each round, the microorganisms take turns from left to right. After a turn, the next turn belongs to the microorganism immediately to the right of the one that just took its turn, in the row as it is at that moment. A microorganism that is eaten before its turn gets no turn.
- On its turn, a microorganism checks its left neighbor first and then its right neighbor, and eats the first one that is a valid target. If neither is a valid target, it does nothing.
- A neighbor is a valid target if it belongs to a different family, its current size is strictly smaller than the eater's current size, and it has not eaten during the current round.
- When a microorganism eats, its size grows by the size of the target, and the target is removed, so the microorganisms on either side of the gap become neighbors. These changes take effect at once, so later turns in the same round see the new sizes and neighbors.
- A microorganism eats at most once per round, on its own turn, and a microorganism that has eaten during a round cannot be eaten during that round. Because turns run from left to right, when a microorganism could be eaten by either neighbor, the left neighbor's turn comes first.
- The simulation stops after the first round in which nothing is eaten.
### Output
Return a string: the family letter of the largest remaining microorganism, a single space, then its size as a decimal integer, for example `"B 15"`. The input guarantees that this microorganism is unique.
### Constraints
- `1 <= len(organisms) <= 20`
- Each family is a single uppercase English letter from `"A"` to `"Z"`.
- `1 <= size <= 10^6` for every microorganism.
- The input guarantees that, when the simulation stops, exactly one microorganism has the maximum size.
- Sizes only grow by absorbing other microorganisms, so no size ever exceeds 20 * 10^6 = 2 * 10^7; every value fits in a signed 32-bit integer.
### Example 1
```text
Input: organisms = [("A", 2), ("B", 5), ("C", 3), ("C", 4), ("A", 1)]
Output: "B 15"
```
Round 1: `A 2` cannot eat `B 5`. `B 5` checks its left neighbor first and eats `A 2`, becoming `B 7`. `C 3` cannot eat `B 7`, and its right neighbor `C 4` is the same family. `C 4` eats `A 1` and becomes `C 5`. The row is now `B 7, C 3, C 5`. Round 2: `B 7` eats `C 3` and becomes `B 10`; `C 5` cannot eat `B 10`. Round 3: `B 10` eats `C 5` and becomes `B 15`. Round 4: nothing is eaten, so the simulation stops.
### Example 2
```text
Input: organisms = [("A", 1), ("B", 2), ("C", 10)]
Output: "C 13"
```
Round 1: `A 1` cannot eat `B 2`. `B 2` eats `A 1` and becomes `B 3`. On its turn, `C 10` cannot eat `B 3`, because `B 3` has eaten during this round. Round 2: `C 10` eats `B 3` and becomes `C 13`. Round 3: nothing is eaten.
Constraints
- 1 <= len(organisms) <= 20
- Each family is a single uppercase English letter from "A" to "Z".
- 1 <= size <= 10^6 for every microorganism.
- The input guarantees that, when the simulation stops, exactly one microorganism has the maximum size.
- Sizes only grow by absorbing others, so no size exceeds 20 * 10^6 = 2 * 10^7; every value fits in a signed 32-bit integer.
Examples
Input: ([('A', 2), ('B', 5), ('C', 3), ('C', 4), ('A', 1)],)
Expected Output: 'B 15'
Explanation: Source Example 1: B 5 eats A 2 and C 4 eats A 1 in round 1, then B absorbs C 3 in round 2 and C 5 in round 3.
Input: ([('A', 1), ('B', 2), ('C', 10)],)
Expected Output: 'C 13'
Explanation: Source Example 2: B 3 ate in round 1, so C 10 must wait and eats it in round 2.
Hints
- Within a round, remember which microorganisms have already eaten: they cannot eat again and cannot be eaten until the next round.
- When a microorganism is removed, its neighbors close the gap immediately. Make sure the next turn goes to the microorganism now directly to the right of the one that just moved, and that an eaten microorganism never gets a turn.
- The row only shrinks, and the first round with no meal ends the simulation, so the number of rounds is at most the number of microorganisms.