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/
Quick Answer: 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
Solution
def exclusive_time(n: int, logs: list[str]) -> list[int]:
ans = [0] * n
stack = [] # stack of function ids
prev = 0 # previous timestamp marker
for entry in logs:
fid_str, typ, t_str = entry.split(":")
fid = int(fid_str)
t = int(t_str)
if typ == "start":
if stack:
ans[stack[-1]] += t - prev
stack.append(fid)
prev = t
else: # "end"
last = stack.pop()
ans[last] += t - prev + 1
prev = t + 1
return ans
Explanation
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).
Hints
- Use a stack to track the active function ids.
- Keep a variable prev to mark the start of the current uninterrupted interval.
- On a start at time t, add t - prev to the current top function before pushing the new one, then set prev = t.
- On an end at time t, pop and add t - prev + 1 to that function, then set prev = t + 1.