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.

What difficulty level is this interview question?

This is a medium difficulty Coding & Algorithms question, commonly asked during Technical Screen rounds at Meta.

What role is this question designed for?

This question is commonly asked for Machine Learning Engineer candidates at Meta during technical interviews.

Optimize repeated-value vectors and compute exclusive times

Q: 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.)

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.)

Optimize repeated-value vectors and compute exclusive times

Quick Overview

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

Input/Output

Constraints (typical)

Example

Task 2: Compute exclusive execution time from nested logs

Input/Output

Example

Comments (0)

Optimize repeated-value vectors and compute exclusive times

Quick Overview

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

Input/Output

Constraints (typical)

Example

Task 2: Compute exclusive execution time from nested logs

Input/Output

Example

Comments (0)