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.

What difficulty level is this coding question?

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

What role is this question designed for?

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

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.

You are given a list of log entries for a single-threaded program. Each entry is either '->Name' (a function is entered) or '<-Name' (the current function exits). The logs are valid, so every exit matches the most recent unmatched entry. After every '->Name' event, record the current call-stack snapshot from root to top, joined by '->'. For example, if the current stack is [A, B, C], the snapshot string is 'A->B->C'. Return the snapshot that appears most frequently across the entire log and the number of times it appears. If multiple snapshots have the same highest frequency, return the lexicographically smallest snapshot. If there are no entry events at all, return ('', 0). A function may call itself recursively, so the same name can appear multiple times in one snapshot.

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)

Time complexity: O(n + S), where n is the number of log entries and S is the total length of distinct snapshot strings created. Space complexity: O(U + S), where U is the number of distinct stack states and S is the total length of distinct snapshot strings stored.

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.

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