Stack Whose Pop Removes the Most Frequent Value, Ties Broken by Recency
Company: Amazon
Role: Software Engineer
Category: Coding & Algorithms
Difficulty: medium
Interview Round: Onsite
A frequency stack holds integers and supports two operations:
- **push x**: place `x` on top of the stack.
- **pop**: remove and return the value that occurs most often in the stack right now. If several values tie for the highest count, choose the one that has an occurrence closest to the top of the stack. Only that value's topmost occurrence is removed.
Given a sequence of operations, return the values returned by the pop operations, in order.
### Function Signature
```python
def frequency_stack(operations: list[tuple[str, int]]) -> list[int]:
```
Each operation is `("push", x)` or `("pop", 0)`. The integer in a pop operation is always `0` and is ignored.
### Rules
- The count of a value is the number of its occurrences currently in the stack. Occurrences already removed by earlier pops do not count.
- Among the values tied for the highest count, pick the one whose topmost occurrence is nearest the top of the stack, then remove exactly that occurrence. All other elements keep their order.
- A pop is issued only when the stack is not empty.
- If there are no pop operations, return an empty list.
### Constraints
- `1 <= len(operations) <= 10^5`
- `-10^9 <= x <= 10^9` for every pushed value
- Every pop is applied to a non-empty stack.
### Examples
**Example 1**
```text
Input: operations = [("push", 3), ("push", 8), ("push", 3), ("push", 8), ("push", 1), ("push", 3),
("pop", 0), ("pop", 0), ("pop", 0), ("pop", 0)]
Output: [3, 8, 3, 1]
```
The stack, bottom to top, is 3, 8, 3, 8, 1, 3. The first pop returns 3, which occurs three times, and leaves 3, 8, 3, 8, 1. Now 3 and 8 both occur twice, and the topmost 8 is above the topmost 3, so 8 is returned, leaving 3, 8, 3, 1. Next 3 is the only value that occurs twice, leaving 3, 8, 1. Finally 3, 8 and 1 each occur once, and 1 is on top.
**Example 2**
```text
Input: operations = [("push", 2), ("push", 2), ("push", 9), ("pop", 0), ("push", 9),
("pop", 0), ("pop", 0), ("pop", 0)]
Output: [2, 9, 9, 2]
```
After three pushes the stack is 2, 2, 9. The first pop returns 2 and leaves 2, 9. Pushing 9 gives 2, 9, 9, so 9 now occurs most often and is returned, leaving 2, 9. Then 2 and 9 each occur once, and 9 is on top. The last pop returns 2.
**Example 3**
```text
Input: operations = [("push", -1), ("pop", 0), ("push", -1), ("push", 6), ("push", 6),
("push", -1), ("pop", 0)]
Output: [-1, -1]
```
The first pop empties the stack. Afterwards the stack is -1, 6, 6, -1: both values occur twice, and the topmost -1 is above the topmost 6.
Overview: Phone screen coding problem: process push and pop operations on a stack in which every pop removes the value that currently occurs most often, breaking ties by the tied value closest to the top. It tests designing a data structure that tracks frequency and recency together efficiently.
A frequency stack holds integers and supports two operations:
- **push x**: place `x` on top of the stack.
- **pop**: remove and return the value that occurs most often in the stack right now. If several values tie for the highest count, choose the one that has an occurrence closest to the top of the stack. Only that value's topmost occurrence is removed.
Implement `frequency_stack(operations)`. `operations` is a list of operations applied in order to an initially empty stack. Each operation is a pair `("push", x)` or `("pop", 0)`; the integer in a pop operation is always `0` and is ignored. Return the values returned by the pop operations, in the order the pops occur.
**Rules**
- The count of a value is the number of its occurrences currently in the stack. Occurrences already removed by earlier pops do not count.
- Among the values tied for the highest count, pick the one whose topmost occurrence is nearest the top of the stack, then remove exactly that occurrence. All other elements keep their order.
- A pop is issued only when the stack is not empty.
- If there are no pop operations, return an empty list.
**Example 1**
```text
Input: operations = [("push", 3), ("push", 8), ("push", 3), ("push", 8), ("push", 1), ("push", 3),
("pop", 0), ("pop", 0), ("pop", 0), ("pop", 0)]
Output: [3, 8, 3, 1]
```
The stack, bottom to top, is 3, 8, 3, 8, 1, 3. The first pop returns 3, which occurs three times, and leaves 3, 8, 3, 8, 1. Now 3 and 8 both occur twice, and the topmost 8 is above the topmost 3, so 8 is returned, leaving 3, 8, 3, 1. Next 3 is the only value that occurs twice, leaving 3, 8, 1. Finally 3, 8 and 1 each occur once, and 1 is on top.
**Example 2**
```text
Input: operations = [("push", 2), ("push", 2), ("push", 9), ("pop", 0), ("push", 9),
("pop", 0), ("pop", 0), ("pop", 0)]
Output: [2, 9, 9, 2]
```
After three pushes the stack is 2, 2, 9. The first pop returns 2 and leaves 2, 9. Pushing 9 gives 2, 9, 9, so 9 now occurs most often and is returned, leaving 2, 9. Then 2 and 9 each occur once, and 9 is on top. The last pop returns 2.
**Constraints**
- `1 <= len(operations) <= 10^5`
- `-10^9 <= x <= 10^9` for every pushed value
- Each operation is `("push", x)` or `("pop", 0)`.
- Every pop is applied to a non-empty stack.
Every pushed and returned value fits in a signed 32-bit integer.
Constraints
- 1 <= len(operations) <= 10^5
- -10^9 <= x <= 10^9 for every pushed value
- Each operation is ("push", x) or ("pop", 0); the integer in a pop operation is always 0 and is ignored
- Every pop is applied to a non-empty stack
Examples
Input: ([('push', 5)],)
Expected Output: []
Explanation: Minimum valid: a single push and no pops returns an empty list.
Input: ([('push', 7), ('pop', 0)],)
Expected Output: [7]
Explanation: Single push then single pop returns the only value.
Hints
- Only occurrences still in the stack count: every push raises one value's count by one, and every pop lowers one value's count by one.
- When several values share the highest count, compare where their topmost occurrences sit; the one pushed most recently among those occurrences is removed.
- A value whose occurrences have all been popped starts again from a count of zero.