Дюжина логических задач с собеседований

    image

    Не знаю, как у вас, но у меня любимая часть интервью — логические задачи.
    Довелось пройти немало собеседований на вакансию разработчика, поэтому набралась небольшая коллекция.
    Спешу поделиться с вами!

    Некоторые задачи проще и широкоизвестные, другие заставляют хорошенько задуматься.
    Ответы пока что публиковать не буду, надеюсь, вы сами сможете всё решить.
    Предлагаю размять свой мозг...

    1) Человек построил дом, все стены которого смотрят на юг. К нему в дом забрался медведь. Какого цвета медведь?

    2) На столе 12 монет, одна из которых фальшивая. Она отличается от остальных лишь по массе. За какое минимальное число взвешиваний на чашечных весах можно обнаружить фальшивую монету?

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

    4) Даны две веревки и спички. Каждая из верёвок сгорает за 1 час, но горят они неравномерно, поэтому нельзя точно узнать, какая часть веревки за какое время сгорит. Как отмерить при помощи этих веревок интервал в 45 минут?

    5) В офис привезли три автомата с напитками. Первый выдаёт чай, второй кофе, а третий случайным образом чай или кофе. Стакан любого напитка стоит одну монету. На каждом автомате есть наклейка с названием продукта, который он выдаёт. Так получилось, что на заводе перепутали местами наклейки и на каждом автомате оказалась неправильная. Сколько нужно потратить монет, чтобы выяснить, где какой автомат?

    6) Есть два абонента A и B, почтальон C и открытый сейф с двумя замками. У каждого абонента есть ключ от одного из замков. Если передавать ключ через почтальона, то он может сделать дубликат. Как передать письмо от одного абонента к другому через почтальона, чтобы тот не смог его прочитать? Как изменится алгоритм, если в сейфе сделать небольшое отверстие для вложения письма?

    7) Путник находится в лесу в какой-то случайной точке. Известно, что площадь леса равна S, а форма может быть совершенно произвольная, однако в лесу нет полян. По какой траектории нужно двигаться путнику, чтобы гарантировано выйти из леса затратив минимальный по длине маршрут?

    8) Путешественник прошёл один километр на юг, затем один километр на запад, а после один километр на север и вернулся в исходную точку. Сколько существует таких мест на земле? Подсказка: больше одного…

    9) Есть огромный файл в несколько гигабайт, в котором записаны целые числа. Нужно записать в другой файл все эти числа в отсортированном порядке. Как это эффективно сделать?

    10) Есть огромный файл в несколько гигабайт, в котором записаны целые числа. Известно, что каждое число встречается два раза, но есть единственное число, которое встречается один раз. Предложите эффективный алгоритм для поиска этого числа. Как изменится алгоритм, если каждое число будет встречаться в файле чётное число раз, а единственное из них нечётное число раз?

    11) Есть огромный файл, в котором записаны все целые числа из диапазона от 1 до 10^9 в произвольном порядке. То есть в файле есть абсолютно все числа из этого диапазона, и встречаются они лишь по одному разу. Однако одно число встречается два раза. Как найти это число эффективным образом?

    12) Сколькими способами можно разложить на 6 целых множителей 1 000 000?

    P.S. Любителям геометрии на закуску euclidthegame.org
    Поделиться публикацией
    Реклама помогает поддерживать и развивать наши сервисы

    Подробнее
    Реклама
    Комментарии 244
    • +2
      Задание под номер 8 интересное.
      • +1
        Популярный вопрос, задавали мне его на собеседовании. Решения очень простые.
        • +4
          если простое решение — это про наворачивание кругов вокруг полюса, то у меня вопрос.
          если я нахожусь в 500м от южного полюса и начинаю идти на юг, верно ли утверждение, что через 500м я буду продолжать идти на юг? Кажется, что нет.
          • +1
            Нет, оказавшись на южном полюсе вы дальше не сможете идти на юг, куда бы не пошли, все пути будут на север.
            А вот идея про наворачивание кругов хорошая.
            • +2
              а ну я догнал. на расстоянии, скажем, (1000 + 1000/2*k*pi)м от южного полюса начать идти на юг, потом навернуть k кругов и вернуться назад. да, я не правильно запомнил то решение
              • +1
                Есть ещё второе, более простое решение.
                • +15
                  Этой фразой можно убить любое решение любой задачи!
                  • +7
                    При этом приводить само решение ни в коем случае не надо — пускай человек мучается, гадает (:
                  • –3
                    Любая точка в 500 метрах севернее экватора подойдёт.
                    • НЛО прилетело и опубликовало эту надпись здесь
                      • –1
                        на одинаковом удалении на север и юг от экватора идеального геоида длины параллелей одинаковые
                        image
                        как-то так
                        • +3
                          В условии задачи нет возврата на восток.
                          • +2
                            верно. в следующий раз внимательнее буду условие читать =)
                            • +1
                              в таком случае кроме северного полюса в голову ничего не приходит
                              • +1
                                Я чуть ниже привел второе решение.
                          • НЛО прилетело и опубликовало эту надпись здесь
                        • +3
                          Неверно. Подойдет любая точка в 1 + 1/2pi км севернее южного полюса.

                          P.S. Действительно интересная задачка.
                          • –1
                            не согласен. по поверхности вы пройдёте 1 км. поэтому вам нужна половина этого расстояния по каждую сторону экватора, а это 500 метров.
                            • +3
                              Пройдя на 1 км на юг вы окажетесь в 1/2pi км от южного полюса. Если вы пройдете 1 км на запад, вы опишите окружность вернувшись в ту же точку (2 * pi * r = 2 * pi * (1/2pi) = 1). Теперь вернувшись на 1 км на север вы окажетесь в том месте, откуда начали путешествие.
                              • +1
                                Вот только мне кажется не 1/2π, а чуть больше — Земля же не плоская.
                                • +1
                                  Так и есть, но на таких маленьких расстояниях погрешность ничтожно мала. Ну и главое в решении подобных задач не точные цифры, а общая идея решения :)
                          • +1
                            Чтоб, когда двигаешься на запад — вернулся в ту же точку.
                            • НЛО прилетело и опубликовало эту надпись здесь
                          • НЛО прилетело и опубликовало эту надпись здесь
                            • +1
                              Это про Северный полюс?
                          • +1
                            (1000 + 1000/2*k*pi)м

                            Не понял, как вы это получили?

                            Вот мое решение, идея похожа на вашу:
                            mathb.in/18669
                            • +1
                              пройдя 1 км на юг, путник должен остановиться на таком расстоянии от полюса, чтобы 1км пути на запад составил k полных кругов, чтобы вернуться в ту же точку при возвращении на север. Длина огружности 2*pi*r, 1000 = 2 * pi * r * k, ну да, неточность в том, что надо было написать 1000 / ( 2 * k * pi). подразумевал я это, дроби плэйн текстом — это занудно.
                              • +1
                                Не правильно выразился. Из вашего комментария было не понятно, что означает это число?
                                (1000 + 1000/2*k*pi)м

                                Вы получили сумму 1000 метров и некого радиуса до оси земли. В чем математический смысл этого числа?

                                То, что вы выше описали, и так очевидно :)
                                • +1
                                  любая точка на окружности радиусом (1000 + 1000/2*k*pi)м с центром в южном полюсе подходит под решение.
                                  то есть этих мест бесконечное количество применительно к вопросу задачи
                                  • +1
                                    Не понятно, что такое окружность с центром в южном полюсе?
                                    • +1
                                      радиус земли 6400 км, область о которой мы говорим, имеет радиус 1160 метров, в этих условиях можем считать область вокруг полюса плоской. Можно, конечно внести поправку на геоид, но это экономия на спичках, поправка на искривленность будет меньше, скажем, минимальной ширины траектории человека.
                                      Если бы в условии задачи шла речь об отрезках, хотя бы 100км, то, да, поправка уже может стать весьма существенной
                                      • +1
                                        Все не так просто, как вам кажется:
                                        Даже если для k=1 — вы промахнетесь на 0.01% в вычислении нужных точек, то вы ошибетесь на 0,036 градуса и немного не попадете в начальную точку. В принципе ничего страшного.
                                        Но в вашей формуле ошибка в вычислениях пропорциональна k, и, ошибаясь в каждом витке на 0.01%, для k=500 вы пойдете в диаметрально противоположную сторону, потому что ошибка будет 180 градусов.
                                        • +1
                                          при k=1 интересующий нас радиус составляет 159.15м. Поправка на искривленность в этом случае сильно меньше ширины траектории. Минимальная ширина траектории — это ширина ступни, то есть где-то 0.1м и то, добиться такой ширины траектории практически не возможно. При больших значениях k область еще больше сужается, что дает нам возможность без проблем говорить о плоскости.
                                          • +2
                                            1) Хорошо, сыграю вашим методом: С чего вы вообще взяли, что речь идет о платене Земля? С чего вы взяли, что «путешественник» — человек? Возьмем нейтронную звезду радиуса 1км и в качестве путешественника, например, электрон. Честное математическое решение будет работать до тех пор, пока piR > 1км.

                                            2) При k=100 витки будут по 10 метров, ошибка хотя бы на 1 см в вычислении длины витка приведет к 1 метру погрешности в итоге. А это 1/10 круга или 36 градусов. В итоге путник промахнется на ~600 метров (если речь идет о Земле) от начальной точки.
                                            • +1
                                              1. казуистика
                                              2. подсчитайте погрешность предположения о плоскости земли в радиусе 16 метров (k=100) от полюса. И сравните ее с 1см
                                              • 0
                                                Ладно я понял вашу позицию, я думаю, вы поняли мою.

                                                Вообще условие задачи слишком расплывчатое, чтобы что-то говорить конкретно. По крайней мере я на собеседовании больше смотрю на то, как человек пытается решать задачу и какие вопросы задает в процессе, а какой ответ от получит по большому счету вообще не важно.
                                          • +1
                                            все, что я хотел сказать, что это задачка на сообразительность, а не на точность, поэтому достаточно приближения плоской земли вокруг плоскости. Ваш подход тоже плох, т.к. земля не шар, а геоид. Поэтому углубляться в такие точности в этой задаче в рамках собеседования — это скорее минус на собеседовании, любой оптимизации свое время.
                                            • +1
                                              если же вы просто хотите докопаться до погрешности моей формулы, то, конечно же, вы правы, поправка на форму поверхности нужна. Но тогда и вы не правы, используя поправку на сферу
                                              • +1
                                                ну и я тогда напоследок докопаюсь :)
                                                при k=500 и погрешности 0.01% на витке, я в итоге ошибусь на 5% и в итоге собьюсь на 18 градусов )
                                                • +1
                                                  Это да, я хотел написать про 5000 конечно же =)
                                                  • +1
                                                    Ну и оба вы не правы.)
                                                    1. Условия задачи не расплывчатые, а предельно конкретные.
                                                    2. Ответ тоже предельно конкретен: существкет бесконечное множество точее, для которых удовлетворяются условия задачи.
                                                    3. Доп.вопрос «а какие это точки» полностью удовлетворяется ответом: это сев.полюс и множество окружностей у южного, пройдя 1 км на юг от которых, оказываешься в месте, пройдя 1 км на запад, ты сделаешь один или больше полных кругов. Заметьте, вопроса и ответа о точном расстоянии этих кругов до полюса все еще нет, хотя множество этих кругов описано однозначно четко.
                                                    4. На вопрос о формуле для расстояния этих кругов от полюса абсолютно подходит плоское приближени (предполагаем что это Земля).
                                                    5. Любителям докапываться до точности замечу, что мелкие неровности поверхности, холмики, торосы, ямки и т.п. существенно увеличивают расстояние и напрочь убивают любые «точные» представления хоть как шара, хоть как геоида, хоть как гамбургера.
                                                    6. Задача явно на сообразительность, а не на расчеты.
                        • +5
                          Ох, помню эту задачу с фальшивой монетой. В начальной школе давали каждую неделю парочку подобных логических задач и очень часто были разные вариации с фальшивой монетой. Эти задачи испортили мне все детство!
                          • +2
                            Интересно, а в этой задаче, как она тут сформулирована, ответ два взвешивания подходит?
                            • +8
                              Не совсем… По идее да, это будет считаться правильным вариантом решения, хоть это им и не является:

                              По условию фальшивая монета может обладать абсолютно любым весом относительно остальных. И задача спрашивает
                              За какое минимальное число взвешиваний на чашечных весах можно обнаружить фальшивую монету?

                              Значит, может получиться частный случай, когда фальшивая монета тяжелее двух масс обычной монеты. (3х, 4х, etc)
                              В этом случае можно обнаружить фальшивую монету за одно взвешивание. Если вам повезёт, и первым взвешиванием вы положите на одну чашу весов фальшивую монету, а на другую чашу весов — две обычных. Фальшивая монета перевесит, и единственный вывод из этой ситуации будет: одна монета, перевешивающая две другие — фальшивая.

                              Правильно было бы задать вопрос:
                              За какое наименьшее количество взвешиваний вы всегда узнаете, какая из монет фальшивая.
                              • +1
                                Да, получается можно и за одно.
                                Интересно, а можно ли как-то посчитать вероятность с которой можно определить фальшивую монету за одно и два взвешивания?
                                • +2
                                  За одно в любом случае нельзя, ведь неизвестно заранее, тяжелее она или легче. Поэтому даже если рассматривать, как говорит Shultc, случай, когда сразу попалась пара хорошая-фальшивая — нужно провести еще одно взвешивание, чтобы определить, фальшивой является более тяжелая или более легкая монета.
                                  • +1
                                    Читайте внимательнее. Я предложил что попалась две монеты, которые в сумме легче одной. Какие в такой ситуации могут быть варианты, кроме как та одна монета — фальшивая?
                                    • +2
                                      Да, понял. Про случай сильно-сильно отличающейся массы как-то не осознал даже. Красиво =)
                                      • +1
                                        Спасибо! Была ещё идея про магнитящуюся монету с отрицательным весом… Но решил не засорять мозги читателям Хабра.
                                        • НЛО прилетело и опубликовало эту надпись здесь
                              • –2
                                Вообще, мне видится, что вопрос некорректен. Если какое минимально гарантированное, то 6, если просто минимальное, то одного взвешивания может хватить.
                                • +10
                                  А нет, минимально гарантированно — за 3 раза.
                                  • –7
                                    Минимально гарантированно — за 2 раза.
                                    • +4
                                      за 2 не получится. ведь из условий задачи неясно, легче подделка или тяжелее, чем остальные.
                                      • –4
                                        Почему не получится? Исходя из формулировки «минимальное кол-во» предполагаем что нам повезло, и мы сразу выбрали для первого взвешивание две монеты одна из которых фальшивая. Для второго взвешивания мы берем третью монету, которая заведомо настоящая, и одну из первых двух. В зависимости от результата второго взвешивания определяется какая из первых двух фальшивая.
                                        • +1
                                          100% решают задачу 3 взвешивания.
                                          за 2 взвешивания решения будет работать в 25% случаев. это не решение, это баг ;)
                                          • 0
                                            Нам повезло и мы выбрали фальшивую монету без взвешиваний!
                                            лолчто??
                                            • 0
                                              А теперь без взвешиваний докажите, что она фальшивая.
                                        • –1
                                          Эт как? Делим же 6 на 6, затем 3 на 3. У нас остается кучка из трех монет, одна из которых фальшивая. Как за два-то?
                                          • 0
                                            тоже всегда решал эту задачу бинарным поиском
                                            • +1
                                              1. взвешиваем 1234 и 5678 (1)
                                              если равны — взвешиваем 9-10 и 11-8 (2)
                                              если равны — дефектный 12, сравниваем его с любым другим (3)
                                              если второе взвешивание неравно — взвешиваем 9 и 10 (3)
                                              если равно — дефектный 11, сторона по результату второго взвешивания
                                              если не равно, то по результату второго взвешивания известна сторона, а по результату третьего известно кто из них.
                                              — остался вариант когда первое взвешивание не равно, 1234 <> 5678
                                              взвешиваем 125 и 369 (2)
                                              если равно — дефектный среди 478
                                              взвешиваем 7 и 8 (3)
                                              если равно — дефектный 4, сторона по первому взвешиванию
                                              если нет — сторона по первому взвешиванию, какой шар — по третьему
                                              — если второе не равно, то два варианта — знак во взвешивании 1 и взвешивании 2 разный или одинаковый
                                              если разный — дефектный один из перемещенных шаров: 5 или 3.
                                              взвешиваем любой из них с любым нормальным (3) по результату понятно какой из них, по результату первого взвешивания известна сторона
                                              если одинаковый — дефектный один из 126
                                              тогда сравниваем 1 и 2 (3)
                                              если равны — дефектный 6, сторона по результату первого взвешивания
                                              если нет, то сторона по результату первого взвешивания, а кто из них понятно по третьему.
                                        • +4
                                          Да. За 3. Думаю решение полезно знать. Решается методом теории инфонмации.
                                          b — эксперимент, определить монету. Его энтропия H(b)=log(12). одно взвешивание дает не более log(3) информации. k — взвешиваний дают не более I<= klog(3) информации. Так как информация I позволяет определить монету, то I>=H(b). Имеем k>=log(12)/log(3). То есть k>=2.26… Так как k — целое, то требуемое равно 3.
                                          • –3
                                            А зачем так мучиться, логично же что если число монет четное нужно делить каждый раз на два. Это же логические задачи а не математические.
                                            • 0
                                              Попробуйте воспользоваться своим методом для 8 монет. Вы будете удивлены :)
                                            • 0
                                              а почему «одно взвешивание дает не более log(3) информации»?
                                              • +1
                                                Всего три различных исхода: перевесила одна чаша, перевесила вторая, обе чаши весят одинаково.
                                          • 0
                                            Каждое взвешивание дает один трит=lb(3) бит информации. Следовательно, максимум три.
                                        • 0
                                          Задачки с монетками, только попроще, были в книжке Шарыгина «Задачи на смекалку для 5-6 класса».
                                        • +16
                                          Я просто оставлю это здесь
                                          braingames.ru
                                          • +5
                                            «Капча» у них прекрасна!
                                            • +3
                                              а я тогда, вот это nazva.net
                                              • 0
                                                Мда, мегафон решил что этот сайт с платной подпиской. Будьте аккуратнее.
                                              • +2
                                                Вернулся сюда только чтобы сказать спасибо.
                                                • 0
                                                  За ссылку спасибо
                                                • +4
                                                  По-моему, задача 7 сводится к задаче Дидоны. По незамкнутой траектории ходить не стоит: есть риск, что лес — узенькая полосочка вокруг нашей траектории. Если же мы прошли по замкнутой траектории, а лес всё ещё не кончился — значит, траектория гарантированно не охватывает площадь S…

                                                  9 — внешняя сортировка, несложного и для всех случаев оптимального алгоритма для неё вроде бы нет…
                                                  • 0
                                                    Т.е., кажется, смысл вопроса 9 такой. Знает ли человек, что такое внешняя сортировка; и если не знает — способен ли написать хоть какую-то.
                                                    • 0
                                                      для каких случаев сортировка слиянием может считаться не оптимальной? что оптимальнее?
                                                      • +1
                                                        Я не читал, всё это — моё личное ИМХО.

                                                        Отрезки, умещающиеся в память, лучше сортировать «на месте» — а значит, не до слияний.

                                                        Несколько десятков или сотен таких отрезков можно слить таким образом. Заводим двоичную «кучу» по количеству отрезков. Минимальный элемент вытаскиваем, вставляем следующий за ним.

                                                        Если отрезков тысячи или десятки тысяч, то, вероятно, лучше рекурсивно: например, сливаем отрезки по 100 шт., потом полученные сотни сливаем ещё раз, снова сотнями… 100 — это я так сказал: эта цифра должна быть меньше на механическом винчестере и больше на SSD.
                                                        • +1
                                                          Это и есть алгоритм внешней сортировки:)
                                                          • 0
                                                            Ну… я думал именно над алгоритмом внешней сортировки.
                                                        • 0
                                                          P.S. Это если сортируем обычные числа фиксированной длины — например, восемь или шестнадцать байтов. Но часто ключ сортировки не числовой (а, например, строковый), и на этом ключе висит «полезная нагрузка» — какие-нибудь данные в сотни и более байтов на запись. В такой ситуации будут работать какие-нибудь хитрые, специфичные для задачи методики экономии памяти.
                                                      • +1
                                                        Здесь про память ничего не сказано. Если под «целыми числами» понимать int (32 бит) и у нас есть полгига ОЗУ, задача решается в лоб сортировкой подсчётом за О(N). Так же как и следующие.
                                                        • 0
                                                          Внешнюю сортировку я не писал, признаюсь честно. Подсчёты на «пограничном» объёме памяти писал. Приходится налаживать хитрый механизм: заводим массив по полбайта на число. В нём хранятся цифры до 14. 1111 = 15 — признак, что цифра перевалила за 14 и точное количество хранится в особой структуре памяти. Красно-чёрное дерево не годится из-за больших накладных расходов, лучше подобие хэш-таблицы.
                                                        • +1
                                                          Вопрос «Как это эффективно сделать». Самое эффективное, как мне кажется: sort <unsorted_ints> > <sorted_ints>. Это будет эффективнее чем писать собственный алгоритм :)
                                                        • 0
                                                          Мне вот задача 5 кажется интересной. Мы же не знаем ничего о вероятности получения чая или кофе в третьем автомате.
                                                          • +2
                                                            Аналогично. После трех монеток однозначно определяем один автомат, а дальше как повезет.
                                                            • +6
                                                              Одной монеты достаточно, кидать в чай/кофе. Ключ в том что надписи заведомо неправильные. Т.е. они не ничего не говорят, а точно говорят чего там нет.
                                                              • 0
                                                                Ах ну то есть они полностью перепутали, так гораздо проще, да.
                                                                • 0
                                                                  Если, бросая монетку в «чай», мы получаем чай => Это случайный автомат.
                                                                  А если получаем кофе — это либо автомат с кофе, либо случайный. Одной монетой не отделаешься.
                                                                  • +13
                                                                    Вы не поняли. Нужно кидать одну монету в автомат, помеченный, как «случайный». Она всё и решит:

                                                                    • Если вам нальётся кофе, значит это автомат с кофе. Он не может быть случайным, ибо наклейки никогда не говорят правду. Осталось два аппарата:
                                                                      • Аппарат с наклейкой «Чай» будет «Случайным».
                                                                      • Аппарат с наклейкой «Случайный» будет наливать чай.

                                                                    • Если вам нальётся чай, значит это автомат с чаем. Он не может быть случайным, ибо наклейки никогда не говорят правд. Осталось два аппарата:
                                                                      • Аппарат с наклейкой «Кофе» будет «Случайным».
                                                                      • Аппарат с наклейкой «Случайный» будет наливать кофе.

                                                                    • +1
                                                                      Точно, не правильно понял ваше «кидать в чай\кофе».
                                                                      • +7
                                                                        Немного не правильно написали. Вы же всегда бросаете монету в «Случайный» автомат. Значит всегда остаются автоматы «Кофе» и «Чай».
                                                                        То есть:
                                                                        если в «случайном» налили чай, то:
                                                                        — в автомате «чай» — кофе,
                                                                        — в автомате «кофе» — случайный.
                                                                        если в случайном налили кофе, то всё наоборот:
                                                                        — в автомате «чай» — случайный,
                                                                        — в автомате «кофе» — чай.
                                                                  • –1
                                                                    .
                                                                  • +1
                                                                    9 — обычно это тестовое задание. Внешняя сортировка, как она попала в «логические задачи»? 10, 11 — частные случаи.

                                                                    А где задача про циклический поезд в котором надо посчитать число вагонов включая и выключая свет? :)

                                                                    И вообще их там дофига разных, давно почти всё разжевали и даже книжку написали. Ерунда всё это, вот есть книжки хорошие «Математическое понимание природы» и «Задачи для детей от 5 до 15 лет» Арнольда. :)
                                                                    • +3
                                                                      11 — не частный случай, она намного проще :)
                                                                      • +1
                                                                        10 ещё проще. А в 9 один из вопросов — есть ли прямой доступ к файлу. Или можно ли создавать несколько файлов одновременно.
                                                                      • –2
                                                                        Зачем в задачах 10 и 11 вообще что-то сортировать? Создаем битовый массив, где номер бита равен значению числа (для диапазона 1..10^9 этот массив займет менее 120 Mb в памяти; в 1 Gb массива влезут числа в диапазоне от 0 до 8589934591). Первоначально все биты равны 0. Встречаем число — инвертируем соответствующий бит. А после ищем в массиве номер единственного оставшегося единичного / нулевого бита.
                                                                        • 0
                                                                          В 10) про диапазон чисел ничего не сказано. Может быть и MAX_INT.
                                                                          • 0
                                                                            Вы написали то, что мне и, думаю, всем давно известно. Это работает для «маленьких» массивов. А теперь представьте, что данных настолько много, что у вас нет памяти, чтобы выделить её на битовый массив. Что вы будете делать? В этом суть задач с «огромными файлами» — у вас нет памяти, куда можно всё положить.

                                                                            Сортировать не нужно, «частный случай» — это я имел в виду «частный случай задач на огромные файлы». Самая известная из них «внешняя сортировка» ещё у Кнута расписана. :)
                                                                            • 0
                                                                              Проблема возникнет, если файлы и числа настолько «огромные», что памяти не хватит даже на хранение одного числа.
                                                                              • 0
                                                                                Для работы с огромными целыми числами можно использовать длинную математику. Если памяти и в этом случае не хватит, значит задача нерешаема в данное время, либо мы делаем что-то совершенно неправильно. :)
                                                                                • 0
                                                                                  Решаема. Но в задачах 10 и 11 аккумулятор и индексы цикла придётся хранить в отдельных файлах, и менять при обработке каждого числа.
                                                                                  Интересно, как возвести в квадрат число, которое записано в файле, а в память не помещается. Наверное, как-то можно… Но это будет очень долго.
                                                                            • +4
                                                                              Не нужно никаких битовых массивов. В 10 нужно считать XOR от всех чисел. В 11 — сумма всех чисел в файле минус сумма чисел от 1 до 10^9, влезет в int64.
                                                                              • 0
                                                                                10 решается помоему простым XOR попорядку всех чисел — на выходе ответ. с дополнительным условием ничего не меняется.
                                                                                в 11 считаем попорядку сумму чисел, как только сумма становится больше 10^9 — вычитаем из нее (10^9+1) и прибавляем остальное таким образом дальше. на выходе получим ответ.
                                                                            • +2
                                                                              7 — идти по кругу с площадью больше S?
                                                                              • 0
                                                                                А не короче буквой Г?
                                                                                • +1
                                                                                  Нет, просто буквой Г ничего не добьётесь, так как площадь этого пути нулевая. Нужна замкнутая траектория и у круга периметр наименьший при равной площади по сравнению с треугольником или прямоугольником.
                                                                                • –1
                                                                                  Минуточку, но ведь в постановке значится
                                                                                  гарантировано выйти из леса затратив минимальный по длине маршрут


                                                                                  А что если лес имеет форму полоски, а путник неверно выбрал направление и пошел вдоль? Тогда маршрут не минимальный!
                                                                                  Или тут нужно делать акцент на слово «гарантировано»? (кстати почему-то с одной «н»)
                                                                                  • 0
                                                                                    Тут есть смысл скорее говорить об оптимальном, а не минимальном маршруте.
                                                                                    • НЛО прилетело и опубликовало эту надпись здесь
                                                                                      • 0
                                                                                        траектория в виде спирали не гарантированный выход?
                                                                                        • 0
                                                                                          Из леса в виде этой спирали? Нужен минимальный по длине.
                                                                                          • НЛО прилетело и опубликовало эту надпись здесь
                                                                                            • +1
                                                                                              Скорее, через 2*sqrt(pi*S)
                                                                                              • НЛО прилетело и опубликовало эту надпись здесь
                                                                                    • +1
                                                                                      2 и 8 — задачи из Перельмана.
                                                                                      11 — из «Жемчужин программирования».
                                                                                      • +2
                                                                                        А кто-то понял условие шестой задачи? До сих пор ломаю голову над самим условием…

                                                                                        У кого этот сейф? Имеют ли А и В к нему доступ? Если имеют оба, значит они могут просто передать письмо друг-другу из рук в руки… А если не имеют, то в любом случае прося почтальона положить письмо в сейф, есть вероятность, что тот его прочитает… Тогда сейф вообще не важен? Или вейф у одного из них, и его можно использовать как «мешочек» для письма?
                                                                                        • 0
                                                                                          Можно предположить, что оба имеют доступ к сейфу, но один — по чётным дням, другой — по нечётным, так что встретиться не могут. Почтальону не доверяют (в смысле, он может вскрыть письмо), так что письмо можно передать только через сейф. Ключ можно передать через почтальона, но тогда у почтальона окажется копия, которой он сможет открыть один из замков (и если откроется сейф — прочитать письмо).
                                                                                          Другой вариант (более вероятный) — что сейф портативный, и его тоже можно отдать почтальону. Как и ключ.
                                                                                          • +1
                                                                                            О том и речь. Что ж это за задача, в условии которой есть «варианты понимания»?

                                                                                            А правильный ответ будет вообще «Зашифруйте письмо» =)
                                                                                            • 0
                                                                                              Но как тогда организовать обмен криптографическими ключами? Почтальон может организовать атаку «человек посередине».
                                                                                              • +2
                                                                                                Например, вот так

                                                                                                • 0
                                                                                                  Идея та же. Почтальон может заменить публичный ключ на свой. Или я ошибаюсь?
                                                                                                  • 0
                                                                                                    Может. Это я затупил.
                                                                                                  • 0
                                                                                                    Диффи-Хелман подходит для случая, когда почтальон не может менять содержимое сообщений, т.е. не очень подходит в данном случае.
                                                                                              • +2
                                                                                                Хотя во втором варианте непонятно, зачем два замка.
                                                                                                A кладёт письмо в сейф, закрывает на замок, отправляет B.
                                                                                                B, получив сейф, отправляет записку «сейф получен».
                                                                                                A отправляет ключ. У почтальона сейфа уже нет, так что ключ не поможет.
                                                                                                • 0
                                                                                                  Я так понял, что оба имеют доступ к сейфу. Предположим, что это непередвигаемая банковская ячейка.
                                                                                                  У сейфа два замка — и открывается он только тогда, когда открыты оба.
                                                                                                  Ну и написать алгоритм для обмена почтой через такой сейф можно, но использовать асимметричное шифрование разумнее.
                                                                                                  • +4
                                                                                                    Ах да. А что, если почтальон отправляет записку «сейф получен», не передав его?
                                                                                                    Возможности верификации автора записки у нас по условию не предусмотрено.
                                                                                                    • 0
                                                                                                      Тогда он и замок вместо B сможет повесить. Я что-то не понимаю как от этого защититься.
                                                                                                      • 0
                                                                                                        повесить замок? где Вы видели сейф с внешним замком?
                                                                                                  • 0
                                                                                                    Я думаю
                                                                                                    — А цепляет замок на сейф (считаем что крепления на сейфе в форме 2-х колец, а замки амбарные без возможности автоматического закрытия) на одно из колец
                                                                                                    — Передает его к B, B всовывает в сейф письмо, и цепляет свой замок на замок А и второе кольцо и передает обратно
                                                                                                    — А получает сейф обратно и открывает свой замок.

                                                                                                    А воще не совсем понятны характеристики сейфа(можно ли туд кинуть ключ, сколько замков с какой логикой)/замков(можно ли замок закрыть без ключа, он встроенный или навесной, можно ли его положить в сейф)…
                                                                                                    • 0
                                                                                                      ЗЫ: Как ниже написали не применимо если можно подменить сам сейф, вобщем надо очертить меры возможностей почтальона.
                                                                                                      • 0
                                                                                                        зачем так сложно?
                                                                                                        кладем письмо, закрываем А
                                                                                                        приходит Б закрывает
                                                                                                        А открывает
                                                                                                        Б открывает, достает письмо

                                                                                                        Этож классика криптографии. :)
                                                                                                        • 0
                                                                                                          кладем письмо, закрываем А

                                                                                                          отправляем письмо Б «письмо в сейфе» почтальоном
                                                                                                          приходит Б закрывает

                                                                                                          отправляем письмо А «сейф закрыл» почтальоном
                                                                                                          А открывает

                                                                                                          отправляем письмо Б «сейф открыт» почтальоном
                                                                                                          Б открывает, достает письмо

                                                                                                          разве не так [ключи ни разу не попадают к почтальону => сейф можно использовать повторно]?! ведь в задаче вообще не сказанно, что сейф переносной; нет указаний и на то, что почтальон изменяет письма…
                                                                                                      • +1
                                                                                                        Тут просто надо передавать сейф.
                                                                                                        А кладет письмо в сейф и заквыет на свой КлючА. И передете почтальону, чтоб тот передал сейф к Б.
                                                                                                        Почтальон открыть сейф не может.
                                                                                                        Б получив сейф Закрывает его на свой ключБ. И отправляет обратно.
                                                                                                        А получив обратно окрывает свой замок ключемА, он сейф теперь закрыт на ключБ. И отправляет к Б.
                                                                                                        Б получив открывает сейф своим ключом.
                                                                                                        При каждой передаче через почтальона сейф был закрыт хотя бы на один замок.
                                                                                                    • +8
                                                                                                      Большая часть задач на собеседованиях стырена из книжки «Как сдвинуть гору Фудзи». Там же есть и общие указания, как решать задачку, если — внезапно! — попалась незнакомая.
                                                                                                      • +5
                                                                                                        С одной стороны решение таких задач показывает умение… решения таких задач.
                                                                                                        С другой стороны я подумал, кто бы из знакомых программистов это решил, и понял бы, что это будут лучшие программисты из них. Однако это будет связано не с программированием, а с тем, что человек умный, и хорошо получается и то, и другое.
                                                                                                        • +6
                                                                                                          Задача 6

                                                                                                          Сейф — это ящик с двумя замками.

                                                                                                          1. А — кладет письмо в сейф, запирает своим ключом, отдает почтальону.
                                                                                                          2. Почтальон доставляет ящик B.
                                                                                                          3. B — запирает ящик своим ключом, отдает почтальону для доставки A.
                                                                                                          4. A открывает свой замок и убеждается, что сейф остается заперт.
                                                                                                          5. Почтальон снова доставляет ящик B
                                                                                                          6. B — открывает сейф и получает письмо.
                                                                                                          6.5 — Почтальон сильно устал.

                                                                                                          Если есть прорезь, то B запирает сейф и отправляет его A. A сует письмо в прорезь и отправляет сейф B. B — отпирает.
                                                                                                          • +1
                                                                                                            Как защититься от того, что вместо этапов 2 и 3 почтальон повесит свой замок вместо B и вернёт его A? Мы же не можем предположить, что A и B секретно договорились об этом заранее, а почтальон не в курсе, ведь тогда можно было бы и пароль для шифрования сообщения передавать.
                                                                                                            • НЛО прилетело и опубликовало эту надпись здесь
                                                                                                              • 0
                                                                                                                B вообще не будет получать сейфа в случае этой атаки.
                                                                                                                • НЛО прилетело и опубликовало эту надпись здесь
                                                                                                              • 0
                                                                                                                открытый сейф с двумя замками.
                                                                                                                — о навесных замках речи нет.
                                                                                                            • +3
                                                                                                              С 6 ничего не могу понять

                                                                                                              «Есть два абонента A и B, почтальон C и открытый сейф с двумя замками. У каждого абонента есть ключ от одного из замков.»
                                                                                                              Тогда незачем передавать ключ.

                                                                                                              «Если передавать ключ через почтальона, то он может сделать дубликат.»
                                                                                                              Кому передавать? Корреспондент свой ключ имеет.

                                                                                                              «Как передать письмо от одного абонента к другому через почтальона, чтобы тот не смог его прочитать?»
                                                                                                              Зашифровать.

                                                                                                              Что-то с формулировкой мутно.
                                                                                                              • 0
                                                                                                                Нагуглил слудующий вариант этой задачки:

                                                                                                                Ромео и Джульетта были разлучены родителями и сидели каждый в своем замке. Они не могли встречаться, но им хотелось хотя бы писать друг другу любовные письма. Почта в те времена в Италии уже работала, но работала примитивно. Курьер относил адресату шкатулку со всем в нее вложенным. Влюбленные не могли допустить даже мысли о передаче своих писем в незапертой шкатулке, ведь содержание их так интимно! У Джульетты был навесной замок, на который она могла бы запереть почтовую шкатулку, но как ее раскроет Ромео? Ведь она не догадалась заранее снабдить его ключом. У Ромео тоже был замок, но пробемма у него была таже: как передать Джульетте ключ? Послать ключ в незапертой шкатулке до писем было бы полохой идеей. Любопытный почтальон наверняка сделал бы с него копию. Неужели положение безвыходно?
                                                                                                                • 0
                                                                                                                  Эта постановка задачи значительно проще и, возможно, корректнее.
                                                                                                                  Навесные замки можно соединить «цепочкой», таким образом, что открытие одного из них приведет к отпиранию шкатулки.

                                                                                                                  В случае сейфов с внутренними замками, задачу можно решить очевидным способом при наличии дубликатов своих ключей и возможности при закрывании сейфа автоматически защелкнуть любой из двух замков, даже если ключа от него нет.
                                                                                                                  • 0
                                                                                                                    А если просто передать сначала замок?
                                                                                                                    • +1
                                                                                                                      Замок нужно передавать по надежному каналу связи. Иначе почтальон может сделать свой ключ или подменить замок.
                                                                                                                      • 0
                                                                                                                        Если подменить замок — то переписки не выйдет. Потому что получатель не сможет открыть. И может замок такой сложный, что сделать ключ невозможно.
                                                                                                                        • +1
                                                                                                                          А отправляет замок З. Почтальон передает B свой замок Z. B отправляет письмо, закрыв сейф замком Z. Почтальон снимает замок Z, читает письмо, вешает замок З.
                                                                                                                          • 0
                                                                                                                            В сейфах редко бывают навесные замки. Чаще встроенные.
                                                                                                                            • 0
                                                                                                                              Навесные — это для похожей задачи:
                                                                                                                              habrahabr.ru/post/230881/#comment_7805223
                                                                                                                              • 0
                                                                                                                                Но идея та же — он подменяет сейф в таком случае.
                                                                                                                                • 0
                                                                                                                                  В оригинальной задаче все правильно — у А и В есть ключи, которые были переданы по надежному каналу, и сейф. Если есть возможность убедиться в целостности замка (пломбы те же), то можно гарантировать надежную переписку.
                                                                                                                                  В задаче про Ромео и Джульетту ничего про надежный канал связи не сказано, так что она нерешаема.
                                                                                                                                  • +2
                                                                                                                                    Не проходит.
                                                                                                                                    Всё упирается в две вещи:
                                                                                                                                    1) если почтальон подменяет сейф, то в нём оба замка другие, и тот, кто получил этот сейф, сразу обнаружит подмену.
                                                                                                                                    2) Когда A открывает свой замок, он проверяет, не открылся ли сейф. Если сейф неправильный (что невозможно по п.1), то ущерба не возникло — письма в нём нет. Если правильный, но не открылся — то второй замок мог закрыть только B, но не почтальон. Ущерба опять нет.

                                                                                                                                    Единственный вопрос — как мог возникнуть сейф с такими свойствами. Откуда A и B знают, что у них ключи от одного и того же сейфа (и почему они не могли сами сделать две копии ключей хотя бы от одного замка).
                                                                                                                                • НЛО прилетело и опубликовало эту надпись здесь
                                                                                                                                  • +3
                                                                                                                                    В случае со шкатулкой (и навесными замками) почтальон может притвориться, что он B — ведь исходно замка ZB на шкатулке нет. А B шкатулки так и не увидит. Или, открыв шкатулку и прочитав письмо, почтальон перевесит свой замок на место ZA, и будет общаться с B от имени A. Тогда вообще никто ничего не заподозрит, пока к влюблённым не нагрянет полиция нравов.
                                                                                                                                    • НЛО прилетело и опубликовало эту надпись здесь
                                                                                                                            • 0
                                                                                                                              В смысле?
                                                                                                                          • 0
                                                                                                                            А замок можно защелкнуть (закрыть) без ключа?
                                                                                                                            • 0
                                                                                                                              Возможно. Там, где я ее нашел, не было решения. Правда я особо и не искал — сам потом попробую решить.
                                                                                                                        • 0
                                                                                                                          Задача номер 3 меня задела.
                                                                                                                          Ну зачем они сказали про потолок? Почему он низкий? Я его трогать, что ли должен? Как это мне поможет узнать, какая лампочка включилась?
                                                                                                                          • +3
                                                                                                                            Там расчет на то, что лампочка будет нагреваться и ее можно потрогать, скорее всего. Что, конечно, совсем не является обязательным (что она будет нагреваться).
                                                                                                                            • +1
                                                                                                                              Если по ней будет идти ток, то она будет нагреваться. Если по ней не будет идти ток, то вы неправильно решали задачу =)
                                                                                                                              • 0
                                                                                                                                Ток может идти очень маленький, и нагрев будет неощутим.
                                                                                                                                Вот впаять в выключатель реле с таймером — это хороший ответ =)
                                                                                                                                • +2
                                                                                                                                  Думаю, все-таки, задачу предполагалось решить, включив два переключателя на время, достаточное для нагрева лампочки. По истечении времени выключаем олин переключатель и топаем во вторую комнату. Будут лампочки: включенная, теплая и холодная.
                                                                                                                                  • +15
                                                                                                                                    Данное решение разбивается в пух и прах хорошими контр-аргументами.
                                                                                                                                    И очень желательно прочитать вот это: blogs.msdn.com/b/ruericlippert/archive/2011/02/28/what-would-feynman-do.aspx
                                                                                                                                    • +1
                                                                                                                                      Уже читал ранее. Сомневаюсь, что на собеседовании ожидались именно такие ответы)
                                                                                                                                      • +3
                                                                                                                                        Вспомнилась байка про Бора и барометр
                                                                                                                                        Сэр Эрнеcт Резерфорд, президент Королевской академии и лауреат Нобелевской премии по физике рассказывал такую историю:
                                                                                                                                        Однажды к нему обратился коллега за помощью. Он собирался поставить самую низкую оценку по физике одному из своих студентов, в то время как тот утверждал, что заслуживает высшего балла. Оба — преподаватель и студент — согласились положиться на суждение третьего лица, незаинтересованного арбитра. Выбор пал на Резерфорда. Экзаменационный вопрос гласил: «Объясните, каким образом можно измерить высоту здания с помощью барометра?».

                                                                                                                                        Ответ студента был таким: «Нужно подняться с барометром на крышу здания, спустить барометр вниз на длинной верёвке, а затем втянуть его обратно и измерить длину верёвки, которая и покажет точную высоту здания».
                                                                                                                                        Случай был и впрямь сложный, так как ответ был абсолютно полным и верным! С другой стороны, экзамен был по физике, а ответ имел мало общего с применением знаний в этой области.

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

                                                                                                                                        Заинтересовавшись, Резерфорд попросил молодого человека приступить к ответу, не дожидаясь истечения отведённого срока. Новый ответ на вопрос гласил: «Поднимитесь с барометром на крышу и бросьте его вниз, замеряя время падения. Затем, используя формулу, вычислите высоту здания».

                                                                                                                                        Тут Резерфорд спросил своего коллегу преподавателя, доволен ли он этим ответом. Тот, наконец, сдался, признав ответ удовлетворительным. Однако студент упоминал, что знает несколько ответов, и его попросили открыть их.

                                                                                                                                        — Есть несколько способов измерить высоту здания с помощью барометра, — начал студент. — Например, можно выйти на улицу в солнечный день и измерить высоту барометра и его тени, а также измерить длину тени здания. Затем, решив несложную пропорцию, определить высоту самого здания.

                                                                                                                                        — Неплохо, — сказал Резерфорд. — Есть и другие способы?

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

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

                                                                                                                                        — Наконец, — заключил он, — среди множества прочих способов решения данной проблемы лучшим, пожалуй, является такой: возьмите барометр с собой, найдите управляющего и скажите ему: «Господин управляющий, у меня есть замечательный барометр. Он ваш, если вы скажете мне высоту этого здания».

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

                                                                                                                                        Студент этот был Нильс Бор (1885–1962), датский физик, лауреат Нобелевской премии 1922 г.
                                                                                                                                  • 0
                                                                                                                                    Ну, не только же лампы накаливания в природе существуют. Там ниже Ogra привел отличную ссылку, кстати =)
                                                                                                                                    • +1
                                                                                                                                      когда была придумана эта задача, лампочки были только вольфрамовые
                                                                                                                                • 0
                                                                                                                                  про потолок сказано, ибо намекнуть, что вы можете дотянуться до лампочек.

                                                                                                                                  А решение простое
                                                                                                                                  1) Включаем первый рубильник на некоторое время.
                                                                                                                                  2) Выключаем первый рубильник и включаем второй.
                                                                                                                                  3) Заходим в комнату. Горящая лампочка — второй рубильник, тёплая лампочка — первый рубильник, холодная лампочка — третий рубильник


                                                                                                                                  Такие задачи в школьные годы решали