Задачи с собеседований - логические

Часто собеседования начинают не с основ языка Java или программирования в целом, а с логической задачи, напрямую никак не связанной с написанием кода и, тем более, с конкретным языком программирования. Как правило цель такой задачи - узнать, как человек рассуждает, попадает ли он в тупик, как реагирует на подсказки и доводит решение до конца. Я приведу здесь подборку популярных задач, с некоторыми дополнениями, чтобы не получалось простое повторение того, что уже есть в тысяче и одном другом источнике в сети. Советую, конечно же, сначала попробовать решить самостоятельно. С основами алгоритмической сложности можно ознакомиться в другом посте.

Задача про поезд

Формулировка задачи: Есть поезд, состоящий из некоторого количества вагонов. Вы находитесь в одном из них. Вагоны поезда сцеплены в кольцо и можно переходить только в соседний вагон, выходить из поезда нельзя. В каждом вагоне есть лампочка, которую вы можете включать и выключать. Начальное состояние ламп неизвестно. Больше ничего в вагоне делать нельзя. Ваша задача заключается в том, чтобы определить количество вагонов в поезде. Опишите алгоритм решения этой задачи. Дополнительно: Какова алгоритмическая сложность такого решения? Какую сложность имеет оптимальное решение?

Решение. Понятно, что если идти в одну сторону, то мы никогда не сможем сказать, вернулись мы в первый вагон или нет. Нельзя закодировать начало поезда каким-то набором включенных или выключенных ламп, ведь любая последовательность может встретиться в других вагонах поезда. Единственная достоверная механика решения - включить лампу, пройти N вагонов в одну сторону, выключая все лампы, а потом вернуться на N вагонов назад. Если лампа оказалась выключена - значит выключая лампы мы прошли по кругу, иначе - точно нет. Пользуясь такой механикой получаем простое решение - идти в одну сторону на 1, 2, 3 и т.д. вагона, включая лампу в первом и выключая во всех последующих, возвращаться назад и как только свет окажется выключенным - значит мы нашли число вагонов в поезде.

Давайте посчитаем, сколько действий нам потребуется при условии, что в поезде N вагонов. Действием считаем переход из одного вагона в другой, а включения и выключения ламп не считаем. В любом случае манипуляции с освещением у нас производятся не чаще переходов. На каждой итерации алгоритма мы продвигаемся на f(k) = k вагонов в вперёд и назад, пока k не станет равным N. То есть 2 * k действий на каждой итерации. Общее количество действий будет равно сумме арифметической прогрессии:

    F(N) = 2 * ( 1 + 2 + 3 + ... + N) = 2 * N ( N - 1 ) / 2 = O (N^2)
    

Итак, сложность нашего решения квадратичная. На вскидку кажется, что можно улучшить. Очевидно, что лучше линейной, то есть O(N) достичь не получится, ведь уж по одному-то разу в каждый вагон зайти придётся.

В подобных алгоритмических задачах существует общий приём - если что-то увеличивается на один на каждой итерации, то можно попробовать вместо этого удваивать. Тогда решение будет выглядеть так: делаем то же самое, но на каждом шаге выключаем свет не в k вагонах, а в 2^k. То есть последовательность будет выглядеть так: 1, 2, 4, 8, ..., 2^k. Когда на очередной итерации свет в первом вагоне окажется выключенным, то значит, что 2^k >= N, при этом 2^(k-1) < N, потому что на предыдущей итерации мы не прошли полный круг по вагонам. Осталось сделать одну дополнительную итерацию. Мы знаем, что теперь свет во всех вагонах выключен, так что просто включаем свет в первом и идём в любую сторону, пока не встретим включённую лампу.

Оценим алгоритмическую сложность изменённого решения.

    Если k - номер последней итерации, то 2^(k-1) < N <= 2^k, следовательно,
    k ~= [log2(N)] + 1
    На каждой итерации i количество действий равно 2 * 2^i, то есть общее количество равно
    F(N) = 2 * (1 + 2 + ... + 2 ^ ([log2(N)] + 1)) = 2 * ( 1 + 2 + ... + M),
         где M - ближайшая к N степень двойки сверху, то есть N <= M < 2 * N
    Применяя формулу нахождения суммы геометрической последовательности, получаем, что выражение в скобках равно
    1 * (2^k - 1) / (2 - 1) = 2 * M - 1 < 4 * N
    

Хорошо, но почему именно удвоение? Честно говоря, не знаю точно. Увеличение не на константу, а на множитель применяется, например, в ArrayList при необходимости расширить границы массива. Но там множитель 1.5. Деревья поиска чаще используются бинарные. Если в решении мы изменим множитель, например, на 3, то порядок решения останется тем же, изменится только основание логарифма.

Задача про колонну мудрецов в колпаках

Формулировка задачи. N мудрецов приговорили к расстрелу. На рассвете мудрецов построят в колонну по одному и каждому оденут колпак чёрного или белого цвета. Каждый мудрец видит цвета колпаков всех впереди стоящих, но не видит цвета своего колпака. Начиная с последнего, каждый должен назвать цвет своего колпака и, если ответит правильно, то избежит казни. Говорить не в свою очередь или использовать любые другие способы общения запрещено. Нельзя называть ничего кроме цвета: "чёрный" или "белый". Ночью мудрецы могут обговорить стратегию вместе. Предложите стратегию, чтобы спасти максимальное количество мудрецов.

Решение. Давайте придумаем несколько простых стратегий. Например, каждый мудрец называет цвет колпака на впереди стоящем, а тот в свою очередь, повторяет, и спасается. Такая стратегия точно спасает половину мудрецов плюс несколько удачливых мудрецов, у которых цвет совпал с соседом спереди. Но нам важно только количество гарантированное спасённых мудрецов (худший случай работы стратегии), а это лишь половина.

Можно перейти от колпаков к битам. 0 - чёрный, 1 - белый. Тогда мудрецы, стоящие в конце могут попробовать закодировать последовательность бит, соответствующую тем, кто стоит в начале колонны. Мы бы тогда получили результат лучший, чем половина, если бы удалось добиться какого-то сжатия, например, трети последовательности было бы достаточно для того, чтобы закодировать другие две трети. Хорошей степенью сжатия обладают алгоритмы архивирования текстов, видео, изображений, но в них последовательности бит не случайна, там много повторяющихся и "лишних" данных, которые можно закодировать более оптимально. У нас же последовательность случайна и таким образом мы получим те же 50% спасённых мудрецов.

Промежуточное решение, которое бы сохранило треть или логарифм от мудрецов, придумать не получается, поэтому перехожу к оптимальному.

Заменяем понятия чёрного и белого на биты 0 и 1. Тогда мудрецы, стоящие в колонне, представляют собой произвольную последовательность бит длины N. Суть решения в использовании суммы по модулю два и контроле чётности, суммируя биты перед собой с битами, названными другими мудрецами.

    Мудрецы:
     № 1 2 3 4 5 6 7 8 9 10
       1 0 1 0 0 0 0 1 1 1
    Мудрец под номером 1 - первый бит в последовательности. Он считает чётность всех впереди стоящих,
        суммируя элементы последовательности по модулю 2 (кроме себя, потому что он ему не известен):
    v1 = 0 ⊕ 1 ⊕ 0 ⊕ 0 ⊕ 0 ⊕ 1 ⊕ 1 ⊕ 1 = 1, потом он называет результат
    Мудрец под номером два суммирует всех перед собой:
    v2 =      1 ⊕ 0 ⊕ 0 ⊕ 0 ⊕ 1 ⊕ 1 ⊕ 1 = 1, кроме этого он знает, что сказал мудрец под номером 1,
                                                  и тогда он может точно определить свой бит по простой формуле:
    h2 = v1 ⊕ v2 = 0, то есть на нём колпак чёрного цвета, о чем он сообщает и спасается.
    Мудрец под номером три знает:
    v3 =           0 ⊕ 0 ⊕ 0 ⊕ 1 ⊕ 1 ⊕ 1 = 0
    h3 = v1 ⊕ h2 ⊕ v3 = 1 ⊕ 0 ⊕ 0 = 1, то есть на нём колпак белого цвета, о чем он сообщает и спасается.
    Так поступают все следующие мудрецы: суммируют биты перед собой и ответы всех предыдущих мудрецов,
        ведь все слышат ответы других и могут их запомнить (они же мудрецы).
    Для крайнего можно считать, что vN = 0, хотя перед ним и никого нет.
    

    Если bi - бит мудреца под номером i, а
         S - сумма всех bi при i от одного до N, то
         bi = S ⊕ b1 ⊕ b2 ⊕ ... ⊕ b_(i-1) ⊕ b_(i+1) ⊕ ... ⊕ bN,  так как bj ⊕ bj = 0 для любого j.
    

Задача про мышей и вино

Формулировка задачи. Есть 1000 бутылок вина, в одну из которых оказался добавлен сильный яд, и всего 10 лабораторных мышей. Яд убивает мышь за 1 день (точность срока действия яда не позволяет отсчитывать дробное количество дней). За какое наименьшее количество дней можно с помощью этих мышей вычислить отравленную бутылку? Содержимое бутылок можно смешивать, и любое количество яда гарантированно убивает мышь.

Решение. Сразу предложим несколько очевидных решений. Первое - берем одну мышь и даём её вино из бутылок по очереди. Максимум за 1000 дней определяем отравленную. Девять мышей остались без дела, можно улучшить решение - каждой даём вино из 100 бутылок по очереди. Определяем отравленную за 100 дней. Всё ещё очень много. Что если смешать по 100 бутылок вида в пробирке для каждой мыши? Тогда после первого дня останется 9 мышей, но мы будем знать, что яд в одной из 100 бутылок. На второй день смешаем по 10 бутылок, дадим девяти мышам, при этом 10 бутылок оставим. Тогда выживает 8 или 9 мышей, а яд в одной из 10 бутылок. 10 бутылок и 8 мышей - можно справиться ещё за два дня, оставлю продолжение без разбора. Итого на весь эксперимент ушло четыре дня, а если немного оптимизировать алгоритм, то скорее всего сможем уменьшить до трёх.

Хорошо, но все числа мы выбрали наобум. В задаче есть неявная подсказка - число мышей 10, а бутылок 1000, то почти что 2^10 (1024). Каждая мышь представляет один бит информации - либо выживает после эксперимента, либо нет. Десяти бит достаточно, чтобы представить любое число от 1 до 1000. Это намекает на то, что каким-то образом мы можем справиться за один эксперимент. Это было бы замечательно, потому что если бы лучшим решением было бы два дня, то помимо алгоритма для двух дней, пришлось бы доказывать, что задачу невозможно решить за один.

Итак, пытаемся смешать содержимое бутылок так, чтобы решить задачу за один эксперимент. Пронумеруем все бутылки с вином или ядом от 0 до 999 и запишем их двоичное представление. Наше решение можно проводить и для 1024 бутылок.

    1 2 3 4 5 6 7 8 9 10   №

    0 0 0 0 0 0 0 0 0 0    0
    0 0 0 0 0 0 0 0 0 1    1
    0 0 0 0 0 0 0 0 1 0    2
    ...
    0 1 1 1 0 1 0 1 1 1    471 (для примера)
    ...
    1 1 1 1 1 0 0 1 1 1    999
    

    0 1 1 1 0 1 0 1 1 1
    

Понятно, что можно было бы найти отравленную бутылку так же за один эксперимент, даже если бы их было 1024. А если 1025? Давайте попробуем показать, а лучше доказать, что это невозможно.

Предположим, что имеется 1025 бутылок, в одной из них яд, и имеется способ определить отравленную бутылку за один эксперимент. Количество различных возможных исходов эксперимента равно 2^10 = 1024 (два исхода для каждой из 10 мышей, считаем все комбинации). Каждая отравленная бутылка (вернее, входные данные задачи, при которых яд именно в этой бутылке) однозначно определяет исход эксперимента. Теперь по принципу Дирихле (Если кролики рассажены в клетки, причём число кроликов больше числа клеток, то хотя бы в одной из клеток находится более одного кролика) мы можем утверждать, что существует как минимум две бутылки, приводящих к одному и тому же исходу, а значит алгоритм не может однозначно определить, в какой из них яд, что противоречит предположению о его корректности. Многословно, но вроде доказали.

Пираты и сокровище

Формулировка задачи. Три пирата нашли сундук с сокровищами. Предложите способ поделить сокровище так, чтобы все остались довольны при следующих условиях:

1. Каждый пират доволен, если уверен, что получил не менее трети сокровищ
2. Каждый пират любую часть сокровища может поделить на любое количество равных на его взгляд частей.
3. Разные пираты могут оценивать сокровище по-разному.

Решение. Способ для двух пиратов широко известен: один делит, другой выбирает. Каждый уверен, что получил не менее половины сокровищ. Это общеизвестный алгоритм, и тем интереснее подумать, как действовать пиратам, если их трое. Я сам придумал алгоритм недавно, поэтому решил поделиться. Попробуем пойти очевидным путём - первый поделит на три части, двое других будут выбирать себе большую по их мнению часть. Если они выберут разные части, то задача решена - каждый из получает то, что выбрал, первый пират оставшуюся часть. Поэтому исходим из того, что их выбор совпал.

Пронумеруем части: ч1, ч2, ч3. Пусть второй и третий оба выбрали ч1. Тогда они могут поделить её между собой, и у каждого уже будет >=1/6 сокровищ, а ч2 и ч3 остаются.

Второй и третий теперь могут выбрать меньшую часть. Если их выбор совпадёт, то эта часть достаётся первому пирату, он доволен, ведь он делил сам. А второй и третий делят между собой оставшуюся часть и в итоге каждый из них доволен.

Так что далее исходим из того, что второй считает меньшей ч2, а третий ч3, то есть мнение их не совпадает. Напомню, что у них уже есть одна шестая сокровищ, а первый уверен, что ч2 и ч3 это ровно треть сокровищ.

Пересчитаем условие - получается, что от оставшейся части ч23 = ч2 + ч3 второй и третий хотят получить не менее четверти. Второй считает, что ч2 <= 1/2 * ч23, а ч3 >= 1/2 * ч23. Третий - наоборот.

Тогда второй делит ч3 на две равные части, а третий делит ч2 тоже на две равные части. Первый выбирает из каждой по одной, он уверен, что это не менее чем два раза по одной шестой, то есть его доля зафиксирована.

Второй и третий получают оставшиеся части. Второй уверен, что получил половину от ч3, то есть не меньше, чем четверти ч23. Третий так же. Теперь всё сокровище поделено и каждый уверен, что его доля не менее трети. Задача решена.

Судя по всему, решений для троих можно придумать много и даже обобщить до N пиратов.

Проверка наличия цикла в однонаправленном графе

Задача широко известна, решение - создать два итератора, на одном вызывать метод next() один раз, на другом - два, сравнивая с первым указателем. Совпадение - цикл. Дошли до конца - цикла нет. Здесь скорее упражнение - предлагаю посчитать алгоритмическую сложность этого решения при условии, что в графе есть 2*N элементов, а последний элемент указывает на середину (то есть длина цикла N). Выгодно ли второй итератор разгонять сильнее, например, удваивать на каждой итерации, какая сложность будет в этом случае?

Заключение

Я постарался привести те задачи, в которых навыки и принципы программирования важны при нахождении решения или проверке его оптимальности. Эти задачи широко известны и много раз описаны, но я попробовал их немного развить и дополнить, потому что обычно именно так строится беседа на собеседовании: не вопрос - ответ (или задача - решение), а скорее поток наводящих или уточняющих вопросов с целью понять, как будет рассуждать человек, да и просто поговорить.