Decagon·Software Engineer·Technical Phone Screen·Intermediate

Intermediate

May 2026

Summary

Got a stack-based simulation problem at Decagon for a software engineer role. Nothing too wild but it required you to actually think through the execution model carefully.

Questions Asked (1)

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 (i.e. time spent in that function excluding any time spent in functions it called).

Algorithms & Data Structures

Author's notes

The stack approach clicked pretty fast but I kept second-guessing the timestamp math.

Create a free account to read the full note

AI HintsAI Generated

Suggested Approach

Use a stack to track the call hierarchy and compute exclusive times by subtracting child durations from parent durations. Process logs in chronological order, and when a function ends, calculate its exclusive time as (end - start + 1) minus the sum of its children's exclusive times.

Pro tip: Clarify whether timestamps are inclusive or exclusive and whether they represent discrete time units (e.g., milliseconds) to avoid off-by-one errors. Also, mention that the stack approach naturally handles nested calls and is O(n) time and space.

1. Parse and sort logs

Parse each log entry into function ID, event type (start/end), and timestamp. Ensure logs are sorted by timestamp; if not, sort them first.

2. Initialize data structures

Create an array to store exclusive times for each function (size n). Use a stack to keep track of currently executing functions and their start times.

3. Process logs with stack

Iterate through logs: on 'start', push function ID and timestamp onto stack. On 'end', pop the function, compute its exclusive time as (end - start + 1) minus the sum of exclusive times of its children (tracked separately), and add to the result array.

4. Handle nested calls and child times

Maintain a separate stack or variable to accumulate child exclusive times for the current parent. When a child ends, add its exclusive time to the parent's child sum.

5. Return results

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

Key Points to Mention

Use of stack to track call hierarchy and handle nested function calls.
Inclusive vs exclusive timestamps: clarify and adjust calculation accordingly (e.g., add 1 if inclusive).
Time complexity: O(n) where n is number of logs, as each log is processed once.
Space complexity: O(n) for stack and result array.
Handling of multiple calls to the same function: accumulate exclusive times.
Edge cases: empty logs, single function, deeply nested calls.

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