Facebook | Representation and dot product of two vectors
7684

Question:
https://leetcode.com/problems/product-of-two-run-length-encoded-arrays/ (premium)

Given the following vectors (arbitrary numbers), design a more memory-efficient representation of these vectors.

A: [1, 1, 4, 4, 4, 4, 7, 7, 7, 7, 7, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2]
B: [2, 2, 5, 5, 5, 5, 5, 5, 5, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3]

Follow-up:
With the vectors represented as suggested, write a function to calculate the dot product of two vectors.

Example:

Input:
A: [1, 1, 4, 4, 4, 4, 7, 7, 7, 7, 7, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2]
B: [2, 2, 5, 5, 5, 5, 5, 5, 5, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3]

Output: 291

Explanation: 1 * 2 + 1 * 2 + 4 * 5 + ... + 2 * 3

Additional information:

  • The vectors are guaranteed to contain a large number of duplicate values, similar to the example given above.
Comments (13)