Вложенный поиск требует O(nm) в худшем случае. С хеш-множеством ожидаемое время O(n+m), если операции поиска и вставки имеют ожидаемую постоянную стоимость.
Время поиска общих пользователей в двух списках
Вложенный поиск требует O(nm) в худшем случае. С хеш-множеством ожидаемое время O(n+m), если операции поиска и вставки имеют ожидаемую постоянную стоимость.
Короткий ответ
Что ответить на собеседовании
Подробный разбор
Ответ с пояснениями
Условие
Нужно найти уникальных пользователей, присутствующих в двух списках длины n и m. Один вариант для каждого элемента первого сканирует второй; другой использует hash set. Сравните время.
Ответ
Вложенный поиск требует O(nm) в худшем случае. С хеш-множеством ожидаемое время O(n+m), если операции поиска и вставки имеют ожидаемую постоянную стоимость.
Удаляйте найденный ID или отдельно учитывайте уже выданные значения, если в списках есть повторы. Для уже отсортированных списков два указателя также дают O(n+m) без хеш-таблицы. Нельзя назвать решение O(n), не определив, что n обозначает суммарный размер обоих входов.