How do I practice coding and algorithm questions?

Use PracHub's coding console to write, test, and debug your solutions in Python or JavaScript. View hints, test against sample inputs, and compare with official solutions.

What difficulty level is this coding question?

This is a medium difficulty Coding & Algorithms question, commonly asked during Technical Screen rounds at Meta.

What role is this question designed for?

This question is commonly asked for Software Engineer candidates at Meta during technical interviews.

Compute Exclusive Execution Times | Meta Coding Question

Compute Exclusive Execution Times

Company: Meta

Role: Software Engineer

Category: Coding & Algorithms

Difficulty: medium

Interview Round: Technical Screen

You are given `n` functions labeled from `0` to `n - 1` and a chronological list of execution logs from a single-threaded CPU. Each log has the format: ```text function_id:start_or_end:timestamp ``` - `function_id` is an integer ID in `[0, n - 1]`. - `start_or_end` is either `start` or `end`. - `timestamp` is a non-negative integer. - A `start` log means the function begins executing at the beginning of that timestamp. - An `end` log means the function finishes executing at the end of that timestamp. - Function calls may be nested. When a function calls another function, the caller is paused until the callee finishes. Return an integer array `result` of length `n`, where `result[i]` is the total amount of time function `i` spent actively executing, excluding time spent inside functions it called. Example: ```text Input: n = 2 logs = [ "0:start:0", "1:start:2", "1:end:5", "0:end:6" ] Output: [3, 4] ``` Explanation: - Function `0` runs from time `0` to `1`, contributing `2` units. - Function `1` runs from time `2` to `5`, contributing `4` units. - Function `0` resumes at time `6` and ends at time `6`, contributing `1` more unit. - Therefore, function `0` has exclusive time `3`, and function `1` has exclusive time `4`.

Quick Answer: This question evaluates understanding of nested function execution and precise exclusive-time accounting derived from chronological logs, emphasizing event parsing and maintenance of execution state.

You are given n functions labeled from 0 to n - 1 and a chronological list of execution logs from a single-threaded CPU. Each log has the format "function_id:start_or_end:timestamp". A start log means the function begins executing at the beginning of that timestamp, and an end log means the function finishes executing at the end of that timestamp. Function calls may be nested; when one function calls another, the caller is paused until the callee finishes. Return an integer array result of length n where result[i] is the total time function i spent actively executing, excluding time spent inside functions it called.

Constraints

1 <= n <= 100
2 <= len(logs) <= 200000
0 <= function_id < n
0 <= timestamp <= 1000000000
logs are in chronological order and form a valid execution trace
Every start log has a matching end log

Examples

Input: (2, ["0:start:0", "1:start:2", "1:end:5", "0:end:6"])

Expected Output: [3, 4]

Explanation: Function 0 runs from time 0 to 1 for 2 units, pauses while function 1 runs from 2 to 5 for 4 units, then resumes at time 6 for 1 unit. The result is [3, 4].

Input: (1, ["0:start:0", "0:end:0"])

Expected Output: [1]

Explanation: The only function starts and ends at timestamp 0. Since end timestamps are inclusive, it runs for 1 unit.

Input: (2, ["0:start:0", "0:end:1", "1:start:2", "1:end:3"])

Expected Output: [2, 2]

Explanation: There is no nesting. Function 0 runs from 0 to 1 for 2 units, and function 1 runs from 2 to 3 for 2 units.

Input: (2, ["0:start:0", "0:start:2", "0:end:5", "1:start:6", "1:end:6", "0:end:7"])

Expected Output: [7, 1]

Explanation: Function 0 has an outer call and a nested call with the same ID. Its total exclusive time is 2 units before the nested call, 4 units for the nested same-ID call, and 1 unit at timestamp 7. Function 1 runs for 1 unit at timestamp 6.

Input: (3, ["0:start:0", "1:start:2", "1:end:3", "2:start:4", "2:end:7", "0:end:8"])

Expected Output: [3, 2, 4]

Explanation: Function 0 runs at times 0, 1, and 8 for 3 total units. Function 1 runs from 2 to 3 for 2 units. Function 2 runs from 4 to 7 for 4 units.

Hints

Use a stack to keep track of which function is currently running.
Track the previous timestamp. On a start log, the current running function has executed until just before the new timestamp. On an end log, remember that the ending timestamp is inclusive.

Quick Overview

This question evaluates understanding of nested function execution and precise exclusive-time accounting derived from chronological logs, emphasizing event parsing and maintenance of execution state.