Постройте множество меньшего списка и просмотрите больший. При совпадении добавляйте ID в ответ и удаляйте его из множества, чтобы не повторять результат.
Как уменьшить память поиска лояльных пользователей
Постройте множество меньшего списка и просмотрите больший. При совпадении добавляйте ID в ответ и удаляйте его из множества, чтобы не повторять результат.
Короткий ответ
Что ответить на собеседовании
Подробный разбор
Ответ с пояснениями
Условие
Пользователь лоялен, если был активен хотя бы раз в каждый из двух дней. Даны два больших списка user_id с повторами. Как найти пересечение с меньшей дополнительной памятью?
Ответ
Постройте множество меньшего списка и просмотрите больший. При совпадении добавляйте ID в ответ и удаляйте его из множества, чтобы не повторять результат.
Память без учёта ответа O(min(n,m)), ожидаемое время O(n+m). Если входы уже отсортированы, можно использовать два указателя и постоянную рабочую память, пропуская повторы. Сортировка не бесплатна и может изменить вход, поэтому её стоимость и допустимость нужно оговорить.