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.
Overview: 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.
Community answers
Answer by tonychungyay
from collections import defaultdict
from typing import List, Tuple
def most_frequent_snapshot(logs: List[str]) -> Tuple[str, int]:
stack = []
freq = defaultdict(int)
best_snapshot = ""
best_count = 0
for entry in logs:
if entry.startswith("->"):
name = entry[2:]
stack.append(name)
snapshot = "->".join(stack)
freq[snapshot] += 1
if freq[snapshot] > best_count:
best_snapshot = snapshot
best_count = freq[snapshot]
elif entry.startswith("<-"):
name = entry[2:]
if not stack or stack[-1] != name:
raise ValueError(f"Invalid log: exiting {name} but stack is {stack}")
stack.pop()
else:
raise ValueError(f"Invalid log entry: {entry}")
return best_snapshot, best_count
Test:
logs = ['->A', '->B', '->C', '<-C', '->C', '<-C', '<-B', '<-A']
snapshot, count = most_frequent_snapshot(logs)
print(snapshot, count)