Design a Sparse Vector/Matrix

To design an optimized sparse vector, I would avoid allocating memory for every index since most are zero. Instead, I'd use a hash map mapping indices to their values, or a sorted list if we need ordered traversal. For Stripe's high-throughput environment, a hash map offers O(1) average access for updates and lookups while keeping space proportional to non-zero elements. When calculating the dot product, I iterate through the non-zero entries of the first vector. For each entry, I check if that index exists in the second vector's storage. If it does, I multiply the values and add to the sum. This ensures the operation runs in O(min(n1, n2)) time relative to non-zero elements rather than the full vector length. For example, if Vector A has non-zeros at indices [0, 5] and Vector B at [5, 10], we only compute the product for index 5. This approach prevents wasted computation on zeros, which is crucial when dealing with large-scale transaction logs or feature matrices in distributed systems. I would also consider thread-safety if used concurrently, adding locks or using concurrent maps as needed for production readiness.