← 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 classic stack-based CPU scheduling problem. Pretty straightforward if you've seen this type before, but the edge cases around nested calls can trip you up if you're not careful.

Questions Asked (1)

Q1

Given a list of log strings representing function start and end events on a single-threaded CPU, compute the exclusive execution time for each function (i.e., time spent running but not inside a nested call).

Algorithms & Data Structures
Author's notes

I knew immediately this was a stack problem but fumbled the timestamp arithmetic for a bit.

Create a free account to read the full note

AI HintsAI Generated

Suggested Approach

Use a stack to track active functions and a variable for the current timestamp. When a function starts, push its ID and start time; when it ends, compute its total elapsed time, subtract the exclusive time of any nested calls, and add the result to the output. This approach handles nesting and ensures exclusive time is correctly calculated.

Pro tip: Clarify the log format and whether timestamps are inclusive or exclusive before coding. Mention that you'll handle edge cases like multiple nested calls and ensure the stack is empty at the end.

1. Parse the logs

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

2. Initialize data structures

Create a stack to store active function calls (each entry holds function ID and start time) and a dictionary or list to accumulate exclusive times per function.

3. Process events with a stack

For a start event, push the function ID and timestamp onto the stack. For an end event, pop the top entry, compute the total elapsed time, subtract the exclusive time of any nested calls (tracked separately), and add the result to the function's exclusive time.

4. Handle nested calls

When a nested function ends, its exclusive time is added to its own record and also subtracted from the parent's total elapsed time. This can be done by maintaining a separate variable for the current function's exclusive time or by adjusting the parent's start time.

5. Return results

After processing all logs, return the exclusive times for each function in the order they first appeared or as specified.

Key Points to Mention

  • Stack data structure for managing nested function calls
  • Time complexity: O(n) where n is the number of log entries
  • Space complexity: O(m) where m is the maximum nesting depth
  • Handling of inclusive vs exclusive timestamps (e.g., if end time is inclusive, add 1 to elapsed time)
  • Edge cases: multiple nested calls, functions with no nested calls, and ensuring all start events have matching end events
  • Using a dictionary to map function IDs to their exclusive times for efficient updates

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