Compute exclusive times and call stack from logs

Q: Compute exclusive times and call stack from logs

This is a Coding & Algorithms interview question from Anthropic for Software Engineer roles. View the full question and solution on PracHub.

Q: How do I approach Coding & Algorithms interview questions?

Coding & Algorithms questions require understanding of core concepts and practice. PracHub provides solutions with explanations to help you master coding & algorithms interviews.

Question

Design an algorithm that, given a single-threaded program's execution log, computes per-function exclusive durations and reconstructs the active call stack at an arbitrary time. Input: (

integer m = number of function IDs (0..m- 1); (
list logs where each entry is the string "t,event,id" with t as a non-negative integer timestamp in milliseconds, event in {BEGIN, END}, and id in [0..m-1]. The list is sorted by t; for equal t, process END before BEGIN. Each BEGIN has a matching END; calls may nest but the runtime is single-threaded. Also given an integer q representing a query timestamp. Output: (a) durations, a length-m array where durations[i] is the total exclusive time spent running function i (excluding time consumed by its child calls); (b) stack_q, the ordered list of function IDs from bottom to top that are active at time q (empty if none). Implement an O (n) time solution using O(m + call_depth) space, clarify how timestamps are treated (use half-open intervals [start, end)), and explain how you handle ties and edge cases (back-to-back events, nested calls, and q outside any interval).

Compute exclusive times and call stack from logs

Comments (0)