Optimize repeated-value vectors and compute exclusive 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).

1. 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)] .
2. 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.)