Найти пары слов связанных с 4ми и более одинаковыми url?

Question

[mkone112]

Дали задачу на собеседовании.

Есть список из 400 тыс ключевых слов. С каждым словом связано 10 url. Необходимо вывести пары ключевых слов, у которых есть 4 и более одинаковых url, при условии, что во всей массе url:
нет url привязанного ко всем словам;
количество уникальных url составляет 30% от общей массы

У меня нет идей кроме перекрестного сравнения всех слов со всеми, как мне использовать два последних условия вообще не понимаю.

Comments

[Alexandroppolus]

Насколько я понимаю, может быть такие 4 урла, которые связаны со всеми словами, кроме одного. Тогда количество пар будет O(N^2), и мотивации что-то придумывать нет

[Akina]

как мне использовать два последних условия вообще не понимаю.

Это ограничения.
Первое чётко говорит, что не стОит пытаться найти такой URL, исключить его и решать задачу с 3 общими URL.
Второе нужно только для того, чтобы отсечь заведомо более длинный обратный путь решения - не от слов, а от URL-ов.

Answer 1

[Wataru]

Во-первых, я бы с помощью бора все урлы перенумеровал. Теперь в задаче есть 400,000 ключевых слов, связанных с 10-ю числами.

Далее, В каждой группе по 10 чисел есть 10!/4!/6! = 840 четверок. Всего различных четверок наберется 840*400000 ~= 330,000,000. Это не так много. Для хранения всей этой радости, правда, понадобится ~8 гигабайт памяти, но это подъемно. Потом вам надо среди этих 300 миллионов найти совпадающие. Можно отсортировать (лучше радиксом) или воспользоваться хеш таблицей (правда тут еще больше памяти потребуется).

Это будет на много порядков быстрее сравнивания каждого слова с каждым или перебор 4-х урлов.
Все за несколько секунд должно отработать.

Comments

[Wataru]

Борис Алексеев, radix sort. Поразрядная сортировка.

Сложность - да, линейная + сортировка, если считать, что 10 и 4 - константы. Если их в оценку сложности брать, то там экспоненциальная по ним сложность будет.

Answer 2

[imageman]

В входе список слово-URL (длина списка порядка 400k*10=4M элементов).
Сортируем его по URL. Если после сортировки у 4 и более подряд идущих элементов одинаковый URL, то выводим ключевые слова.

Можно без сортировки - через словарь, но сомневаюсь, что будет быстрее (из-за промахов кэша).

Comments

[Wataru]

Это вы урл у четырех и более слов ищите. А надо пары слов, у которых совпадают 4 и более урлов.

[imageman]

Wataru, да, ошибся.

Answer 3

[mayton2019]

Я-бы строил граф. Тогда задача сводится к поиску пар верин имеющих 4х одинаковых соседей.

Впрочем такое ограничение как 10 url дает возможность отобразить граф на матрицу. Хотя чисто эстетически мне граф кажется более наглядным и общим.