Логика в программировании: логические задачи с собеседований

16
32472
Добавить в избранное

Нестандартное мышление и логика в программировании – наше все. На собеседовании будьте готовы к тому, что некоторые задачи будут нетривиальными.

Логика в программировании

Полторы белки и логика в программировании

1,5 белки, да: такая задача действительно существует. Давайте посмотрим на условие:

1,5 белки за 1,5 минуты съедают 1,5 ореха. Сколько орехов съедят 9 белок за 9 минут?

Лампочки и переключатели

Условие:

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

Бейсбольный мяч и бита

Здесь работает чистая математика. Условие:

Бейсбольный мяч с битой вместе стоят $13. Но мяч дешевле бейсбольной биты на $3. Рассчитайте стоимость каждого предмета.

Задача о фальшивой монете

Логика в программировании не ограничивается только математической составляющей, но она является одной из ключевых. То же самое и в случае с монетами. Условие:

Дано 12 монет, из которых 11 – настоящие, и только 1 – фальшивая. Фальшивая монета отличается от настоящих по массе. Какое минимальное количество взвешиваний необходимо, чтобы обнаружить фальшивую монету? Для взвешивания используются чашечные весы.

Сжигаем веревки

Условие:

Есть 2 веревки и неограниченное количество спичек. Каждая веревка сгорает за час, однако горят они неравномерно, так что нельзя точно узнать, за какое время сгорит определенная часть веревки. Как отмерить с помощью этих двух веревок интервал в 45 минут?

Бочка с водой

Условие:

Дана пустая бочка. Нужно наполнить ее водой так, чтобы заполнена была только половина. Использовать палку или другие предметы для измерения нельзя.

Дождь и солнце

Это очень легкая задача, но горе вам, если зададут ее под конец собеседования, когда последние силы покинут, а мыслительный процесс начнет изрядно буксовать. Условие:

12 часов ночи. Идет дождь. Можно ли ожидать, что по истечении 72 часов будет солнечная погода?

Кофе-брейк

Условие:

В офисе расположили 3 автомата с различными напитками. В первом – кофе, во втором – чай, а в третьем – и кофе, и чай (выдает случайным образом). Для любого из них нужна 1 монета. Каждый автомат обозначен наклейкой с названием продукта, который он выдаёт. Вот только на заводе перепутали наклейки, и на каждом из трех автоматов оказалась неправильная. За сколько монет можно выяснить, где какой автомат?

А вот вам еще несколько интересных задач, которые рассчитаны исключительно на программистов. Сможете их решить? 😉

  1. Сколькими способами можно разложить на 6 целых множителей 1 000 000?
  2. Имеем большой файл в несколько Гб, в котором записаны целые числа. Нужно записать в другой файл все эти числа в отсортированном порядке. Как это сделать максимально эффективно?
  3. Имеем все тот же большой файл в несколько Гб с целыми числами. Каждое число встречается дважды, но также есть 1 число, которое встречается всего 1 раз. Предложите эффективный алгоритм для поиска этого числа.

Вас также могут заинтересовать:

Готовитесь к собеседованию?

Подпишитесь на нашу рассылку, чтобы получать больше интересных материалов:

И не беспокойтесь, мы тоже не любим спам. Отписаться можно в любое время.




16 Комментарии

  1. Что-то мне кажется, что задача про «Кофе-брейк» имеет неправильное решение. Почему кинув одну монету можно судить о всех остальных автоматах? Мне кажется, что надо использовать минимум две монеты. Если я не прав, исправьте меня. Если мы кидаем монету и попадаем в автомат, который выдаёт нам чай и кофе, то он выдаст нам либо то, либо другое. Но мы не можем точно сказать, что этот автомат относится к той или иной группе, потому что мы наверняка не знаем, выдаст ли нам автомат в следующий раз тот же результат. Мы можем предположить, что автомат относится к одной из групп (чай OR чай-кофе) или (кофе OR чай-кофе). Для того, чтобы уточнить результат, нам надо использовать ещё одну монету и только тогда мы сможем узнать, к какой группе относится этот автомат. Здесь не будет работать простое исключение, ведь мы не знаем наверняка, какой перед нами автомат, если кинем одну монету. Если наклейки расположены так: {чай -> кофейный автомат}, {кофе -> кофе-чайный автомат}, {кофе-чай -> чайный автомат}, то мы не сможем применить ту логику, что представлена в решении выше. Исправьте пожалуйста, если я не прав. Спасибо.

    • Перепутаны все наклейки. То есть все 3 наклейки 100% не на своих местах. Первую монету бросаем в автомат с надписью «чай-кофе». Далее — методом исключения. Если автомат «чай-кофе» выдает чай — он чайный. Следовательно автомат с надписью «кофе» не может выдавать ни чай, ни кофе: он выдает и кофе, и чай. Остается последний: «чай» выдает кофе. Почему не сможем?

  2. Условие задачи про монеты выглядит не полным.
    Не сказано какие весы используются (видимо с двумя чашами).
    Также неизвестно, фальшивая монета легче или тяжелее, оригинальной.
    Я думаю, что при данной формулировке задания однозначно верно определить фальшивую монету за 3 взвешивания возможно только в одном счастливом случае.

    • Если в условии стоит «легче» или «тяжелее» — 2 взвешивания. Если данной информации в условии нет (а ее нет) — 3 взвешивания.

      • Думаю, что за два взвешивания при самом удачном раскладе возможно определить. Удачный расклад, это когда первое взвешивание показывает разницу в весе.

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

        Так что минимум два взвешивания.

      • Задача про монеты действительно выглядит неполной.
        Во-первых не сказано рассматриваются ли случаи «удачи» или нужно гарантированно определить при любом раскладе.

        Потому что, при удачном случае происходит следующее: берем 2 монеты и они различаются по весу. Одну из монет меняем, если опять различие — то оставшаяся монета фальшивая. Если чашки уравнялись, значит замененная монета — фальшивая.
        Вот и всё, 2 взвешивания и вполне вписывается в условие задачи.

      • За 2 взвешивания найти фальшивую монету, зная легче она или тяжелее остальных, можно среди 9 монет, а не 12. В задачах на логику не рассматриваются ответы на «удачу». То есть нужно подсчитать самый неблагоприятный исход. В задаче четко указано найти фальшивую монету с неизвестным весом и за 3 взвешивания это сделать физически невозможно (даже для 9 монет, нужно 5). Ответ автора, что многие отвечают «1» или «2», убил.

        • Да, можно найти за 3 взвешивания. Я бы сам не додумался. Нашел в другом месте. Решение интересное и ни разу не легкое. Жаль, что в статье его нет.

  3. Первые задачки решены верно, но абсолютно глупо.
    По сути это уровнения, которые решают в 5-6 классе. А задачка про лампочки… Причем тут программирование? Это вопросы на уровень: «давать ему острый нож или порежется».

  4. Про бочку:

    >Заполняем бочку водой (или полностью, или точно больше половины).
    >Наклоняем бочку на 45 градусов: вся лишняя вода выливается, и остается ровно половина.

    Нет, не на 45 градусов. Бочка может быть произвольных размеров (удлиненная или наоборот, «широкая») и тогда условия задачи не соблюдаются. На 45 градусов имеет смысл опрокидывать бочку только в том случае, если в меридиональном сечении она квадратная. Произвольную бочку нужно опрокидывать так, чтобы уровень воды проходил по диагонали в меридиональном сечении.

  5. 1) По поводу задачи с бочкой воды. Во первых решение неточное уже в том, что мы не знаем сколько будет наглаз 45 градусов. Мое решение было таким: наполняем бочку полностью, делаем дырку посередине, вуаля половина бочки. Либо находим центр окружности бочки, наполняем полностью, делаем дырку в центре окружности, переворачиваем, задача решена …. как бы. Только вот опять же не точно.
    Машинное обучение на глаз … ну не знаю стал бы я такому доверять.

    P.S. Может кто-то знает как без линейки и циркуля найти центр окружности? … ну и сделать дырку другим, не измерительным предметом мы по условию можем. Допустим я возьму гвоздь и молоток.

    2) Чай, кофе или чай-кофе. О да… Я тут просто завис. Если ребята перепутали на заводе наклейки, какая вероятность того, что они перепутали их 1 раз? Я допускаю что они могли перепутать их рандомно опять же. Либо наклеек вообще нет.

    Мой ответ: минимально 3. Мы бросаем в любые 2, а потом повторно в один из них. Если он поменял напиток, значит задача решена. Но по скольку не сказано что кофе-чай обязательно меняет напиток (т.е. это не триггер), то он может выдавать кофе и чаи помногу раз повторяясь, по этому вычислить его будет дороже

    • Про бочку. Заполненную бочку нужно наклонять до тех пор, пока не покажется ободок дна. Тогда воды будет ровно половина бочки (любой симметричной формы).

      Про автоматы с напитками. В условии задачи указано, что все наклейки неправильные. Следовательно, машина с наклейкой «чай-кофе», точно не машина, выдающая и чай, и кофе. Узнав одной монетой, какой напиток она выдает, мы, зная, что на двух других машинах наклейки тоже перепутаны, сможем определить, кто какие напитки выдает.

  6. Бейсбольный мяч и бита: вспомним школу 🙂
    Дано:
    мяч + 3 = бита
    мяч + бита = 13
    Найти:
    мяч = ?
    бита = ?
    Решение:
    мяч = x
    бита = x + 3
    x + x + 3 = 13
    x + x = 10
    x = 5
    Ответ:
    мяч = 5
    бита = 8

Оставьте комментарий