Find most frequent call path in logs
Company: Roblox
Role: Software Engineer
Category: Coding & Algorithms
Difficulty: medium
Interview Round: Technical Screen
You are given a sequence of trace log lines for a **single-threaded** program. Each line is either a function **entry** or **exit**:
- Entry: `"-> funcName"`
- Exit: `"<- funcName"`
Maintain a call stack as you scan the logs from left to right.
Whenever you see an **entry** line, push the function onto the stack and form the **full call path** by joining the stack elements with `"->"` (including the top). For example, stack `[main, handleEvents, handleClickEvent]` corresponds to the path:
`main->handleEvents->handleClickEvent`
Count how many times each full call path occurs (**only on entry events**). Return the path string with the **highest frequency**.
### Tie-breaking
If multiple paths have the same highest frequency:
1. Prefer the **deeper** path (the one with more functions).
2. If depth is also tied, prefer the one that **appears first** while scanning the logs (i.e., the earliest time that path was encountered).
If the input list is empty, return an empty string.
### Examples
**Example 1**
Input:
```
["-> main",
"-> handleEvents",
"-> handleClickEvent",
"<- handleClickEvent",
"-> handleClickEvent",
"<- handleClickEvent",
"<- handleEvents",
"<- main"]
```
Output:
```
"main->handleEvents->handleClickEvent"
```
**Example 2**
Input:
```
["-> main",
"-> handleEvents",
"-> handleKeyEvent",
"<- handleKeyEvent",
"-> handleClickEvent",
"<- handleClickEvent",
"-> handleClickEvent",
"<- handleClickEvent",
"-> handleKeyEvent",
"<- handleKeyEvent",
"<- handleEvents",
"<- main"]
```
Output:
```
"main->handleEvents->handleClickEvent"
```
**Example 3**
Input:
```
[]
```
Output:
```
""
```
### Constraints
- `0 ≤ len(traces) ≤ 100,000`
- Each log line starts with either `"-> "` or `"<- "`.
- `funcName` contains only letters, digits, or underscores.
- Logs are well-formed: every exit matches a previous entry.
- No recursion: the same function will not be re-entered before it returns.
- Max call depth ≤ 1,000.
- Number of distinct paths ≤ number of entry events.
Quick Answer: This question evaluates stack-based simulation of single-threaded call traces, hierarchical path construction and frequency counting with deterministic tie-breaking by depth and first occurrence. It is commonly asked in the Coding & Algorithms domain to assess practical application of data structures and parsing logic for runtime logs rather than purely conceptual theory.
You are given a list of trace log lines from a single-threaded program. Each line is either a function entry ('-> funcName') or a function exit ('<- funcName'). Scan the logs from left to right while maintaining the current call stack. Only entry events contribute to counts: whenever you read an entry line, push that function onto the stack, form the full call path by joining the stack with '->', and count that path. Return the path string with the highest frequency. If multiple paths have the same frequency, prefer the deeper path. If depth is also tied, prefer the path that was encountered first while scanning the logs. If the input list is empty, return an empty string.
Constraints
- 0 <= len(traces) <= 100000
- Each log line starts with either '-> ' or '<- '
- funcName contains only letters, digits, or underscores
- Logs are well-formed: every exit matches a previous entry
- No recursion: the same function is not re-entered before it returns
- Maximum call depth <= 1000
Examples
Input: ['-> main', '-> handleEvents', '-> handleClickEvent', '<- handleClickEvent', '-> handleClickEvent', '<- handleClickEvent', '<- handleEvents', '<- main']
Expected Output: 'main->handleEvents->handleClickEvent'
Explanation: The path 'main->handleEvents->handleClickEvent' is encountered twice on entry events, more than any other full path.
Input: ['-> main', '-> handleEvents', '-> handleKeyEvent', '<- handleKeyEvent', '-> handleClickEvent', '<- handleClickEvent', '-> handleClickEvent', '<- handleClickEvent', '<- handleEvents', '<- main']
Expected Output: 'main->handleEvents->handleClickEvent'
Explanation: The click path appears twice, while every other path appears once.
Input: []
Expected Output: ''
Explanation: With no log lines, no call path is ever formed.
Input: ['-> a', '-> b', '<- b', '<- a', '-> c', '<- c']
Expected Output: 'a->b'
Explanation: All counted paths appear once, so frequency ties. 'a->b' is deeper than 'a' and 'c', so it wins.
Input: ['-> x', '<- x', '-> y', '<- y', '-> y', '<- y', '-> x', '<- x']
Expected Output: 'x'
Explanation: Both 'x' and 'y' appear twice at the same depth. 'x' was encountered earlier, so it wins the tie.
Hints
- A stack is enough to track the current active call path while scanning from left to right.
- To avoid rebuilding long path strings repeatedly, represent each full path by its parent path plus the current function.