Katkat
Back

Compute exclusive CPU time from nested logs

DecagonSoftware Engineer · Technical Screen
MediumSoftware EngineerTechnical ScreenCoding & Algorithms

Last updated

This question evaluates the ability to interpret execution logs and compute exclusive CPU time, testing skills in parsing structured logs, reasoning about nested execution intervals, and precise time accounting.

You are given logs from a single-threaded CPU that runs n functions (IDs 0 to n-1). Each log entry is a string in the format:

  • "functionId:start:timestamp" or
  • "functionId:end:timestamp"

Rules/semantics:

  • The CPU runs at most one function at a time.
  • A function can call other functions; calls are properly nested (well-formed like a stack).
  • start means the function begins executing at the start of timestamp.
  • end means the function finishes executing at the end of timestamp (inclusive).
  • Timestamps are non-decreasing across the log list.

Task: Return an array ans of length n where ans[i] is the exclusive time spent executing function i (time spent in its own body excluding time spent in functions it calls).

Input:

  • Integer n
  • List of strings logs

Output:

  • Integer array ans

Example:

  • n = 2
  • logs = ["0:start:0","1:start:2","1:end:5","0:end:6"]
  • Output: [3,4]

Constraints (typical interview assumptions):

  • 1 <= n <= 10^5
  • 1 <= logs.length <= 10^5
  • Log format is valid and properly nested.