Most frequent call stack per thread from enter/exit logs, deeper stacks win ties
Company: Roblox
Role: Software Engineer
Category: Coding & Algorithms
Difficulty: medium
Interview Round: Technical Screen
A program writes a log of function calls. Each log line records that a thread entered or exited a function. At any moment, each thread has its own call stack: the functions it has entered and not yet exited, listed from the outermost to the innermost.
Every time a thread enters a function, the thread's call stack right after that entry counts as one occurrence of that call stack for that thread. For each thread, return its most frequent call stack.
The interview built this up in three steps: first, find the most frequent call stack in a log; second, when several stacks tie on count, return the deeper one; third, compute the answer separately for each thread. This version asks for the final behavior, which includes all three. A log that uses a single thread is exactly the first two steps.
### Function Signature
```python
def most_frequent_call_stacks(logs: list[str]) -> dict[str, list[str]]:
```
Each log line has the form `"<thread_id> <action> <function>"`, with single spaces between the three fields, where `<action>` is `enter` or `exit`. Return a dictionary that maps every thread ID appearing in `logs` to that thread's most frequent call stack, written as a list of function names from the outermost to the innermost.
### Rules
- Lines are in chronological order. Lines from different threads may interleave, and each thread's stack changes only with that thread's own lines.
- `enter f` pushes `f` onto the thread's stack, and the whole stack after the push counts as one occurrence. `exit f` pops `f` and never creates an occurrence.
- Two stacks are the same only if they contain the same function names in the same order. A function may appear more than once in one stack (recursion).
- Counts are kept per thread: an occurrence on one thread never counts toward another thread.
- The answer for a thread is chosen by, in order: the highest occurrence count; then the greatest depth (number of functions in the stack); then the stack that comes first lexicographically, comparing function names position by position by character code (the order Python's `<` gives on lists of strings).
- A log may end while some functions are still open. That changes nothing: occurrences are counted when functions are entered.
### Constraints
- `1 <= len(logs) <= 10^4`
- Thread IDs and function names are 1 to 20 characters, each from `A-Z`, `a-z`, `0-9` and `_`.
- Every line is well formed, and every `exit f` names the function at the top of that thread's stack. As a result, the first line of every thread is an `enter`.
- There are at most 100 distinct thread IDs.
- A thread's stack never holds more than 100 functions.
### Examples
**Example 1**
```text
Input: logs = ["t1 enter main", "t1 enter load", "t1 exit load", "t1 enter load",
"t1 enter parse", "t1 exit parse", "t1 exit load", "t1 enter render",
"t1 exit render", "t1 exit main"]
Output: {"t1": ["main", "load"]}
```
The entries create the occurrences `[main]`, `[main, load]`, `[main, load]`, `[main, load, parse]` and `[main, render]`. Only `[main, load]` occurs twice.
**Example 2**
```text
Input: logs = ["t1 enter main", "t1 enter x", "t1 enter y", "t1 exit y", "t1 exit x",
"t1 enter w", "t1 enter z", "t1 exit z", "t1 exit w", "t1 exit main"]
Output: {"t1": ["main", "w", "z"]}
```
The occurrences are `[main]`, `[main, x]`, `[main, x, y]`, `[main, w]` and `[main, w, z]`, each once. The deepest stacks are `[main, x, y]` and `[main, w, z]`, both of depth 3. They agree on `main` and differ next at `"w" < "x"`, so `[main, w, z]` is returned.
**Example 3**
```text
Input: logs = ["t1 enter main", "t2 enter worker", "t2 enter fetch", "t1 enter init",
"t2 exit fetch", "t2 enter fetch", "t1 exit init", "t2 exit fetch",
"t2 exit worker", "t1 exit main"]
Output: {"t1": ["main", "init"], "t2": ["worker", "fetch"]}
```
Thread `t1` sees `[main]` and `[main, init]` once each, so the deeper `[main, init]` wins. Thread `t2` sees `[worker]` once and `[worker, fetch]` twice. The `init` entry belongs to `t1` and is pushed onto `t1`'s stack, even though `t2` has `fetch` open at that moment.
Overview: Parse a log of thread-tagged function enter and exit events, maintain a separate call stack for each thread, and return each thread's most frequently occurring call stack, preferring deeper stacks on ties. Tests stack simulation, careful log parsing, counting sequences as keys and multi-level tie-breaking.
A program writes a log of function calls. Each log line records that a thread entered or exited a function. At any moment, each thread has its own call stack: the functions it has entered and not yet exited, listed from the outermost to the innermost.
Every time a thread enters a function, the thread's call stack right after that entry counts as one occurrence of that call stack for that thread. For each thread, return its most frequent call stack.
Implement `most_frequent_call_stacks(logs)`. Each log line has the form `"<thread_id> <action> <function>"`, with single spaces between the three fields, where `<action>` is `enter` or `exit`. Return a dictionary (a map or object in Java, C++ and JavaScript) that maps every thread ID appearing in `logs` to that thread's most frequent call stack, written as a list of function names from the outermost to the innermost. The order of the keys in the returned dictionary does not matter.
### Rules
- Lines are in chronological order. Lines from different threads may interleave, and each thread's stack changes only with that thread's own lines.
- `enter f` pushes `f` onto the thread's stack, and the whole stack after the push counts as one occurrence. `exit f` pops `f` and never creates an occurrence.
- Two stacks are the same only if they contain the same function names in the same order. A function may appear more than once in one stack (recursion).
- Counts are kept per thread: an occurrence on one thread never counts toward another thread.
- The answer for a thread is chosen by, in order: the highest occurrence count; then the greatest depth (number of functions in the stack); then the stack that comes first lexicographically, comparing function names position by position by character code (the order Python's `<` gives on lists of strings). By character code, digits come before uppercase letters, uppercase letters before `_`, and `_` before lowercase letters; a name that is a prefix of another comes first (`"a"` before `"ab"`).
- A log may end while some functions are still open. That changes nothing: occurrences are counted when functions are entered.
Because the first line of every thread is an `enter`, every thread has at least one occurrence and therefore a nonempty answer. No count exceeds 10^4, so every number involved fits in a 32-bit signed integer.
### Constraints
- `1 <= len(logs) <= 10^4`
- Thread IDs and function names are 1 to 20 characters, each from `A-Z`, `a-z`, `0-9` and `_`.
- Every line is well formed, and every `exit f` names the function at the top of that thread's stack. As a result, the first line of every thread is an `enter`.
- There are at most 100 distinct thread IDs.
- A thread's stack never holds more than 100 functions.
### Example 1
```text
Input: logs = ["t1 enter main", "t1 enter x", "t1 enter y", "t1 exit y", "t1 exit x",
"t1 enter w", "t1 enter z", "t1 exit z", "t1 exit w", "t1 exit main"]
Output: {"t1": ["main", "w", "z"]}
```
The occurrences are `[main]`, `[main, x]`, `[main, x, y]`, `[main, w]` and `[main, w, z]`, each once. The deepest stacks are `[main, x, y]` and `[main, w, z]`, both of depth 3. They agree on `main` and differ next at `"w" < "x"`, so `[main, w, z]` is returned.
### Example 2
```text
Input: logs = ["t1 enter main", "t2 enter worker", "t2 enter fetch", "t1 enter init",
"t2 exit fetch", "t2 enter fetch", "t1 exit init", "t2 exit fetch",
"t2 exit worker", "t1 exit main"]
Output: {"t1": ["main", "init"], "t2": ["worker", "fetch"]}
```
Thread `t1` sees `[main]` and `[main, init]` once each, so the deeper `[main, init]` wins. Thread `t2` sees `[worker]` once and `[worker, fetch]` twice. The `init` entry belongs to `t1` and is pushed onto `t1`'s stack, even though `t2` has `fetch` open at that moment.
Constraints
- 1 <= len(logs) <= 10^4
- Each line has the form "<thread_id> <action> <function>" with single spaces between the three fields, and <action> is enter or exit.
- Thread IDs and function names are 1 to 20 characters, each from A-Z, a-z, 0-9 and _.
- Every line is well formed, and every exit f names the function at the top of that thread's stack. As a result, the first line of every thread is an enter.
- There are at most 100 distinct thread IDs.
- A thread's stack never holds more than 100 functions.
Examples
Input: (['t1 enter main'],)
Expected Output: {'t1': ['main']}
Explanation: Minimum valid log: a single enter gives the only occurrence [main].
Input: (['t1 enter main', 't1 enter load', 't1 exit load', 't1 enter load', 't1 enter parse', 't1 exit parse', 't1 exit load', 't1 enter render', 't1 exit render', 't1 exit main'],)
Expected Output: {'t1': ['main', 'load']}
Explanation: Source Example 1: [main, load] is the only stack entered twice.
Hints
- Each thread's stack changes only with that thread's own lines, and counts never cross threads, so keep every thread's state separate.
- An occurrence is the whole stack right after an enter, not just the function that was entered, and exit lines never add an occurrence.
- Two stacks match only when they have the same names in the same order, so [a, bc] and [ab, c] are different stacks. Apply the tie-breaks strictly in order: count, then depth, then name-by-name character-code order.