Здравствуйте, мыщъх, Вы писали:
М>как бы x & (x — 1) проверка на то, что x это степень двойки. если поменять минус на плюс, то получим проверку, что следующее за x число это степень двойки, а сама x это битовая маска из единиц. это в том случае если результат равен нулю. все остальные случаи мы приравниваем к true.
Все же x & (x — 1) — это обнуление младшего единичного бита, как и x & (x + 1) — обнуление группы единичных битов, начинающихся с нулевой позиции. Проверка на степень двойки — уже следствие. Так что Паблик Морозов все верно сказал.
Вообще, основная цель задачек на собеседовании — оценка стиля мышления кандидата: склонен ли он к анализу, умеет ли строить логические умозаключения, последователен ли в решении проблем, его степень ассоциативности. Попутно можно многое узнать о его бекграунде (не все знакомы с простейшими структурами данных, не говоря уже про "большое О") и общем кругозоре. В идеале, для решения должно быть достаточно базовых знаний, а самих решений должно быть несколько (компромиссных), чтобы можно было завязать содержательную беседу. Желательно также, чтобы задача не была слишком известна; например, можно взять что-нибудь из внутреннего проекта и слегка упростить/изменить.
Рассмотрим несколько проблем, упомянутых в соседней ветке.
1. Реверсирование односвязного списка. Задача действительно элементарная, требующая понимания двух вещей — указателей и структуры "односвязный список". Никаких хвостовых рекурсий и прочих выводов знать не требуется, достаточно нарисовать несколько прямоугольников со стрелками (для некоторых нужно две схемы — начальное состояние и промежуточное), после чего решение становится очевидным, а код пишется с картинки. Вполне может выступать для отсеивания полных идиотов, не умеющих рисовать
Впрочем, есть нюансы. Если кандидат выдает решение без схем, то, скорее всего, он его вызубрил. Проверяется предложением объяснить ход мыслей. С другой стороны, кандидат, выдающий решение как у gandjustas скорее всего overqualified, и либо "выпендривается", либо любит усложнять без надобности.
2. Выборка N случайных элементов массива. Тут фильтр серьезнее. Решения на shuffle и сортировке по случайным ключам достаточно очевидны, но появляется возможность поговорить о сложности, требованиях к ГСЧ и пр.
Есть решение "в лоб" — выбирать случайный элемент по одному и проверять не выбран ли он уже. Тут вопросов еще больше
Решение, указанное gandjustas выдать весьма не просто, если не знать его принцип, но после небольшой подсказки (использовать теорию вероятностей) оно находится простейшим мозговым брутфорсом. Однако, для доказательства корректности этого решения базовых знаний тервера может не хватить.
Кода больше, чем в предыдущем случае, и это максимум по объему, что можно требовать написать, имхо.
3. Нахождение максимальной общей подпоследовательности. Имхо, такие вещи спрашивать на собеседовании бесполезно. Человек, знающий о существовании динамического программирования алгоритм сформулирует с высокой вероятностью, не знающий — вряд ли переизобретет велосипед. Кода много, он весьма наворочен, так что возникнут проблемы с проверкой его корректности, в результате времени будет потрачено много, а результатов достигнуто мало.
Нужно помнить, что для проведения подобных собеседований сам интервьюер должен обладать всеми вышеперечисленными качествами и быть готовым самому на время стать собеседуемым, иначе можно сесть в лужу. Например, когда кандидат выдаст неординарное решение. И, чем сложнее задача, тем риски выше.
Также есть вакансии на которые мыслящий работник не нужен (быдлокодерство по разжеванным требованиям). В этом случае задавать задачки — терять время.
