Find most frequent call stack from logs
Company: Roblox
Role: Software Engineer
Category: Coding & Algorithms
Difficulty: medium
Interview Round: Technical Screen
Given an array of log entries for a single-threaded program's function calls, each entry is either '->Name' (function entry) or '<-Name' (function exit). The call stack updates accordingly. Consider the call-stack snapshot immediately after each '->Name' (root at the left, top at the right) and represent it as a string like 'A->B->C'. Return the snapshot that appears most frequently across the entire log and the number of times it occurs. Example: ['->A','->B','->C','<-C','->C','<-C','<-B','<-A'] should return 'A->B->C' with count 2. Explain your approach, analyze time/space complexity, and provide working code.
Quick Answer: This question evaluates a candidate's ability to simulate and maintain a runtime call stack from event logs, parse entry and exit records, and aggregate snapshot frequencies using appropriate data-structure and string-manipulation skills.
Given an execution log of a **single-threaded** program, find the call-stack state that occurs most often.
## What to implement
Write a function `solution(logs)` that takes a list of log-entry strings and returns the most frequently recorded call-stack snapshot together with how many times it appears.
## Input
`logs` is a list of strings. Each string is one of two event types:
- **`"->Name"`** — the function `Name` is **entered** (pushed onto the call stack).
- **`"<-Name"`** — the current function **exits** (the top frame is popped).
The log is guaranteed to be **valid**: every exit matches the most recent unmatched entry, so the call/return sequence is always well-formed.
A function may call itself, so the **same name can appear multiple times** in a single stack (e.g. `A->A`).
## What to record
Immediately after **each `"->Name"` (entry) event**, take a snapshot of the **current call stack** from **root to top** and join the frame names with `"->"`.
For example, if the live stack is `[A, B, C]`, the snapshot string is `"A->B->C"`. (Exit events do **not** produce a snapshot.)
## Output
Return a tuple `(snapshot, count)`:
- **`snapshot`** — the snapshot string that was recorded the most times across the entire log.
- **`count`** — the number of times that snapshot was recorded.
**Tie-break:** if two or more snapshots share the highest frequency, return the **lexicographically smallest** snapshot string.
**Empty case:** if the log contains **no entry events** at all (e.g. an empty list), return `("", 0)`.
## Examples
- `['->A','->B','->C','<-C','->C','<-C','<-B','<-A']` → `("A->B->C", 2)`
The stack `A->B->C` is snapshotted twice (once for the first `->C`, once for the second `->C`).
- `['->A','<-A','->A','<-A','->B','<-B']` → `("A", 2)`
`"A"` is recorded twice and `"B"` once.
- `['->A','->A','<-A','->A','<-A','<-A']` → `("A->A", 2)`
Recursion lets `A` appear twice in one snapshot.
- `['->B','<-B','->A','<-A','->C','<-C']` → `("A", 1)`
Three distinct depth-1 snapshots each occur once; the lexicographically smallest, `"A"`, wins.
- `[]` → `("", 0)`
## Constraints
- `0 <= len(logs) <= 20000`
- Each function name has length between **1 and 20** and contains only letters, digits, or underscores.
- The logs form a **valid** call/return sequence for a single-threaded program.
- The maximum call-stack depth does not exceed **200**.
Constraints
- 0 <= len(logs) <= 20000
- Each function name has length between 1 and 20 and contains only letters, digits, or underscores
- The logs form a valid call/return sequence for a single-threaded program
- The maximum call-stack depth does not exceed 200
Examples
Input: ['->A','->B','->C','<-C','->C','<-C','<-B','<-A']
Expected Output: ('A->B->C', 2)
Explanation: The entry snapshots are 'A', 'A->B', 'A->B->C', and again 'A->B->C'. So 'A->B->C' appears 2 times.
Input: ['->A','<-A','->A','<-A','->B','<-B']
Expected Output: ('A', 2)
Explanation: The snapshots are 'A', 'A', and 'B'. The most frequent snapshot is 'A' with count 2.
Hints
- Use a stack to simulate the current call stack, and only count snapshots after '->Name' events.
- If rebuilding the whole snapshot every time feels wasteful, represent each stack state by its parent state plus the new function name and reuse states that appear again.