1ЗадачаMedium
Разность отсортированных списков id
Условие
You have two datasets: a train dataset and a test dataset. Each record is identified by an integer id, so each dataset can be represented as a sorted list of integer ids.
Build a function that takes two integer lists and returns every id from the first list that is not present in the second list.
The context from the interview is data leakage detection between train and test datasets.
Решение прямо на странице
Напишите код, запустите проверки и только потом открывайте разбор.
Проверка решения
Нажмите «Запустить проверки» или Ctrl+Enter.
Показать разбор
Идея решения
Так как оба списка отсортированы, можно идти двумя указателями.
Для каждого элемента first[i] двигаем указатель j по second, пока second[j] < first[i]. Если после этого second[j] != first[i] или второй список закончился, добавляем first[i] в ответ.
Эталонный код
def sorted_diff(first: list[int], second: list[int]) -> list[int]:
result = []
j = 0
for value in first:
while j < len(second) and second[j] < value:
j += 1
if j == len(second) or second[j] != value:
result.append(value)
return resultСложность
Время: O(n + m). Память: O(1).
Два указателя проходят оба списка один раз. Пространство не считает массив ответа.