Katkat
Back

Find the Slowest Function from Profiler Events

AnthropicSoftware Engineer · Onsite
MediumSoftware EngineerOnsiteCoding & Algorithms

Last updated

This question evaluates the ability to interpret time-ordered profiler event logs, compute inclusive and exclusive function runtimes, reason about call-stack semantics, and recognize anomalies such as recursion, cycles, missing end events, or non-returning functions.

You are given a time-ordered profiler event log for a single-threaded program. Each event is one of:

  • START functionName timestamp: execution enters functionName at timestamp.
  • END functionName timestamp: execution exits functionName at timestamp.

Function calls are properly nested like a call stack, except the input may also contain malformed traces such as recursion, cycles in a call graph, missing END events, or a function that appears to run forever.

Design and implement an algorithm that:

  1. Computes the total inclusive running time for each function.
  2. Computes the total exclusive running time for each function, excluding time spent in child calls.
  3. Returns the slowest function by exclusive time. If there is a tie, return all tied functions or define a deterministic tie-breaker.
  4. Explains how your implementation would detect and handle:
  • recursive calls,
  • cycles in the observed call graph,
  • missing end events,
  • an infinite loop or a function that never returns.

Example input:

START a 0
START b 2
END b 5
START c 6
END c 10
END a 12

For this trace, a has inclusive time 12, while its exclusive time excludes the time spent in b and c. The expected output should identify the function with the largest exclusive time and report the computed timing table.