← Decagon Interview Insights

Decagon·Software Engineer·Technical Phone Screen·Intermediate

IntermediatePrefer not to say
May 2026Remote

Summary

Decagon coding interview, one algorithmic question on function call log parsing. Pretty focused session, no fluff.

Questions Asked (1)

Q1

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

Algorithms & Data Structures
Author's notes

Stack-based solution is the right move here.

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 function starts, push it onto the stack; when it ends, pop it and add the elapsed time to its exclusive time, then adjust the parent's start time to account for the nested call. This ensures exclusive time excludes nested calls.

Pro tip: Clarify whether timestamps are inclusive or exclusive, as this affects the off-by-one calculation. Also, mention that the stack approach naturally handles arbitrary nesting depth and runs in O(n) time.

1. Parse and Initialize

Parse each log entry into function ID, event type (start/end), and timestamp. Initialize an array of size n to store exclusive times and an empty stack to track active functions.

2. Process Start Events

When encountering a start event, if the stack is not empty, add the time elapsed since the parent's start to the parent's exclusive time (to account for time before the child started). Then push the new function onto the stack with its start timestamp.

3. Process End Events

When encountering an end event, pop the function from the stack, compute its exclusive time by adding the duration from its start to the current timestamp (inclusive), and then update the parent's start time to the current timestamp + 1 (if timestamps are inclusive) to avoid double-counting.

4. Handle Timestamp Semantics

Adjust calculations based on whether timestamps are inclusive or exclusive. For inclusive timestamps, duration = end - start + 1; for exclusive, duration = end - start. Ensure consistency throughout.

5. Return Result

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

Key Points to Mention

  • Stack data structure to manage nested function calls
  • Time complexity O(n) and space complexity O(n) for the stack and result array
  • Handling of inclusive vs exclusive timestamps and off-by-one errors
  • Updating parent's start time after a child call ends to correctly attribute time
  • Edge cases: multiple top-level functions, deeply nested calls, and functions with no nested calls
  • Assumption that logs are well-formed and function IDs are 0-indexed

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