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

Даны два массива, состоящих из элементов типа (id, val), отсортированных по неубыванию id Нужно их объединить в один массив, удовлетворяющий следующим условиям
1) В итоговом массиве каждый id входит ровно один раз и элементы массива отсортированы по неубыванию id
2) val, имеющие одинаковые id, суммируются и их сумма будет в итоговом массиве под тем же id

Требуется решение с линейной скоростью и константной памятью

Наш чат алгоритмистов

Решение:
Пройдемся по обоим массивам параллельно, поддерживая текущий айдишник и сумму для него

def merge_sum_list(a: List[Pair], b: List[Pair]) -> List[Pair]:
i = 0
j = 0
na = len(a)
nb = len(b)

res: List[Pair] = []
cur_id: Optional[int] = None
cur_sum: float = 0.0

while i < na or j < nb:
if i < na and (j >= nb or a[i][0] < b[j][0]):
next_id, next_val = a[i]
i += 1
else:
next_id, next_val = b[j]
j += 1

if cur_id is None:
cur_id = next_id
cur_sum = next_val
elif next_id == cur_id:
cur_sum += next_val
else:
res.append((cur_id, cur_sum))
cur_id = next_id
cur_sum = next_val

if cur_id is not None:
res.append((cur_id, cur_sum))

return res

@algoses