import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

import static org.assertj.core.api.Assertions.assertThat;

public class SparseVectorDoctProduct {
    public int vectorDotProduct(List<Integer> list1, List<Integer> list2) {
        if(list1 == null || list1.size() == 0 || list2 == null || list2.size() == 0) {
            return 0;
        }
        int sum = 0;
        List<int[][]> index1 = new ArrayList<>();
        List<int[][]> index2 = new ArrayList<>();
        for(int i = 0; i < list1.size(); i++) {
            if(list1.get(i) != 0) {
                index1.add(new int[][]{{i, list1.get(i)}});
            }
            if(list2.get(i) != 0) {
                index2.add(new int[][]{{i, list2.get(i)}});
            }
        }
        int ptr1 = 0, ptr2 = 0;
        while(ptr1 < index1.size() && ptr2 < index2.size()) {
            if(index1.get(ptr1)[0][0] == index2.get(ptr2)[0][0]) {
                sum += index1.get(ptr1++)[0][1] * index2.get(ptr2++)[0][1];
            } else if(index1.get(ptr1)[0][0] < index2.get(ptr2)[0][0]) {
                ptr1++;
            } else {
                ptr2++;
            }
        }
        return sum;
    }

    public void test() {
        List<Integer> list1 = new ArrayList<>(Arrays.asList(1, 2, 3));
        List<Integer> list2 = new ArrayList<>(Arrays.asList(5, 6, 7));
        assertThat(vectorDotProduct(list1, list2)).isEqualTo(38);

        List<Integer> list3 = new ArrayList<>(Arrays.asList(0, 1, 0));
        assertThat(vectorDotProduct(list1, list3)).isEqualTo(2);

        List<Integer> list4 = new ArrayList<>(Arrays.asList(1,2,3,4,5,6,7,8,9,10));
        List<Integer> list5 = new ArrayList<>(Arrays.asList(0,0,0,0,0,1,2,0,0,0));
        assertThat(vectorDotProduct(list4, list5)).isEqualTo(20);
    }

    public static void main(String[] args) {
        SparseVectorDoctProduct o = new SparseVectorDoctProduct();
        o.test();
    }
}