Design compressed vector and compute dot product

Compressed Vector Dot Product

Many real-world vectors are sparse or contain long sequences of identical values. Instead of storing a full array of size N, we can represent a vector as a list of pairs (value, count), where count is the number of times value repeats consecutively.

Task

Design a class CompressedVector that stores a vector in this format. Then, implement a method dot_product(vec1, vec2) that computes the dot product of two CompressedVector objects.

Interface

class CompressedVector:
    def __init__(self, data: list[tuple[int, int]]):
        # data is a list of (value, count) pairs
        self.data = data

def dot_product(vec1: CompressedVector, vec2: CompressedVector) -> int:
    # Returns the dot product of the two vectors

Constraints

• Each vector may contain up to 10^6 elements, but the number of (value, count) pairs is significantly smaller (e.g., 10^3).
• Values are integers.
• Ensure your solution handles cases where the runs in vec1 and vec2 have different boundaries.

Examples

Example 1:

• vec1: [(1, 2), (3, 1)] (represents [1, 1, 3])
• vec2: [(2, 1), (1, 2)] (represents [2, 1, 1])
• Result: (1*2) + (1*1) + (3*1) = 6

Example 2:

• vec1: [(5, 10)] (represents 10 fives)
• vec2: [(2, 5), (3, 5)] (represents 5 twos followed by 5 threes)
• Result: (5*2)*5 + (5*3)*5 = 50 + 75 = 125