Алгоритмы с нуля
Инструментарий решения задач: тренажёр для собеседований
Битовые трюки и манипуляции с матрицей на месте ты понимаешь. Собеседование проверяет, потянешься ли ты за XOR или за «транспонируй-и-разверни» под таймером и объяснишь ли вслух, почему трюк верен.
Реши каждую задачу до того, как откроешь подсказку, уложись в целевое время и проговаривай временную и пространственную сложность так, будто тебя слушает интервьюер. Подсказки нужны, когда ты по-настоящему застрял — они подталкивают к приёму, но не выдают всё решение.
Пять задач из NeetCode-150 на приёмы math-geometry и bit manipulation из этого раздела. Засеки время, реши каждую вхолодную без подсказок, затем проговори вслух временную и пространственную сложность, прежде чем двигаться дальше. Открывай подсказку, только если действительно застрял — подсказки подталкивают, но не выдают ответ.
0/5 решено
math geometry
Follow-up (вслух)
Почему транспонирование с последующим разворотом строк равно повороту по часовой? Что изменится, если нужен поворот против часовой?
Follow-up (вслух)
Где именно ты перепроверяешь границы, чтобы не вывести строку или столбец дважды на неквадратной матрице?
bit manipulation
Follow-up (вслух)
Почему цикл n & (n - 1) — это O(числа единичных бит), а не O(32)? Когда это реально важно?
Follow-up (вслух)
Работают и bits[i >> 1] + (i & 1), и bits[i & (i - 1)] + 1. Объясни, что каждая рекуррента на самом деле говорит о битах i.
Follow-up (вслух)
Почему коммутативность и ассоциативность XOR делают сокращение пар независимым от порядка? А если бы каждый элемент встречался трижды, а не дважды?
Отмечай задачу решённой, только когда сделал её вхолодную, уложился в целевое время и смог назвать сложность без запинки. Вернись через несколько дней и перерешай отмеченные — именно интервальные повторы превращают узнанный приём в рефлекс.