Exclusive Function Time
Updated
Problem statement
A single-threaded program has n functions numbered from 0 to n - 1. You are given chronological event strings in logs, each formatted as id:start:timestamp or id:end:timestamp.
- A start event begins a call at the beginning of that integer time unit. If another call is running, it is suspended.
- An end event finishes the currently running call at the end of that time unit. Its suspended caller, if any, resumes at the next time unit.
- Calls are properly nested and every start has a matching end. A function may call itself recursively or be called multiple times.
- Only the innermost active call executes. Time when no call is active is idle and belongs to no function.
Return an array of length n whose entry i is the total number of time units spent executing function i, excluding time spent in its child calls. Accumulate all calls of the same function. A function that is never called has exclusive time 0.
Function
exclusiveTime(n: int, logs: List<String>) → int[]Examples
Example 1
n = 2logs = ["0:start:0","1:start:2","1:end:5","0:end:6"]return = [3,4]Function 0 runs at times 0, 1, and 6. Function 1 runs from 2 through 5, inclusive.
Example 2
n = 1logs = ["0:start:0","0:start:2","0:end:3","0:end:5"]return = [6]Both nested calls belong to function 0, which executes for all six time units from 0 through 5.
Example 3
n = 2logs = ["1:start:5","1:end:5"]return = [0,1]Function 1 executes for exactly one time unit. Function 0 is never called, and earlier idle time is not counted.
Constraints
1 <= n <= 100.0 <= logs.length <= 20000.- Each log uses exactly the described format with
0 <= id < nand0 <= timestamp <= 1000000000. - The log is a valid chronological single-thread execution. Every end matches the top active call, and no call remains active after the final event.
- Multiple starts may share a timestamp. After an end at time
t, the next event has timestamp at leastt + 1. - Every answer fits in a signed
32-bit integer.
More Illumio interview questions
Similar questions at other companies
- Asteroid CollisionSiemens · PHONE SCREEN
- Billing Log with Undo and RedoReddit · PHONE SCREENReddit interview questions
- Compress Editor Actions into Operational Transform OperationsReplit · OA · PHONE SCREEN · ONSITE INTERVIEW
- Adjacent Pair and Run RemovalWhatNot · PHONE SCREENWhatNot interview questions
- Multiline Text Editor with Cursor MovementDatologyAI · PHONE SCREEN
- Run a Stack Language InterpreterJane Street · PHONE SCREENJane Street interview questions
- Trace Nested Object Destruction OrderArista Networks · PHONE SCREENArista Networks interview questions
- Recipe Cart with Undo and RedoDecagon · PHONE SCREENDecagon interview questions
- Layer History with Batch Undo and RedoFigma · OA · PHONE SCREENFigma interview questions
- Convert Stack Samples to Trace EventsAnthropic · PHONE SCREEN · ONSITE INTERVIEWAnthropic interview questions