## Problem You are given very long integer vectors where **many adjacent elements repeat** (e.g., long runs of the same value). Storing the full array is memory-expensive. ### Task 1. **Design a compact data structure** to store such a vector more efficiently than a raw `int[]`/`vector<int>`. 2. Using your compact representation, implement a method to compute the **dot product** of two vectors `A` and `B` of equal length `n`: \[ A \cdot B = \sum_{i=0}^{n-1} A[i] \times B[i] \] ### Requirements / Constraints - `n` can be very large (e.g., up to \(10^7\) or more), so avoid full decompression when possible. - Values fit in 32-bit signed integers; the dot product may require a 64-bit accumulator. - Your structure should support: - Building from an input array - Iterating through the logical sequence (implicitly) - Computing dot product between two compressed vectors efficiently ### Clarifications to state during interview - Assume “many repeats” primarily means **runs of identical adjacent values** are common. - Vectors are dense (not necessarily sparse / not mostly zeros). ### Deliverables - Describe the data structure and its space complexity. - Describe the dot product algorithm using the compressed form and its time complexity. - Provide key edge cases (e.g., negative values, different run boundaries, overflow concerns).