Katkat
Back

Find most frequent call path in logs

RobloxSoftware Engineer · Technical Screen
MediumSoftware EngineerTechnical ScreenCoding & Algorithms

Last updated

This problem tests your ability to parse structured log strings representing nested function calls into a hierarchical tree and identify the most frequently occurring execution path.

Problem Statement

You are given a list of log entries representing the execution of a single-threaded program. Each entry is a string in the format "function_name:action", where action is either "ENTER" or "EXIT". Since the program is single-threaded, calls are perfectly nested.

A "call path" is defined as the sequence of function names currently on the call stack, joined by "/". For example, if the stack is ['main', 'process_data', 'read_file'], the path is "main/process_data/read_file".

Write a function findMostFrequentPath(logs) that returns the call path string that appears most frequently throughout the execution. If multiple paths have the same highest frequency, return the one that first appeared in the logs.

Function Signature

def findMostFrequentPath(logs: List[str]) -> str:

Constraints

  • logs will contain between 1 and 10,000 strings.
  • Function names consist of lowercase letters.
  • The call stack is guaranteed to be valid (every EXIT corresponds to the most recent ENTER).

Examples

Example 1: Input: ["main:ENTER", "funcA:ENTER", "funcA:EXIT", "main:EXIT"] Output: "main" Explanation: The stack states over time are ["main"], ["main", "funcA"], ["main"], []. "main" appears twice, "main/funcA" appears once.

Example 2: Input: ["a:ENTER", "b:ENTER", "b:EXIT", "c:ENTER", "c:EXIT", "a:EXIT"] Output: "a" Explanation: Paths are "a", "a/b", "a", "a/c", "a". "a" appears 3 times.

Hints

Hint 1

Use a stack data structure to maintain the current path of function names.

Hint 2

After every log entry, represent the current stack as a string to track its frequency in a hash map.

Hint 3

Keep track of the insertion order using a separate list or by checking the existence of a key in the hash map to handle tie-breaking.

Follow-up questions

  • How would you optimize the memory usage if the call stack can be very deep?
  • What if the logs were multi-threaded and included thread IDs? How would your data structure change?
  • How would you identify the 'hot path' (the path that consumes the most total time) instead of frequency?