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

15
48264
Добавить в избранное

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

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

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

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 раз. Предложите эффективный алгоритм для поиска этого числа.

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

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

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

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




Комментариев: 15

  1. Про биту, (13-3)/2+3=8 бита, 13-8=5мяч

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

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

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

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

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

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

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

  4. Про бочку:

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

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

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

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

    1. Возможно я и ошибаюсь, но фальшивые монеты обычно весят меньше настоящих, поэтому это, скорее всего, просто опущено в условии. Тогда мы можем вычислить фальшивую монету за три взвешивания :
      1) Кладем на чаши весов по 6 монет. Те, что весят тяжелее откладываем, из тех, что весили легче формируем две кучки 3 и3
      2) Взвешиваем на чашах весов 3 и 3 монеты. Оставляем те, что легче.
      3) Берем две монеты и взвешиваем — та, что легче — фальшивая. Если же монеты на весах имеют одинаковую массу, то та монетка, что осталась лежать на столе — фальшивка

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

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

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

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

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

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

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

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

  7. Ishtvan_Okhelmann

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

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

Добавить комментарий