Задача с собеседования в ШАР Яндекса

Даны 2 вектора целых чисел одинаковой длины, заданные в сжатой форме списками пар вида (value, count)
Например, вектор [4, 4, 5] задается как [(4, 2), (5, 1)]

Необходимо посчитать скалярное произведение заданных векторов

Пример:
DotProduct([(1, 3)], [(1, 2), (10, 1)]) -> 12

Решение:
Пройдемся двумя указателями по обоим массивам за линию
Реализация может быть разной, но идея одна и та же - будем их "разворачивать" на лету, одновременно считая ответ

def DotProduct(vec1, vec2):
i = j = 0
count1 = count2 = 0
val1 = val2 = 0
result = 0

while i < len(vec1) and j < len(vec2):
if count1 == 0:
val1, count1 = vec1[i]
i += 1
if count2 == 0:
val2, count2 = vec2[j]
j += 1

k = min(count1, count2)
result += val1 * val2 * k
count1 -= k
count2 -= k

return result

Асимптотика O(N)

@algoses