← Decagon Interview Insights

Decagon·Software Engineer·Technical Phone Screen·Intermediate

Intermediate
Jun 2026

Summary

Interviewed for a software engineer role at Decagon and got a stack-based simulation problem. Pretty straightforward round, nothing too surprising.

Questions Asked (1)

Q1

Given n functions running on a single-threaded CPU and a list of logs in the format 'function_id:start|end:timestamp', compute the exclusive execution time for each function (meaning time spent in that function itself, not in any functions it called).

Algorithms & Data Structures
Author's notes

Stack simulation problem.

Create a free account to read the full note

AI HintsAI Generated

Suggested Approach

Use a stack to track the call hierarchy, recording each function's start time and accumulating child time. When a function ends, compute its exclusive time as (end - start + 1) minus the total time spent in its children, then add that exclusive time to the function's total and propagate the child time to the parent.

Pro tip: Clarify the timestamp semantics upfront: timestamps are inclusive and represent discrete time units, so duration is end - start + 1. Also, explicitly handle nested calls and ensure the stack correctly manages parent-child relationships to avoid off-by-one errors.

1. Parse and Understand Logs

Parse each log entry into function ID, event type (start/end), and timestamp. Clarify that timestamps are inclusive and represent discrete time units.

2. Initialize Data Structures

Use a stack to maintain the current call stack, and an array to store exclusive times for each function. Optionally, maintain a separate stack for accumulated child time per function.

3. Process Logs Sequentially

For a 'start' event, push the function ID and its start timestamp onto the stack. For an 'end' event, pop the function, compute its exclusive time by subtracting child time from the total duration, update its exclusive time, and propagate the child time to the parent if any.

4. Compute Exclusive Time

When a function ends, calculate total duration as (end_timestamp - start_timestamp + 1). Subtract the sum of exclusive times of all direct children (tracked separately) to get the function's exclusive time.

5. Return Results

After processing all logs, return the array of exclusive times for each function in order of function ID.

Key Points to Mention

  • Use of stack to track call hierarchy and manage nested function calls.
  • Inclusive timestamp handling: duration = end - start + 1.
  • Separate tracking of child time to compute exclusive time correctly.
  • Propagation of child time to parent when a function ends.
  • Time complexity: O(m) where m is number of logs, space complexity: O(n) for stack and result array.
  • Edge cases: nested calls, multiple calls to the same function, and functions with no children.

AI-generated suggestions, not part of the candidate's original notes. May be inaccurate — verify before relying on them.