Распределение выбранных чисел после max XOR
Как меняется распределение выбранных чисел, если для каждого query выбирать число с максимальным XOR?
Ответить самому
Сначала сформулируйте ответ как на собеседовании, затем откройте разбор и оцените себя.
Короткий ответ
Выбор max XOR не сохраняет исходное равномерное распределение выбранных элементов: чаще выбираются числа, которые закрывают старшие биты query противоположными битами.
Полный разбор
Max XOR жадно старается отличаться от query в старших битах, потому что старший отличающийся бит дает больший вклад в значение XOR. Если массив кандидатов конечный, выбранные элементы смещаются в сторону тех веток trie, где чаще находятся противоположные биты для запросов.
На равномерных независимых 10-bit числах итоговое распределение зависит от размера массивов и покрытия trie. При большом числе кандидатов почти для каждого query найдется близкий bitwise complement, при малом - выбор будет шумным и завязанным на случайные gaps в наборе кандидатов.