Decagon·Software Engineer·Technical Phone Screen·Intermediate

Intermediate

Apr 2026

Summary

Got a coding question from Decagon that was pretty squarely in the stack-based simulation category. Nothing about the format stood out, felt like a standard technical screen.

Questions Asked (1)

Given logs of function calls on a single-threaded CPU, each formatted as function_id:start|end:timestamp, compute the exclusive time for each function (time the function itself ran, excluding any time spent inside nested calls). Return an array of length n with the exclusive time for each function ID.

Algorithms & Data Structures

Author's notes

The stack approach clicked for me pretty quickly but I fumbled the timestamp math at first.

Create a free account to read the full note

AI HintsAI Generated

Suggested Approach

Use a stack to track the currently executing function and its start time. When a new function starts, add the elapsed time since the previous start to the previous function's exclusive time, then push the new function. When a function ends, add the elapsed time to its exclusive time and pop the stack, updating the start time for the next function on the stack.

Pro tip: Clarify whether timestamps are inclusive or exclusive, and handle the end timestamp carefully by adding 1 if the end is inclusive. Also, consider edge cases like nested calls and ensure the stack is empty at the end.

1. Parse the logs

Split each log entry into function ID, event type (start/end), and timestamp. Convert the timestamp to an integer.

2. Initialize data structures

Create an array of size n to store exclusive times, initialized to 0. Use a stack to keep track of function IDs and their start times.

3. Process each log entry

For a start event: if the stack is not empty, add the time elapsed since the top function's start to its exclusive time. Then push the new function ID and its start time. For an end event: pop the function, add the elapsed time (including the end timestamp) to its exclusive time, and if the stack is not empty, update the start time of the new top function to the current timestamp + 1.

4. Return the result

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

Key Points to Mention

Use of stack to simulate the call stack on a single-threaded CPU.
Handling of nested function calls and ensuring time is attributed correctly.
Time complexity: O(m) where m is the number of log entries, and space complexity: O(n) for the result and O(d) for the stack where d is the maximum depth of nested calls.
Edge cases: multiple nested calls, functions with no nested calls, and ensuring the stack is empty at the end.
Inclusive vs exclusive timestamps: if the end timestamp is inclusive, add 1 to the duration.
Updating the start time of the parent function after a child function ends to avoid double-counting.

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