Find most frequent call stack from logs

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.

Find Most Frequent Call Stack from Logs

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.

Hints

1. Use a stack to simulate the current call stack, and only count snapshots after '->Name' events.
2. 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.

Approach

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).

• 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.