Max XOR: выбрать число из первого массива
Даны два массива неотрицательных целых чисел: candidates и queries.
Для каждого числа q из queries нужно выбрать такое число x из candidates, что значение x ^ q максимально.
Верните массив выбранных чисел той же длины, что и queries.
Если candidates пустой, выбросите ValueError.
Сигнатура
def max_xor_choices(candidates: list[int], queries: list[int]) -> list[int]:Решение прямо на странице
Напишите код, запустите проверки и только потом открывайте разбор.
Нажмите «Запустить проверки» или Ctrl+Enter.
Показать разбор
Подсказки
- Opposite bit
Для XOR на текущем бите выгоднее получить 1, поэтому сначала ищите противоположный бит.
- Bit width
Trie нужно строить от старшего значимого бита максимального числа во всех входах.
Идея решения
Брутфорс перебирает все пары и работает за O(n * m). Оптимизация строит битовый бор по candidates.
Чтобы максимизировать x ^ q, на каждом бите выгодно идти в ветку, противоположную биту q. Если такой ветки нет, идем в единственную доступную. В листе хранится исходное число из candidates.
Эталонный код
def max_xor_choices(candidates: list[int], queries: list[int]) -> list[int]:
if not candidates:
raise ValueError('candidates must not be empty')
if any(x < 0 for x in candidates) or any(q < 0 for q in queries):
raise ValueError('only non-negative integers are supported')
bit_width = max(1, max(candidates + queries).bit_length())
root = {'next': {}, 'value': None}
for value in candidates:
node = root
for bit_index in range(bit_width - 1, -1, -1):
bit = (value >> bit_index) & 1
node = node['next'].setdefault(bit, {'next': {}, 'value': None})
if node['value'] is None or value < node['value']:
node['value'] = value
result = []
for query in queries:
node = root
for bit_index in range(bit_width - 1, -1, -1):
bit = (query >> bit_index) & 1
preferred = 1 - bit
if preferred in node['next']:
node = node['next'][preferred]
else:
node = node['next'][bit]
result.append(node['value'])
return resultРаспределение выбранных чисел после max XOR
Как меняется распределение выбранных чисел, если для каждого query выбирать число с максимальным XOR?
Сначала проговорите ответ вслух или тезисами.
Формулы, план решения, риски и примеры.
Откройте разбор только после своей попытки.
Показать разбор
Короткий ответ
Выбор max XOR не сохраняет исходное равномерное распределение выбранных элементов: чаще выбираются числа, которые закрывают старшие биты query противоположными битами.
Подробный разбор
Max XOR жадно старается отличаться от query в старших битах, потому что старший отличающийся бит дает больший вклад в значение XOR. Если массив кандидатов конечный, выбранные элементы смещаются в сторону тех веток trie, где чаще находятся противоположные биты для запросов.
На равномерных независимых 10-bit числах итоговое распределение зависит от размера массивов и покрытия trie. При большом числе кандидатов почти для каждого query найдется близкий bitwise complement, при малом - выбор будет шумным и завязанным на случайные gaps в наборе кандидатов.
Python runtime: mutability, hashability, GIL и GC
Какие базовые runtime-вопросы по Python часто идут после алгоритмической задачи?
Сначала проговорите ответ вслух или тезисами.
Формулы, план решения, риски и примеры.
Откройте разбор только после своей попытки.
Показать разбор
Короткий ответ
Нужно различать mutable/immutable объекты, hashability для dict/set, влияние GIL на CPU-bound threads и роль reference counting плюс cyclic GC.
Подробный разбор
Mutable объекты можно менять на месте, immutable создают новое значение при изменении. Hashable объект должен иметь стабильный hash и корректное equality-поведение, поэтому list/dict/set не подходят как ключи dict, а tuple подходит только если все элементы hashable.
GIL в CPython ограничивает параллельное исполнение Python bytecode потоками, но не отменяет race conditions и полезность threads для I/O. Память в CPython в основном освобождается reference counting, а отдельный cyclic GC нужен для циклов ссылок, которые счетчик сам не разорвет.