Quick Overview

This set evaluates algorithmic problem-solving and mastery of core data structures and algorithms, covering function execution tracking, interval overlap and resource allocation, vertical-order tree traversal, and selection for kth-order statistics.

Solve 4 LeetCode algorithm problems

Company: Meta

Role: Software Engineer

Category: Coding & Algorithms

Difficulty: medium

Interview Round: Onsite

##### Question LeetCode 636. Exclusive Time of Functions LeetCode 253. Meeting Rooms II LeetCode 314. Binary Tree Vertical Order Traversal LeetCode 215. Kth Largest Element in an Array https://leetcode.com/problems/exclusive-time-of-functions/description/ https://leetcode.com/problems/meeting-rooms-ii/description/ https://leetcode.com/problems/binary-tree-vertical-order-traversal/description/ https://leetcode.com/problems/kth-largest-element-in-an-array/description/

Overview: This set evaluates algorithmic problem-solving and mastery of core data structures and algorithms, covering function execution tracking, interval overlap and resource allocation, vertical-order tree traversal, and selection for kth-order statistics.

Given n functions labeled 0..n-1 and a list of log entries describing start and end times of function calls on a single-threaded CPU, compute the exclusive execution time for each function. Each log entry is a string "function_id:type:timestamp", where type is "start" or "end". A "start" entry at time t means the function begins at the start of time t. An "end" entry at time t means the function ends at the end of time t (inclusive). Logs are in chronological order and properly nested (well-formed). Return an array ans of length n where ans[i] is the total time spent executing function i excluding time spent in functions it calls (including recursive calls).

Constraints

  • 1 <= n <= 10^4
  • 1 <= len(logs) <= 10^5
  • 0 <= function_id < n
  • 0 <= timestamp <= 10^9
  • logs are in chronological order
  • each start has a corresponding end; calls are properly nested
  • single-threaded execution; at most one function runs at any time

Hints

  1. Use a stack to track the active function ids.
  2. Keep a variable prev to mark the start of the current uninterrupted interval.
  3. On a start at time t, add t - prev to the current top function before pushing the new one, then set prev = t.
  4. On an end at time t, pop and add t - prev + 1 to that function, then set prev = t + 1.

Loading coding console...

Show the approach

Approach

Maintain a stack of active function ids and a pointer prev to the start of the currently running time segment. When a new function starts at time t, the function on top of the stack was running exclusively from prev to t-1, so attribute t - prev to it, then push the new function and set prev to t. When the current function ends at time t, attribute t - prev + 1 to it (end is inclusive), pop it, and set prev to t + 1 to mark the next free time unit. This correctly accumulates exclusive times while respecting nested calls and recursion.

Time complexity:
O(len(logs))
Space complexity:
O(n + depth_of_call_stack)