Find most frequent call stack from logs

Q: Find most frequent call stack from logs

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.

Q: How do I practice coding and algorithm questions?

Use PracHub's coding console to write, test, and debug your solutions in Python or JavaScript. View hints, test against sample inputs, and compare with official solutions.

Q: What difficulty level is this coding question?

This is a Medium difficulty Coding & Algorithms question, commonly asked during Technical Screen rounds at Roblox.

Q: What role is this question designed for?

This question is commonly asked for Software Engineer candidates at Roblox during technical interviews.

Question

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.

PracHub · Accepted Answer

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)

Quick Overview

Solution

Hints

Quick Overview