Profiler and stack trace coding problems explained

In this article

1. Before you start
2. Why interviewers ask this
3. Profiler stack trace problems from first principles
4. Worked example
5. Trade-offs and edge cases
6. How to answer it in an interview
7. Common mistakes
8. Follow-up questions
9. Sources

Before you start

This page belongs to the industry coding rounds guide, where applied, systems-flavoured problems like this one are collected.

Why interviewers ask this

The problem looks like string parsing and is really a test of one habit: can you keep a stack and attribute time to the right owner? Candidates report versions of it, such as "exclusive running time of functions" and "find the slowest part from profiler samples", in interviews at AI labs and large tech companies.

A weak answer subtracts begin from end for each function and calls the biggest number the winner. That finds the function that contains the most work, which is the outermost call. A strong answer separates exclusive time from inclusive time, uses a stack, and says what happens with recursion and with a trace that stops before a function ends. A Staff-level answer also explains how the same logic applies to stack samples, where there are no begin and end events at all.

Profiler stack trace problems from first principles

Exclusive time

Exclusive time is the time a function spends running its own code, with the time spent inside the functions it called subtracted. Python's profiler output reports it as tottime, the time in the function itself, excluding calls to sub-functions.

Inclusive time

Inclusive time is the time from a function's start to its end, so it includes every function it called. Python's profiler output reports it as cumtime, cumulative time, which covers the function and everything it called.

Sampling profiler

A sampling profiler is a profiler that records the call stack at regular intervals instead of recording every call. Functions that appear on top of the stack in many samples are where the time went.

In plain words

Picture a relay with a baton. Whoever holds the baton is the only runner on the clock. When a runner hands the baton to a helper, the helper's time counts and the runner's pauses. When the helper finishes, the baton returns. The call stack is the pile of paused runners, and the top of the pile holds the baton. The analogy breaks in one place: a function can hand the baton to a copy of itself, which is recursion, and the pile must then hold two entries with the same name.

In one precise sentence: sort the events by time, and each gap between two events belongs to exactly one function, the one on top of the stack during that gap.

Python's built-in profilers are of the kind the problem imitates. The Python documentation says a deterministic profiler "instruments every function call and return", and a deterministic profiler is one that records every call and return event, which is why it gives exact call counts. The input to your problem is that event log.

Step 1: Read the events in time order and keep a stack

Each event has a function name, a timestamp and a kind: b for begin or e for end. Start with an empty stack, an empty dictionary of totals and a variable holding the previous timestamp. Process events in time order; if the log may arrive shuffled, sort by timestamp first with a stable sort, so that events with equal timestamps keep their given order.

Input: one event. Output: an updated stack. This section fixes the convention that matters: a function runs from its begin timestamp up to its end timestamp, so its inclusive time is end minus begin. Some versions of the problem count the end tick as a full tick: an end at t means the function runs through the end of tick t. Under this inclusive-end convention, an end event pays the top frame t - last + 1 and sets last = t + 1, which adds one unit per call. On foo 10 b, bar 20 b, bar 50 e, foo 100 e that gives bar 31 and foo 60.¹ Ask which convention the interviewer wants and say it aloud.

You now have the data structures; the next two steps are the only two things that can happen to them.

Step 2: On a begin event, pay the parent and push the child

When a begin event arrives and the stack is not empty, the function on top has been running since the previous event. Add the gap, the current timestamp minus the previous timestamp, to that function's exclusive total. Then push the new function and remember the current timestamp.

In the example from the diagram, foo begins at 10 and bar begins at 20. At the second event the stack holds foo, so foo is paid the gap of 10 and bar goes on top.¹ Foo is now paused, not finished.

The step names its input (a begin event), what changes (the parent's total and the stack) and its output (the child on top). Nothing here needs a later step to make sense.

Step 3: On an end event, pay the function and pop it

When an end event arrives, the function on top is the one ending, because functions finish in last-in, first-out order. Add the gap since the previous event to its exclusive total, pop it, and remember the current timestamp.

Bar ends at 50, so bar is paid 30, which is 50 minus 20, and bar is popped.¹ The same code path handles every end event; there is no special case for a child or a parent. What you now know: after each event the stack always describes who is running, and the previous timestamp always marks when that began.

1 · Foo begins2 · Bar begins3 · Bar ends4 · Foo endsReplay

Step-by-step description

1. Foo goes on the stack at 10.
2. Foo is paid 10; bar goes on top.
3. Bar is paid 30 and popped.
4. Foo is paid 50 more: 60 in total.

• Foo begins at 10 and bar begins at 20.
• Bar ends at 50, so bar owns 30.
• Foo ends at 100 and owns 60.

Step 4: Close frames that never end

A trace can stop while a function is still on the stack: the program crashed, the trace was cut, or the function loops forever. The stack is not empty after the last event. The clean rule is to close every open frame at the end-of-recording time if the problem gives one (here 100), pay the top frame the remaining gap, and flag those functions as unfinished in the output. If the problem gives no such time, close at the last event's timestamp, which adds nothing more.

Take foo begins at 0, bar begins at 10, bar ends at 30, and the trace ends at 100 with foo still open. Foo is paid 10 before bar and 70 after it, so 80, and bar is paid 20; foo is flagged unfinished.¹ A function that never returns is then reported as the slowest, which is the honest reading: it held the baton for the whole remaining trace. State this as a design choice and offer the alternative of raising an error.

def exclusive_times(events, trace_end=None):
    """events: (name, time, kind) sorted by time; kind is "b" or "e"."""
    stack, totals, last = [], {}, None
    for name, t, kind in events:
        if stack:                      # pay whoever was on top since the last event
            totals[stack[-1]] += t - last
        if kind == "b":
            stack.append(name)
            totals.setdefault(name, 0)
        else:
            stack.pop()                # the ending function is always on top
        last = t
    unfinished = list(stack)
    if stack and trace_end is not None:
        totals[stack[-1]] += trace_end - last
    return totals, unfinished

The loop visits each event once with constant work, so it runs in linear time in the number of events and uses space proportional to the deepest nesting.

Worked example

The first trace is a common version of the problem: foo begins at 10, bar begins at 20, bar ends at 50, foo ends at 100. All timestamps here are illustrative. The code gives bar an exclusive time of 30 and foo an exclusive time of 60.¹ Foo's inclusive time is 90, the whole span from 10 to 100, and subtracting bar's 30 leaves 60, so the two views agree.¹

The recursion row is the one to remember. Foo calls itself: the outer frame runs 0 to 50 and the inner frame 10 to 30. Adding the two interval lengths gives 70, but only 50 time units passed.¹ Charging each gap to the top frame only gives 50, so the stack never double counts.

Samples instead of events

Sometimes the input is not begin and end events but stack samples: the whole stack at each tick. Take ten samples, illustrative, each standing for one time unit. Three show main and parse, one shows main and work, four show main, work and hash, one shows main and work again, and the last shows main alone. Counting the function on top of each sample gives hash 4, parse 3, work 2 and main 1.¹ Counting every sample a function appears in, the inclusive count, gives main 10, work 6, parse 3 and hash 4.¹ So main tops one sample and appears in ten, while hash tops four samples, the most of any function.

Text description of the diagram

• Main tops one sample and appears in ten.
• Hash tops four samples, the most of any function.

Samples convert to events: when the stack changes between two samples, emit an end for each popped function and a begin for each pushed one, at the sample time. Running the same stack algorithm on those events returns the same totals as the top-of-stack count.¹

Trade-offs and edge cases

The central trade-off is which number answers "slowest". Inclusive time answers "which call contains the most work", and a root function wins it. Exclusive time answers "where was the time actually spent". The Python documentation separates the two for the same reason: self time excludes callees, while cumulative time measures "the total cost of calling a function, including its entire call subtree" (Python documentation, accessed October 2026). Report exclusive time to find the hotspot, and inclusive time to see which branch of the program is responsible.

Profilers themselves are imperfect. The Python documentation notes that the profiler modules "are designed to provide an execution profile for a given program, not for benchmarking purposes", because measuring every call adds overhead. A sampling profiler avoids per-call overhead but sees only what its samples catch, so a very short function can be missed.

Text description of the diagram

• Recursion is handled by the stack, one entry per call.
• An open frame is closed at the trace end and flagged.
• An end with no begin is malformed input.

Edge cases: events that arrive unsorted need a stable sort, so the tie order survives; an end event on an empty stack, or one naming a different function than the top, is malformed; raise an error or skip it and say which. Equal timestamps give a gap of zero, so ties cost nothing, but order matters: process an end before a begin at the same time if the problem says one function hands off to another.

Percall time in the Python output is total time divided by the number of calls (cProfile manual, accessed October 2026), a useful extra if the interviewer asks for the slowest per call rather than in total. Related stack-and-structure problems appear in nested list weight sum and in least recently used (LRU) cache implementation; for log-style input see event and log processing problems.

How to answer it in an interview

The spoken structure: reject end minus begin, define exclusive time, describe the stack loop, state the complexity, then name the open-frame rule before you are asked.

Common mistakes

• "I subtract begin from end for each function." (wrong) That is inclusive time, so the root always looks slowest. (right) "I charge each gap to the top of the stack to get exclusive time."
• "Recursion needs a separate counter per name." (wrong) The stack already holds each call separately. (right) "Each frame is its own stack entry, and only the top is paid."
• "A function with no end event is bad input." (wrong) Real traces get cut off. (right) "I close open frames at the trace end and flag them unfinished."
• "I would match each begin to the end with the same name in a dictionary." (wrong) With recursion the same name has several open calls. (right) "I pop the stack; the top frame is the one that ends."

Follow-up questions

How would you handle cycles or an infinite loop?

A cycle in the call graph is just recursion in the trace, and the stack handles it. A true infinite loop produces a begin with no end, so apply the open-frame rule: close it at the trace end, flag it, and report its exclusive time. The profiler cannot tell a slow function from a stuck one; the flag lets a person decide.

How would you account for a long-running function that never returns?

Pay it the time from its last resume to the trace end and mark it unfinished. If it also called children, those children keep their own exclusive time, and the unfinished function owns only the gaps when it was on top.

How do you find the slowest part from profiler samples?

Count the function on top of each sample, the self count, and rank by it. Each sample stands for one sampling interval, so multiply the count by the interval to get time. Use the inclusive count only to see which branch is responsible.

What is the difference between self time and cumulative time?

Self time, which Python names tottime, excludes time in called functions; cumulative time, cumtime, includes the whole call subtree. Exclusive time in this problem equals self time.

What if two events have the same timestamp?

The gap is zero, so no time moves between them. Order still decides who is on the stack afterwards, so process events in the order given, or follow the tie rule the problem states.

Applied problems like this often sit beside design rounds; see low level design interview questions and the CodeSignal in-memory database assessment for neighbouring formats.

Sources

1. The Python profilers: choosing a profiler and understanding profile output — Python Software Foundation (accessed 2026-10-26; page undated), 26 Oct 2026
2. The Python Profilers: cProfile and profile — Python Software Foundation (accessed 2026-10-26; page undated), 26 Oct 2026
3. pstats: statistics for profilers — Python Software Foundation (accessed 2026-10-26; page undated), 26 Oct 2026