Coding questions · Meta

Optimize repeated-value vectors and compute exclusive times

This question evaluates proficiency in data-structure and algorithmic concepts such as run-length encoding for compressed vectors and interval/nesting reasoning for computing exclusive execution times.

You are given two separate coding tasks from an interview.

Task 1: Optimize storage for vectors with repeated values, then compute dot product

You are given integer vectors A and B of the same length n (potentially very large). The vectors often contain long runs of the same value (i.e., many consecutive duplicates).

Design a compressed representation for a vector using run-length encoding (RLE), e.g. represent [-2, -2, -2, 5, 5, 0, 0, 0, 0] as [(-2,3), (5,2), (0,4)].
Using only the compressed representations of A and B (without fully expanding them), compute the dot product:

$A \cdot B = \sum_{i=0}^{n-1} A[i] \times B[i]$

Input/Output

Input: two arrays A and B (or their compressed forms) with the same length.
Output: the dot product as an integer (or 64-bit integer if needed).

Constraints (typical)

1 <= n <= 10^7
Values fit in 32-bit signed integer; the dot product may require 64-bit.
Compression should be significantly smaller than n when there are long runs.

Example

A = [1,1,1,2,2] → [(1,3),(2,2)]
B = [3,3,4,4,4] → [(3,2),(4,3)]
Dot product = 1*3 + 1*3 + 1*4 + 2*4 + 2*4 = 22

Task 2: Compute exclusive execution time from nested logs

You are given n functions labeled 0..n-1 and a list of execution logs. Each log entry is a string:

"<id>:start:<timestamp>" or "<id>:end:<timestamp>"

Rules:

Function calls can be nested (single-threaded CPU).
When a function is running, its time should be counted exclusively, excluding time spent in functions it calls.
Timestamps are integers and are inclusive at end (i.e., an end at time t includes the unit time t).

Input/Output

Input: integer n, array logs of strings.
Output: array ans of length n where ans[i] is the exclusive time of function i.

Example

n = 2
logs = ["0:start:0","1:start:2","1:end:5","0:end:6"]
Output: [3,4]

(Explanation: function 0 runs at times 0–1 and 6 → 3 units; function 1 runs at times 2–5 → 4 units.)

Run-Length Encoded Dot Product

Compute the dot product of two vectors from RLE representations [value,count] without expanding them.

Examples

Example 1

Input: ([(1,3),(2,2)], [(3,2),(4,3)])
Output: 26

Explanation: Prompt example.

Example 2

Input: ([(-2,3),(5,2),(0,4)], [(1,9)])
Output: 4

Explanation: Different run boundaries.

Hints

Choose a representation that makes the requested operation direct.
Handle empty inputs and boundary cases first.

Exclusive Execution Times from Nested Logs

Given n functions and start/end logs with inclusive end timestamps, return exclusive execution time per function.