# Dot Product of Two Vectors (Dense, then Sparse) You are given two integer vectors of the **same length** and must compute their **dot product** — the sum of the element-wise products. For two vectors $a$ and $b$ of length $n$: $$a \cdot b = \sum_{i=0}^{n-1} a_i \cdot b_i$$ ## Part 1 — Dense vectors Implement a function that takes two equal-length integer arrays `a` and `b` and returns their dot product as an integer. **Examples** - `a = [1, 0, 0, 2, 3]`, `b = [0, 3, 0, 4, 0]` -> `1*0 + 0*3 + 0*0 + 2*4 + 3*0 = 8` - `a = [0, 1, 0, 0, 2, 0, 0]`, `b = [1, 0, 0, 0, 3, 0, 4]` -> `0 + 0 + 0 + 0 + 6 + 0 + 0 = 6` - `a = [1, 2, 3]`, `b = [4, 5, 6]` -> `4 + 10 + 18 = 32` ## Part 2 — Sparse vectors (follow-up) In practice the vectors are **very long but mostly zeros** (for example, length $10^7$ with only a few hundred non-zero entries). Storing and iterating over every position wastes time and memory. Represent each vector as a list of `[index, value]` pairs for its **non-zero** entries only, **sorted by index in ascending order**, together with the logical length `n` of the vector. Compute the dot product using only the non-zero entries, so that the running time depends on the number of stored entries rather than on `n`. **Sparse representation example** The dense vector `a = [0, 5, 0, 0, 9]` (length `n = 5`) is represented as `[[1, 5], [4, 9]]`. **Examples (sparse)** - `a = [[1, 5], [4, 9]]`, `b = [[0, 2], [4, 3]]`, `n = 5` (dense `a = [0,5,0,0,9]`, dense `b = [2,0,0,0,3]`) -> only index `4` overlaps -> `9 * 3 = 27` - `a = [[0, 1], [2, 2]]`, `b = [[1, 4], [3, 5]]`, `n = 4` (no shared non-zero index) -> `0` ## Constraints - Both vectors have the same logical length `n`, with `1 <= n <= 10^7`. - Element values fit in a signed 64-bit integer; the dot product is guaranteed to fit in a signed 64-bit integer. - In the sparse representation, indices within a single vector are distinct and sorted ascending, and `0 <= index < n`. - For the sparse case, aim for `O(k_a + k_b)` time and `O(1)` extra space (beyond the inputs), where `k_a` and `k_b` are the numbers of non-zero entries in `a` and `b` respectively. A hash-map lookup approach `O(k_a + k_b)` time with `O(min(k_a, k_b))` extra space is also acceptable; the two-pointer merge over the sorted index lists is the most space-efficient.