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.
Input: ['->A','->A','<-A','->A','<-A','<-A']
Expected Output: ('A->A', 2)
Explanation: This is a recursive call pattern. The snapshots are 'A', 'A->A', and 'A->A', so 'A->A' occurs 2 times.
Input: ['->B','<-B','->A','<-A','->C','<-C']
Expected Output: ('A', 1)
Explanation: All snapshots appear once: 'B', 'A', and 'C'. By the tie rule, return the lexicographically smallest one, which is 'A'.
Input: []
Expected Output: ('', 0)
Explanation: There are no entry events, so there are no snapshots to count.
Input: ['->Main','->Load','<-Load','->Load','<-Load','->Run','<-Run','<-Main']
Expected Output: ('Main->Load', 2)
Explanation: The snapshots are 'Main', 'Main->Load', 'Main->Load', and 'Main->Run'. 'Main->Load' appears 2 times.
Solution
def solution(logs):
# Node 0 represents the empty stack.
parents = [-1]
snapshots = [""]
children = [{}]
counts = [0]
current = 0
best_snapshot = ""
best_count = 0
for entry in logs:
name = entry[2:]
if entry.startswith("->"):
next_node = children[current].get(name)
if next_node is None:
next_node = len(parents)
children[current][name] = next_node
parents.append(current)
if current == 0:
snapshots.append(name)
else:
snapshots.append(snapshots[current] + "->" + name)
children.append({})
counts.append(0)
current = next_node
counts[current] += 1
snap = snapshots[current]
if counts[current] > best_count or (counts[current] == best_count and snap < best_snapshot):
best_count = counts[current]
best_snapshot = snap
else:
# Logs are guaranteed to be valid.
if current != 0:
current = parents[current]
return (best_snapshot, best_count)
Explanation
## Approach: a trie of call-stack states
Every `->Name` event records the *current* stack snapshot (e.g. `A->B->C`). Naively rebuilding and counting that string on every event is expensive, so this solution **memoizes each distinct stack state as a node in a trie**.
Each node `i` stores four parallel arrays:
- `parents[i]` — the node reached by popping the top frame (where to return on `<-`)
- `children[i]` — a dict mapping a function name to the child node for that name (gives O(1) state lookup and dedup)
- `snapshots[i]` — the precomputed `root->...->top` string for this exact stack
- `counts[i]` — how many times this snapshot has been recorded
Node `0` is the empty stack. `current` always points at the node for the live stack.
**On `->Name`:** look up `children[current][name]`. If absent, create a new node whose `snapshots` value is `parent_snapshot + "->" + name` (or just `name` at depth 1) — this builds the string once per distinct state, not per event. Move `current` to that child and increment `counts[current]`.
**On `<-Name`:** pop by setting `current = parents[current]`. The logs are guaranteed valid, so no name check is needed.
**Tracking the answer:** after each increment, compare against `best_count`/`best_snapshot`, taking the higher count or, on a tie, the lexicographically smaller snapshot. Because identical stacks always map to the same node, every occurrence of a snapshot lands on one shared counter — the counts are exact. Empty input yields `("", 0)`.
Time complexity: O(n + S), where n is the number of log entries and S is the total length of all distinct snapshot strings created. Each event is O(1) amortized for dict/array ops; the snapshot string for a state is built only once (cost proportional to its length), and tie-break comparisons are bounded by snapshot length.. Space complexity: O(U + S), where U is the number of distinct stack states (trie nodes) and S is the total length of the distinct snapshot strings stored. The parents/children/counts arrays are O(U); the snapshots array holds O(S) characters in total..
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.