Question
Design a compact representation for an integer vector that contains long runs of repeated values, then compute the dot product of two vectors stored in that representation without expanding either vector. Use run-length encoding: each vector is a sequence of `(value, run_length)` pairs. Implement: ```python def dot_product(a: list[tuple[int, int]], b: list[tuple[int, int]]) -> int: ... ``` The two vectors must describe the same logical length. Return `0` for two empty vectors and raise `ValueError` when their expanded lengths differ. Run lengths are positive integers. Your solution should run in `O(len(a) + len(b))` time and use `O(1)` auxiliary space beyond iterator state. ## Staged follow-ups 1. Explain when run-length encoding is preferable to a sparse `(index, value)` representation. 2. Adapt the design for vectors whose default value is zero and whose nonzero entries are rare. 3. Generalize the two-pointer walk to emit intersections of encoded ranges.