Задачи с собеседований. Три адекватные задачки на «подумать»

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


    Задача 1. Проверьте, насколько вы избалованный программист


    Дана упорядоченная последовательность чисел от 1 до N. Из нее удалили одно число, а оставшиеся перемешали. Найти удаленное число.

    С толку сбивает только одна фраза «упорядоченная последовательность», она-то и может натолкнуть на использование сортировки для решения данной задачи. Программисты довольно часто пользуются готовыми библиотеками и фреймворками, поэтому при решении задач автоматом обдумываешь, что будешь использовать из библиотеки. Для многих программистов единственным очевидным решением является сортировка полученной последовательности и далее поэлементное сравнение исходной и отсортированной последовательностей до первого несовпадения. Можно подсчитать сложность такого решения: $O(N log N)$ сложность сортировки плюс линейная сложность поиска. Хм, может подойти к решению как-то иначе?

    Есть более простое решение
    Давайте забудем о том, что последовательность упорядочена. Обе последовательности различаются всего одним числом, а значит, чтобы его найти нужно из суммы элементов исходной последовательности вычесть сумму полученной. И кстати, если все элементы уникальны, то в исходном массиве у нас арифметическая прогрессия и первую сумму можно вычислить как $(a_1+a_n)n/2$.

    Задача 2. Жонглирование числами


    У вас есть пятилитровый и трехлитровый кувшины и неограниченное количество воды. Как отмерить ровно 4 литра воды? Кувшины имеют неправильную форму, поэтому точно отмерить половину кувшина не получится.

    Это моя любимая задачка из разряда «головоломок». С одной стороны нужно немного подумать, а с другой – она действительно проста и адекватна.

    Решение
    Здесь придется немного пожонглировать с простыми числами 5 и 3.

    1. Заполняем трехлитровый кувшин. Переливаем эти 3 литра в пятилитровый кувшин.
    2. Снова заполняем трехлитровый кувшин и переливаем из него в пятилитровый. Помним, что в пятилитровом кувшине сейчас 3 литра, до полного его заполнения из другого кувшина выливается 2 литра. В трехлитровом кувшине остался один литр.
    3. Опустошаем пятилитровый кувшин. Переливаем в него отмеренный один литр. Снова заполняем трехлитровый кувшин и переливаем из него в пятилитровый. Теперь в большом кувшине у нас 4 литра воды.

    Задача 3. Без посредников


    Имеется два числа. Можно ли поменять их местами без использования дополнительной переменной?

    Как потом оказалось, это довольно популярная задачка. Но я решила со значительным недочетом.

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

    Решение
    Пусть у нас есть A и B.

    A = A + B
    B = A – B // После этого B становится A, т.к. в действительности получаем (A + B) – B = A
    A = A – B

    В этом решении есть большой минус: возможность переполнения. Поэтому лучше использовать поразрядную операцию XOR.

    A = A ^ B
    B = A ^ B
    A = A ^ B

    Как это работает: в первой строке мы получаем маску на различающиеся биты, в этих разрядах будут стоять единички. Далее производится сброс и выставление нужных бит для обмена значений.
    На примере будет наглядней. Рассмотрим обмен чисел 5 и 9.

    A = 0101 ^ 1001 = 1100
    B = 1100 ^ 1001 = 0101
    A = 1100 ^ 0101 = 1001

    Осталось только пожелать всем успешных собеседований!

    А в комментариях можете написать, какие задачи встречались вам.
    Share post
    AdBlock has stolen the banner, but banners are not teeth — they will be back

    More
    Ads

    Comments 257

      +25
      Дана упорядоченная последовательность чисел от 1 до N. Из нее удалили одно число, а оставшиеся перемешали. Найти удаленное число.


      В первой странная постановка задачи. Нигде не говорится, что оригинальная коллекция доступна.
      Вначале думаешь что доступна только измененная коллекция. И ни про какие суммы и вычитания не думаешь.
        +5
        Кому как, я сразу про сумму подумал. Формулировка похожа на школьные задачки, там такого было полно.
          0
          Ок, так и запишем, задача на тренированность читать условия школьных задач.
          0
          Согласен с Вами.
            +7

            Ещё не сказано, что в коллекции ровно N чисел и нет повторений ,) Ессно, на реальном собеседовании на уточнение достаточно 10 секунд

              +5
              Еще не сказано что это целые числа.
              0

              Первая коллекция недоступна — Вы имеете ввиду, что N неизвестно? Это почти никак не меняет решение.

                +4

                Вот вам последовательность, в соответствии с условиями задачи. 1 500 99999999


                Какое число изьяли?

                  0

                  Не соответствует условию. Если вы предполагали, что N равно трем, то "упорядоченная последовательность чисел от 1 до N" это: 1, 2, 3.

                    +7
                    Почему не соовтетствует?
                    Если N=3, то чем упорядоченная последовательность чисел от 1 до N это например не 1,3, или 1,1,3?
                      +7
                      упорядоченная последовательность чисел от 1 до 3 может быть такой
                      1 1 1
                      1, корень из двух, 2
                      или просто 1 ( это тоже упорядоченная последовательность числе от 1 до 3 )
                      ну и удачи в поиске решений
                        –2
                        Это зависит от того, как сформирована последовательность :-)

                        Если N_{i+1} = N_{i}+1 — то да.
                        Но можно же и, например, N_{i+1} = N_{i} + 2*i :-)

                        Хотя, по умолчанию я бы считал первое — но это, ИМХО, вопрос заслуживающий уточнения.
                          +2

                          Ну, "последовательность чисел от 1 до N", это, если не задано дополнительных условий, записанные последовательно числа от 1 до N. Да, разумеется, можно докапываться каждого слова в поисках скрытых смыслов, то можно напридумывать много чего. Но это всё из серии, — а если бы он вёз патроны… Зачем ввдумывать сущности без необходимости?
                          Зы. Ваш случай, кстати, вообще не подходит под формулировку. Значения чисел из набора довольно быстро превысят N.

                            0
                            «Ваш случай, кстати, вообще не подходит под формулировку. Значения чисел из набора довольно быстро превысят N»
                            С чего бы? N — значение последнего элемента в наборе же.
                              0

                              Э? N{i+1} = N{i} + 2i
                              пусть N=3, "последовательность чисел от 1 до 3" в вашем случае будет такая:
                              { 1, 1+2
                              1, 3+2*2 } => {1, 3, 7} Не?

                        +4

                        Фраза "упорядоченная последовательность чисел от 1 до N" в тексте математических задач должна читаться как 1, 2, ..., N, а не как "упорядоченная последовательность чисел, принадлежащих отрезку [1, N]". Для этого есть два основания:


                        1. При втором варианте прочтения не определяется тип чисел (целые, рациональные, действительные). В первом варианте прочтения считывается тип "целые положительные".
                        2. При втором варианте прочтения не обозначается сколько этих чисел. В первом варианте прочтения считывается, что их ровно N.

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

                          0
                          В hpmor.ru, глава 8 в первой встрече Гарри и Гермионы была полностью раскрыта тема как плохо люди трактуют условия задачи. Именно на последовательностях чисел.
                            +1

                            Пол главы написано ради одного предложения.


                            Суть

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


                            Здесь же введение условий, которых нет в задаче.

                      +4
                      В первой странная постановка задачи. Нигде не говорится, что оригинальная коллекция доступна.
                      Вначале думаешь что доступна только измененная коллекция. И ни про какие суммы и вычитания не думаешь.

                      Это проблема многих подобных задач:
                      Не оговариваются условия и допустимые операции.


                      Исходная коллекция доступна или же вначале она копируется, или из копии удаляется число?
                      А если не копируется, можно ли перед ее модифицикацией провести немодицицирующие вычисления (получить сумму?)
                      А числа у нас как в математике — без переполнения, или с переполнением (а при переполнении креш, или просто переполнение — которое может быть и вполне допустимо при решении задачи)?


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


                      Кстати, в задаче про взвешивание 8 монет тоже есть подвох — т.к. для 8-ми монет для минимального кол-ва взвешиваний, монеты нужно взвешивать по 3, то из 9 монет, монета с отличным весом будет найдена за то же число взвешиваний, что и 8.
                      И кстати, что есть взвешивание (число которых нужно подсчитать)? Если мы взвесили 3 + 3 монеты, и потом начинаем взвешивать монеты их тройки, где есть дефектная, то получается, часть монет взвешивается дважды.
                      Такая операция (повторное взвешивание) допустима в задаче? Если да — то, повторное взвешивание одной и той же монеты увеличивает счетчик взвешиваний или нет?


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


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


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

                      +31
                      Вторую задачу можно решить и другим способом.

                      1. Наполнить пятилитровый кувшин водой
                      2. Из пятилитрового кувшина наполнить трёхлитровый кувшин (в пятилитровом останется 2 литра воды)
                      3. Вылить всю воду из трёхлитрового кувшина и перелить 2 литра воды из пятилитрового кувшина.
                      4. Наполнить пятилитровый кувшин водой
                      5. Наполнить заполненый на 2 литра трёхлитровый кувшин водой из полного пятилитрового кувшина (потребуется 1 литр воды)

                      В итоге, в пятилитровом кувшине останется 4 литра воды.
                        +22
                        Я точно так же решил и у нас с вами 6 действий, а не 8, как у автора :)
                          +5
                          И я почему-то тоже сразу по такому пути пошел
                            +6

                            И объём вылитой воды меньше.

                              0
                              Зато объем потребления воды больше.
                              В случае решения ТС идет 3 раза заполенние по 3 литра и 1 раз выливание 5 литров.
                              В случае решения выше получаем 2 заполнения по 5 литров (на литр больше) и одно выливание 3 литров
                                0
                                У нас же неограниченное количество воды. Тут либо быстрей алгоритм, либо меньше воды.
                            +10

                            Нет условия "пользоваться только кувшинами". Потому:


                            1. Наливаем 5 литровый кувшин
                            2. Отливаем 3 литра во второй.
                            3. Оставшиеся 2 литра сливаем в target.
                            4. Повторяем :)
                              +24
                              Если можно пользоваться чем то еще — то ваш вариант крайне не спортивен :)
                              1. Наливаем 5-и литровый кувшин
                              2… (тут что угодно: запой, распилы, откаты, etc)
                              3. Берем кучу камней. Проводим экспертизу для определения их плотности.
                              4. Рассчитываем необходимую массу камней для заполнения объема в 1 кубический дециметр.
                              5. Берем весы, отмериваем необходимое кол-во камней.
                              6. Вываливаем камни в кувшин (как мы помним — наливали в 5-и литровый). По закону Архимеда камни вытесняют необходимое кол-во (1л) воды из кувшина.
                              7. profit! На вопрос — какого х*я в воде камни — делаем круглые глаза и говорим, что в условиях задачи ничего не сказано о том, что вода должна быть чистой. Просим еще денег на очистку воды от камней.
                                +12
                                В менеджеры!
                                  0
                                  Так задача — отмерить. Мы вылили ровно четыре литра воды.
                                    0
                                    Нет, мы _пролили_ 1 кубический дециметр (а это и есть литр, если кто не в курсе) воды, заместив его равным количеством камней. Кувшин объемом 5 литров по прежнему полон, НО содержит 4 л. воды, что соответствует условиям задачи. Если же эта вода далее нужна для чего то еще — нет гарантии, что с водой не получим какое то количество камней. Или наоборот: нам в этом кувшине нужен свободный объем 1 л. для добавления чего то еще — а места то и нет.
                                    А если без шуток, перенося на програмерский быт: такие вещи встречаются сплошь и рядом, называются они красивым словом «костыль».
                                      0
                                      Мы немного о разном. В условиях не только не сказано, что можно пользоваться чем-то еще ( камнями и т.п.), там еще и не сказано, что отмеренные четыре литра должны остаться в одном из кувшинов.
                                0
                                Помнится, в университете проходили универсальный метод «математического бильярда», при помощи которого можно решать подобные задачи для любых размерностей сосудов и искомого количества оставшейся воды.
                                  +1
                                  Решил так же…
                                    0
                                    А у меня сразу мыль была, что нужно наполнить оба сосуда до верха, потом наклонить и вылить воду так, чтобы нижний край горла и верхний край дна были параллельны земле.
                                    В итоге получаем в 3-литровом сосуде 1,5 литра, а в 5-литровом 2,5 литра.
                                    Переливаем из трехлитрового в пятилитровый и у нас получилось 4 литра.
                                      +2

                                      Форма сосуда по условиям неправильная. А ваш вариант не пройдёт с любой даже правильной формой, если горло и основание имеют разную форму. Простейший вариант такой правильной формы — конус, горлышком является основание: вы просто выльете всю воду.

                                    0
                                    В Задаче 1, если обе последовательности доступны, то, как вариант, можно решить линейно. Пробежаться по отсортированному списку и сравнивать с i-1 — ым элементом отсортированного. По идее это должно получиться оптимальнее решения предложенного автором.
                                      +4
                                      Оптимальнее? Вы шутите? Т.е. сначала потратим время на сортировку, потом умножим на два занятую память, а потом проведем N сравнений, это оптимизация? Вместо того, чтобы взять n(n+1)/2 и вычесть из него все имеющиеся числа, и в остатке получить ответ.
                                        +1
                                        Нет, оптимальнее того, что было предложено изначально как решение. Но и тут я не прав. Мне почему-то показалось, что у нас доступна отсортированная последовательность и хотел предложить как вариант.
                                        +1
                                        Вы забываете что она ещё и пермешана так что не выйдет
                                          +1
                                          где оптимальнее-то? в решении автора всего один цикл от 1 до n и единичные арифметические операции. У вас — вложенные циклы и n^2 операций сравнения. или я не понял что вы предлагаете.
                                            0
                                            В решени автора логарифм и линейный обход. А у меня только линейный. Но я ошибься, последовательность даётся только одна, неотсортированная, поэтому мой вариант отпадает.
                                              0
                                              Простите, мы говорим о решении автора, от том, что под спойлером, так? Там один цикл от 1 до n-1, в котором считаем сумму Sum элементов перемешанного массива. Искомое число будет
                                              x = (1 + n) * n / 2 — Sum

                                                0
                                                Я подразумевал решение, которое было в основном тексте, пол самой задачей. Но я в любом случае не прав.
                                          +11
                                          Вторую задачу решает Брюс Виллис
                                            –2
                                            Мне для первой задачи первым всплыло решение брутфорсом. Берём 1 — ищем в последовательности; Берём 2 — ищем; Берём 3 — ищем… берём 34234 — не находим.
                                              +1

                                              ммм… квадратичная сложность.

                                                0
                                                Мне тоже всплыло, только сложность — N^2.
                                                +1

                                                задачки очень простые и легко решаемы, особенно если прорешивали кучу подобных задач в школьные/университетские годы
                                                Мне пока самое сложное, что попалось — это задачка посчитать количесво вагонов в составе
                                                Условие: есть состав вагонов, закольцованный, можно переходить от вагона к вагону, в обоих направлениях. Скажем, что окна закрыты и видите только текущий вагон.
                                                В каждом вагоне определено понятие света — горит или нет
                                                У Вас, при заходе на очередной вагон, есть две возможности: посмотреть, горит ли в этом вагоне свет, и включить/выключить свет(без ограничений)
                                                Вопрос: как посчитать точное количесто вагонов с наименьшим количеством их посещений?

                                                  0

                                                  Включаем свет в том вагоне, в который зашли. Идёми считаем, пока не дойдём до вагона с включенными светом. А как ещё?

                                                    +4

                                                    А теперь представьте, что в вагонах состояние свет включен/выключен изначально случайное.

                                                      +1

                                                      именно так и есть, забыл в условии это написать

                                                        +3

                                                        Это просто отвратительно со всех точек зрения, кроме олимпиадной задачи :) но в этом случае задача не имеет решения на бесконечном количестве вагонов.

                                                          0
                                                          Так на бесконечном количестве вагонов и не предполагается искать точное количество вагонов)) Вопрос то стоял так:
                                                          Вопрос: как посчитать точное количесто вагонов с наименьшим количеством их посещений?
                                                          И этом случае самый банальный подход — сначала включить/выключить везде свет, и дальше по накатанной схеме
                                                            +2
                                                            А как вы поймёте что свет везде включен?
                                                              0
                                                              А как определить, что мы выключили свет во всех вагонах?
                                                                0
                                                                Чёрт. А об этом я как-то даже не подумал.
                                                          0

                                                          … Не, я знаю, что переменные положено инициализировать. Но все же..

                                                          +1

                                                          Нормальная олимпиадная задача. Правда, не скажу за какой класс ,)

                                                            0
                                                            в вагоне с которого начинаем — выключаем свет, во всех остальных — включаем свет. Чтобы точно убедится в правильном кол-ве вагонов: придётся сделать 2 круга.
                                                              0

                                                              Изначално все вагоны случайном образом проинициализированы(включен свет или выключен)
                                                              понятия круг не существует
                                                              для Вас это как List<вагон>. Вы можете только next(), prev().
                                                              Чтобы "сделать круг", надо понять, что Вы дошли опять туда, где и были. Все вагоны — идентичны, не отличаются друг от друга, поэтому круг сделать не получится

                                                                0

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

                                                                  –1

                                                                  ближе к ответу)
                                                                  решение есть, и да, количество вагонов в составе — конечное

                                                                    –1
                                                                    Решения нету, тоже самое что идти по числу пи в двоичном виде, как бы мы не закодировали наше начало, не факт что дальше не будет такого же кода еще бесконечное число раз, даже если количество и кончено оно все равно может стремится в бесконченсоть.
                                                                    Да даже если мы будем запоминать весь наш код и встретим его 50 раз думая что идем по кругу, не факт что дальше на 51 раз будет что то другое.
                                                                      +2
                                                                      Решение есть. Идем, гасим свет и считаем вагоны. Если дошли до вагона с выключенным светом — включаем в нем свет и идем назад на то количество вагонов, которое насчитали (т.е. в тот вагон с которого начали). Если в нем свет горит, значит это в нем мы его включили и решение найдено, если нет, то снова идем в перед до того вагона в котором включили свет продолжаем от него.
                                                                        –2
                                                                        Например, при начале обработки последовательности с 20(+)20(-)1(+)n(±) ваш вариант ломается.
                                                                        Для достоверного решения задачи необходимо иметь ограничение типа 2^(n-1)>x>2^n. Зная n
                                                                        решение возможно. Иначе — вилами по воде. Тащемта.
                                                                          0
                                                                          Вот прям даже не знаю что ответить. Или вам Серёженька не нравится, например?
                                                                    +4

                                                                    При бесконечном числе вагонов задача на их подсчёт как-то теряет смысл. :)

                                                                    0
                                                                    «круг» — это наш логический круг с 1м найденным вагоном в котором свет выключен.
                                                                    Если мы найдём ещё один вагон с выключенным светом — значит обнуляем счёт, включаем свет на предыдущем и начинает отсчитывать вагоны с новой точки(с выключенным светом)
                                                                  +7

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

                                                                    +2

                                                                    ага, верное решение, за O(N^2) в худшем случае

                                                                      +4

                                                                      За O(N log N) есть решение. Основная идея та же. Изначально k=1. Включаем свет в первом вагоне. Идем вправо k шагов, гася свет во всех вагонах. Возвращаемся назад, сколько прошли. Если свет погас в первом вагоне — Ясно что всего их не больше k, переходим ко второй фазе. Иначе, мы знаем, что вагонов больше k. Умножаем k на 2 и повторяем все сначала.


                                                                      Вторая фаза — мы уже знаем, что вагонов больше k/2, но меньше k+1. Бинарным поиском в этом промежутке ищем минимальное i такое, что сделав i шагов вправо, гася везде свет, мы выключим свет и в первом вагоне тоже.


                                                                      Каждая итерация пройти вправо выключая свет и вернуться назад не более 4N шагов (потому что мы не будем проверять k>2N иначе бы k/2 подошло уже). Всего итераций логарифм N найти минимальный k и еще один логарифм на бинарный поиск.

                                                                        0
                                                                        Кажется, что можно обойтись без бинарного поиска во второй фазе. Если k больше реального числа вагонов, то по дороге обратно мы в какой-то момент пройдём через вагон, в котором мы переключили свет, то есть по дороге «туда» надо записывать состояние света в каждом пройденном вагоне, а по дороге «обратно» после переключения света в k-ом вагоне считать вагоны и сверяться со списком. Первый вагон, в котором свет не совпал — это тот вагон, с которого мы начинали обратный обход, всё, мы знаем, сколько вагонов.
                                                                          0
                                                                          Список означает, что вы используете дополнительную память. Задачу можно решить за O(n) операций и O(1) дополнительной памяти. Фактически кроме пары переменных и выключателей в вагонах ничего не нужно.

                                                                          Мое решение (псевдокод)
                                                                          class Train:
                                                                          	set(on/off) # включить/выключить свет в текущем вагоне
                                                                          	test(on/off) # свет горит/не горит
                                                                          	left() # идем налево
                                                                          	right() # идем направо
                                                                          
                                                                          function get_train_length:
                                                                          	k = 1
                                                                          	set(on)
                                                                          	while test(on):
                                                                          		k = k*2
                                                                          		for i in 0..k:
                                                                          			right()
                                                                          			set(off)
                                                                          		for i in 0..k:
                                                                          			left()
                                                                          	
                                                                          	# теперь свет нигде не горит, и мы в вагоне, в котором начали
                                                                          	set(on)
                                                                          	right()
                                                                          	count = 1
                                                                          	while test(off):
                                                                          		count = count + 1
                                                                          		right()
                                                                          	
                                                                          	return count
                                                                          



                                                                          В моем решении в худшем случае придется сделать не более 9n переходов между вагонами (т.е. все равно О(n)), и кроме пары счетчиков дополнительной памяти не нужно, то есть O(1) дополнительной памяти. Возможно, можно оптимальней.
                                                                    0
                                                                    Я могу пользоваться скотчем, стикерами и авторучкой?
                                                                      0

                                                                      да, но нельзя помечать вагоны, можете себе на лоб допустим приклеить))
                                                                      скотчем замотать себе что-нибудь)
                                                                      ЗЫ: что-то меня поперло, простите)

                                                                      –2

                                                                      Если считать, что свет в вагонах инициализирован случайным образом, сходу подумалось о том, чтобы искать самую длинную повторяющуюся последовательность в свете вагонов, таким образом можно найти с некоторой долей вероятности повтор за 2*N вагонов, и увеличивать уверенность в результате за большее количество кругов. Но, с другой стороны, это не сработает, если у вагонов паттерн света повторяется. Мы можем менять один бит в паттерне, как только мы его обнаружили, и начинать отсчет от этого вагона, и идти вперед, пока мы не обнаружим паттерн с измененным битом. Но это не сработает, если поезд "умный" и знает о нашей стратегии, и неизведанные вагоны повторяют наш предыдущий паттерн, каким бы он ни был — поэтому вводить случайную компоненту бессмысленно. Плюс у такого решения очень неоптимальные затраты по памяти — нужно хранить весь трек, и еще и считать автокорреляцию для каждой из промежуточных позиций.


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


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


                                                                      У меня некоторые трудности с тем, чтобы определить временную сложность этого алгоритма, но время растет медленнее, чем O(N^2), но быстрее, чем O(N * log(N)). Сложность по памяти такого решения — O(1).

                                                                        +1

                                                                        Минусы, потому что я где-то ляпнул очевидную глупость, и сам того не заметил? Или метод решения не подходит под условия задачи?

                                                                        0
                                                                        Хм… идем, включаем/выключаем свет в какой-то чередующейся последовательности(идеально — 01...01 ). Так как вероятность наткнуться на такую же последовательность уменьшается вдвое с каждым пройденным шагом, то, наткнувшись на такую же последовательность, проходим такое же число вагонов N. Если последовательность не поменяется еще за N вагонов, то длина поезда с вероятностью 2^n/(2^n -1). Т.е. всего два прохода :-)
                                                                          +1

                                                                          Если вагонов будет четное количество и последние 2 вагона будут иметь состояние 0 и 1, то мы посчитаем неправильно.
                                                                          Например 10 вагонов: хх хх хх хх 01.
                                                                          Пройдя 8 вагонов, получим такое состояние: 01 01 01 01 01.
                                                                          Пройдя еще 8 вагонов, убедимся, что последовательность повторяется, и будем считать, что что вагонов всего 8.
                                                                          Ошибемся с вероятностью 1/4.

                                                                            0
                                                                            в принципе, да. Я уже потом подумал, что последовательность должна быть не повторяющейся.
                                                                        –5
                                                                        Мне, когда задают подобную чушь, сразу хочется встать и уйти.
                                                                          +6

                                                                          Только хочется, или таки уходите? Если первое, то глупо, что вы это здесь говорите, если второе, то глупо, что вы это делаете.

                                                                          +1
                                                                          Спасибо, надеюсь выйдут еще подобные статьи… Будет чем развлечься, а то мозг иногда прикипает, а так и хабр почитал и мозг размял немного
                                                                            0
                                                                            Можно подсчитать сложность такого решения: логарифмическая сложность сортировки

                                                                            Это как? Расскажите, мне интересно, как вы потеряли сравнение с каждым элементом (и, соответственно, N log N в результате).

                                                                              0
                                                                              Третья задача в python:
                                                                              A, B = B, A
                                                                                0

                                                                                А вот вопрос, сколько промежуточных переменных создается при выполнении этой операции. Мне кажеться, что их там чуть ли не 2 лишних будет. И присваиваний там 4, наверно, вместо 3-х для стандартного с одной переменной или с XOR.

                                                                                  +3

                                                                                  Я тут посмотрел на «дизассемблер», получается, что я не прав: для функции


                                                                                  def foo(a, b):
                                                                                      a, b = b, a
                                                                                  
                                                                                  from dis import disassemble as da

                                                                                  дизассемблер (da(foo.__code__) для Python 3.4.5, da(foo.func_code) для 2.7.12) выдаёт


                                                                                    2           0 LOAD_FAST                1 (b)
                                                                                                3 LOAD_FAST                0 (a)
                                                                                                6 ROT_TWO             
                                                                                                7 STORE_FAST               0 (a)
                                                                                               10 STORE_FAST               1 (b)
                                                                                               13 LOAD_CONST               0 (None)
                                                                                               16 RETURN_VALUE

                                                                                  Т.е. кортеж оптимизатор убрал. Но если считать за «присваивания» те операции, которые вызывают инкремент/декремент счётчика ссылок, то их тут действительно четыре — LOAD_FAST вызывает инкремент загружаемого объекта, STORE_FAST вызывает декремент у объекта, который перезаписывается. Считать, сколько там внутренних временных переменных будет использовано, по‐моему, нет смысла, да и сложно: к примеру, я не удивлюсь, если окажется, что компилятор превращает код ROT_TWO (использующий две временные переменные) в три xor. А вот манипуляции со счётчиком ссылок вряд ли куда‐то денутся.

                                                                                  +2

                                                                                  Ага. Только не забывайте, что в вашем примере участвуют две переменные, но три объекта (A, B и кортеж B, A).

                                                                                  +4
                                                                                  А мне предложенный способ решить первую задачу решительно не нравится с технической точки зрения, сумма может выйти за пределы разрядности например.
                                                                                  В таком случае можно сумму заменить на XOR.
                                                                                  так как A XOR A == 0, и XOR ассоциативная операция, то можно посчитать XOR между элементами из массива и XORнуть её с 1..N
                                                                                  Влоб это будет конечно дольше чем если вычислить сумму по формуле.
                                                                                  Кстати, интересно бы попробовать вывести формулу для суммы по модулю 2, сдается мне она не будет шибко сложной…
                                                                                    0
                                                                                    А мне предложенный способ решить первую задачу решительно не нравится с технической точки зрения, сумма может выйти за пределы разрядности например.
                                                                                    Может. Но получите ли вы в этом случае неверный ответ?

                                                                                    Кстати, интересно бы попробовать вывести формулу для суммы по модулю 2, сдается мне она не будет шибко сложной…
                                                                                    Ээээ… Вы тут вообще о чём тут говорите?
                                                                                      0
                                                                                      1) Если сумма посчитана по формуле суммы арифметической прогрессии — вполне вероятно что с учетом переполнения ответ не совпадет.
                                                                                      2) XOR, он же сумма по модулю 2. Вопрос был в том что существует формула для быстрого вычисления суммы арифметической прогрессии, и я высказал идею что вполне себе просто должна выводиться аналогичная формула для побитового XOR арифметической прогрессии.
                                                                                      Собственно пятью минутами после того как я написал сообщение я её вывел, но написать уже не смог, ограничение read-only аккаунта :(
                                                                                      Собственно ответ тов. Nostr чуть ниже совпадает с тем что получил я
                                                                                        0
                                                                                        Если сумма посчитана по формуле суммы арифметической прогрессии — вполне вероятно что с учетом переполнения ответ не совпадет.
                                                                                        Хорошее замечание и хороший допворос — как посчитать так, чтобы совпадало.

                                                                                        Собственно ответ тов. Nostr чуть ниже совпадает с тем что получил я
                                                                                        Понял. Да, хорошая идея.
                                                                                      +2
                                                                                      Можно не считать XOR последовательности от 1 до N, а воспользоваться следующим выражением:
                                                                                      int xor(int n)
                                                                                      {
                                                                                          if (n % 4 == 0)
                                                                                              return n;
                                                                                       
                                                                                          if (n % 4 == 1)
                                                                                              return 1;
                                                                                       
                                                                                          if (n % 4 == 2)
                                                                                              return n + 1;
                                                                                       
                                                                                          return 0;
                                                                                      }
                                                                                      


                                                                                      Подробнее: stackoverflow

                                                                                      Или можно ещё проще: 1 ^ ... ^ n = (n >> 1) & 1 ^ (n&1 ? 1 : n)
                                                                                      +1
                                                                                      Решение первой задачи без перерасхода памяти. Из условия дано, int N и int[N-1] a
                                                                                      int value = N
                                                                                      for(int i = 0; i<N-1; i++ ){
                                                                                      value = value + i - a[i]
                                                                                      }
                                                                                        0
                                                                                        А вот идеальное решение первой задачи нужно xor все элементы массива между собой и ещё с N полученный результат и будет искомое число
                                                                                        int value = N
                                                                                        ...
                                                                                        value = value xor a[i]
                                                                                          +1
                                                                                          Что-то я не въезжаю в Ваше решение:
                                                                                          N = 4
                                                                                          V = 4
                                                                                          было 1, 2, 3, 4 стало 4, 1, 2 (после перемешивания)
                                                                                          V = v + 0 — 4 // 4+0-4=0
                                                                                          V = v + 1 — 1 // 0+1-1=0
                                                                                          V = v + 2 — 2 // 0+2-2=0
                                                                                          4й раз цикл не прогнать, т.к. a[i] не доступно!
                                                                                          Или я что-то напутал?
                                                                                            0
                                                                                            В первом решении ошибка на +1, это нормально при решении на бумажке
                                                                                            V = V + i — a[i] + 1
                                                                                            V = 4
                                                                                            4 + 0 — 4 + 1 = 1
                                                                                            1 + 1 — 1 + 1 = 2
                                                                                            2 + 2 — 2 + 1 = 3
                                                                                          +1
                                                                                          В этом решении есть большой минус: возможность переполнения. Поэтому лучше использовать поразрядную операцию XOR.

                                                                                          В первом и втором способах есть свои плюсы и минусы. Минус для первого указали, а для второго — нет. Например, второй способ не подойдет для float/double.
                                                                                            +4

                                                                                            xor вполне себе подойдёт для float и double, только кода будет больше, чтобы убедить компилятор делать побитовый xor на double «как если бы это было просто N‐битовое беззнаковое целое». А вот арифметические операции для float и double не подойдут совсем. Подумайте, что будет, если в одном или другом числе окажутся такие интересные значения, как +∞, −∞, NaN (кстати, NaN может быть тоже два варианта). Или в одном числе будет 1 × 10100, а в другом — 1 × 10−100.

                                                                                              +2
                                                                                              xor вполне себе подойдёт для float и double, только кода будет больше, чтобы убедить компилятор делать побитовый xor на double «как если бы это было просто N‐битовое беззнаковое целое».
                                                                                              В этом случае и первый алгоритм будет работать, однако. И проблем с переполнением в нём, внезапно, не станет.
                                                                                                0
                                                                                                Зачем так сложно? Есть инструкция процессор XCHG, тогда уж. :-)
                                                                                                  0
                                                                                                  Векторной версии нету.
                                                                                                0

                                                                                                Второй способ не подходит, если данные разной размерности (т.е. например, одна переменная float, вторая double), при этом можно их складывать с потерей точности. Что интересно, в случае целочисленных типов ксорить будет правильно, если более длинный тип привести к правильному размеру, правда, старшие биты придется занулить вручную.

                                                                                                –1

                                                                                                Хотите мозговыносной вариант задачи? Дано две бочки по 20 литров. Обычные типичные дубовые бочки. Требуется: пользуясь только ими, отмерять 10 литров. Не "на глазок" естественно. Бонус поинтс тому, кто не прольёт ни капли.
                                                                                                Это не подстава, задача решаема.

                                                                                                  0
                                                                                                  налить одну полную и переливать во вторую до тех пор, пока будучи наклоненной уровень воды не окажется одновременно у противоположных краев дна и поверхности, в итоге будет по 10 в каждой
                                                                                                    0

                                                                                                    Налить полностью одну, потом переливать из нее во вторую, пока уровни не сравняются.

                                                                                                      +2

                                                                                                      Начать с одной полной и одной пустой, соединить шлангом, подсосать и сделать сообщающиеся сосуды, уровни воды выравняются и получим по десять литров

                                                                                                        0
                                                                                                        А откуда взялся шланг?
                                                                                                          +1
                                                                                                          Ключевое слово: подсосать…
                                                                                                      0
                                                                                                      По поводу третьей задачи. В некоторых языках можно делать так:
                                                                                                      a = [b, b = a][0];
                                                                                                      

                                                                                                      Правда, доп. переменная всё равно создаётся в памяти. Но не в языке.
                                                                                                        +1

                                                                                                        Есть техника "переминования переменных" Если переменные в регистре то компилятор может просто отбросить swap и просто изменить внутреннее представление. Если в памяти и в регистре то xchg в один такт наш все :). Если оба в памяти то задача не решаема на типовых x86, x86-64.

                                                                                                        +2

                                                                                                        Эм, а что, где-то еще предлагают такие задачи? Это же для джунов.

                                                                                                          0
                                                                                                          Только не смейтесь, но эту задачу дали моему знакомому, который собеседовался на старшего программиста. Обойдемся без указания компании, но название всем известное
                                                                                                            0
                                                                                                            На самом деле как раз у «сеньоров» такие задачи и вызывают проблемы зачастую. Любой грамотный школьник их, как бы, должен решать, но если человек «засеньорил» настолько, что посление, скажем, три года не писал кода вообще — то у него будут проблемы.
                                                                                                              0
                                                                                                              Такое вообще может быть? Он же все таки программист, а не тимлид/ менеджер.
                                                                                                                0
                                                                                                                Это вакансия у нас для программиста, а люди приходят разные. Некоторые считают, что если они 10 лет назад код «во сне» могли написать, то и сейчас смогут. Не смогут, увы, навыки теряются.

                                                                                                                Я в своё время на Turbo Pascal мог сделать вообще всё. Вплоть до того, что знал что и где поправить чтобы стандартная библиотека и Turbo Vision с руссими буквами работали. Но если меня сейчас писать на нём программу писать… придётся не один месяц привыкать.

                                                                                                                А если человек прекращает программировать совсем — то вернуться назад ещё сложнее. Но многие — этого не осознают, увы. Отсюда и берутся подобные задачки на собеседованиях. Как первичный фильтр, не более. Будет глупо решать — брать кого-то или нет только на основании таких задачек. Но «для разминки» они как раз подходят — а дальше можно плавно перейти на разные типы данных кеши, компиляторы и прочее, прочее, прочее.
                                                                                                                  –3
                                                                                                                  Знание Turbo Pascal на уровне God вряд ли сильно поможет в программировании на любом другом языке.
                                                                                                                    +4
                                                                                                                    Решительно не соглашусь. Программист, особенно хороший программист, это в первую очередь образ мышления. Навыки выделения алгоритма из словесного описания задачи, разложение этого алгоритма на тот набор «элементарных» операций который доступен, поиск оптимальных структур данных для задачи, понимание о-нотации, дискретная математика. Эти навыки в целом общие для любых языков программирования.

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

                                                                                                                    В общем, такие вот задачки по мне — вполне себе позволительная вещь даже на собеседования синьоров, но конечно не все собеседование из них состоит. Для толкового человека это будет «разминочка», возможность почувствовать себя в своей тарелке. Хотя если человек приходящий на должность синьора такую задачу не щелкнет или того хуже будет в качестве решения первой задачи предлагать O(N^2)… Я бы все таки задумался, это ведь должен быть человек самостоятельно принимающий технические решения, не бегающий проконсультироваться с начальником на каждый чих. Понастроит ведь потом велотренажеров
                                                                                                                      –1
                                                                                                                      Программист, это в первую очередь образ мышления.

                                                                                                                      Я и не возражал ;). Я считаю, что знание, даже, офигенное, какого-то одного языка/фреймворка/IDE никак не связано с образом мышления.

                                                                                                                        0
                                                                                                                        Тут видимо мы по разному воспринимаем слово «знание». Для меня «знание одного языка» == способности на этом языке написать все что угодно. Т. е. человек уже собаку съел в программировании на этом языке.
                                                                                                          0
                                                                                                          Давно интересно почему на собеседованиях проверяют умение думать, но не проверяют способности к планированию и самоорганизации.

                                                                                                          Безусловно хорошо если человек может решить задачу тремя разными способами 2 из которых никто кроме него не придумал, но если бы у меня был выбор: работать с командой из очень талантливых и творческих оболтусов или же с командой которая пишет нормальный код (нормальный это понятный блин, а не короче на 3 строчки чем у соседа) и делает это в срок — я бы даже думать не стал.
                                                                                                            +3

                                                                                                            Тут такой момент — если человек не дурак, то научить его писать понятный код — можно. Если дурак, то научить его самостоятельно решать проблемы — проблемно. :-) Другое дело, что головоломки слабо коррелируют с сообразительностью: глупый мог знать ответ, умный мог не допереть за отведённый срок.

                                                                                                              –4

                                                                                                              Извините, не понял зачем вы это мне написали.

                                                                                                            0
                                                                                                            В первой задачке 9 из 10 нормальных обычных людей посчитает что исходная последовательность недоступна.

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

                                                                                                            И следовательно, возможно, он будет сношать мозг окружающим своей «точностью формулировок» вместо того чтобы засовывать свое чувство превосходства куда нибудь подальше и сосредоточиваться на том чтобы сделать дело.
                                                                                                              0
                                                                                                              > В этом решении есть большой минус: возможность переполнения.

                                                                                                              А что за переполнение такое? У нас же в условиях нет ограничений на память/разрядность/и т.д.
                                                                                                                0
                                                                                                                Да много их. Про альпиниста и веревку, про утку и лису, про лампочки и стоэтажный небоскреб…
                                                                                                                  +1
                                                                                                                  По первой задаче есть замечание: сортировка Counting sort, которая туда просто сама просится, никак не NlogN займет, а N по времени, и N по памяти.
                                                                                                                    +2
                                                                                                                    Нет никакой проблемы, что в первой задачке программист не заметил простого решения ибо обычно таких халявных условий в жизни не бывает. А если так и случается, то программист находится в контексте и знает куда копать. Или заказчик ставит условия объясняет это нюанс. В любом случае, это не повод чтобы отсеять претендента если он просто не заметил подвоха.
                                                                                                                      0
                                                                                                                      Полностью поддерживаю. Не хочется здесь устраивать споры «кто прав», но частенько именно так происходит отсев, возможно, кому-то действительно важно уметь решать подобные задачи.
                                                                                                                      +12
                                                                                                                      Меня всегда в таких задачках напрягает их оторванность от реальности. Они, конечно, неплохо подойдут как «тема для разговора» на собеседовании, но делать прямое соответствие «кол-во правильных ответов — шанс на приём» я бы крайне не рекомендовал. Потому что в реальности многие эти «решения» неприменимы и ущербны.

                                                                                                                      Поясню мысль.
                                                                                                                      Первая задачка (с последовательностью без числа) в реальности может встретиться, например, при работе с БД. Есть список каких-то записей (юзеры, товары, транзакции — не важно), у них есть ID от 1 до N (autoincrement), есть некая функция, которая их удаляет, нам нужно узнать, что было удалено.
                                                                                                                      Тут стоит заметить, что во-первых, обычно используется не удаление, а установка какого-нибудь status: disabled (или установка null в поле, если прямо так необходимо избавится от информации). Удаление может вызвать кучу проблем и головной боли в последствии, не надо так.
                                                                                                                      Во-вторых, обычно всё-таки не должно возникать ситуации «у нас в БД что-то пропало, неизвестно что». ID удалённого объекта должен записываться в момент удаления и обрабатываться сразу же.
                                                                                                                      Но ок, допустим, какое-то вероисповедание нам не позволяет исключить возникновение такой ситуации. Тогда в-третьих: даже если мы делаем проверку суммы сразу после удаления чего-то, никогда нет гарантии, что в самом деле что-то было удалено, или что была удалена только одна запись. Даже если сегодня это так, завтра функцию могут переписать.
                                                                                                                      В итоге, человек, который считает, что ответ с суммой — окончательный и достаточный для продакшена будет просто не прав. Тут либо переделка структуры, либо полный перебор ID'ов.

                                                                                                                      Вторая задачка (кувшины) — ну ок, лёгкая, математическая, чтобы решающий почувствовал себя увереннее. К IT отношения не имеет от слова «совсем».
                                                                                                                      Но вообще в реальных задачах такого типа (когда есть возможность что-то решить, нестандартно используя существующие объекты), нужно в первую очередь начать задавать вопросы.
                                                                                                                      Почему такая задача вообще возникла и к ней не готовы? Может, в ТЗ опечатка и нужно всё-таки 3 литра?
                                                                                                                      Почему у нас нет кувшина на 4 литра? Может, он всё-таки есть и стоит его поискать? Чтобы не занимать те два кувшина, которые явно уже предназначены для других целей и могут понадобиться остальным.
                                                                                                                      А если скоро опять возникнет такая задача? А если в следующий раз — 1/4 литра? Может, стоит озаботиться покупкой кувшина с литровыми отметками, а не тратить своё время на «костыльные» переливания?

                                                                                                                      Третья задачка (поменять переменные местами) — да, задачка интересная. В реальности встречается, но крайне редко. Тут только нужно пояснить, в этой самой реальности для решения используют встроенную функцию (обычно называется Swap), либо (на худой конец) третью переменную. А за неожиданный уход в побитовые операции пускают лучи неневисти (те, кому потом придётся поддерживать такой код).
                                                                                                                        +3

                                                                                                                        Получается, что они не просто оторваны от реальности, они заставляют искать костыльное ad hoc решение, которое годится только для данного конкретного случая. Мне кажется, опытный программист уже на подкорке отсекает такие решения (и на работу его не берут...)

                                                                                                                          0
                                                                                                                          Первая задачка — явная прелюдия к вопросу о сложности алгоритмов. Особенно если соискатель «попался» на желании что-то сортировать. А разглядеть О(n*log n), O(n) и O(n^2) и знать разницу должен каждый джун.

                                                                                                                          Вторая задачка к IT и правда мало отношения имеет, кроме разве того, что в голове приходится проигрывать алгоритм.

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

                                                                                                                          Задача про вагоны из комментов вполне похожа на некоторые задачи биоинформатики с их кольцевыми ДНК.

                                                                                                                          Это далеко не самые оторванные от жизни в IT задачи, я вам скажу. Другое дело, что они банальные и задаются повсюду, отчего их ценность как каких-то индикаторов сходит на нет.
                                                                                                                            0
                                                                                                                            Другое дело, что они банальные и задаются повсюду, отчего их ценность как каких-то индикаторов сходит на нет.
                                                                                                                            Вы не поверите, но несмотря на то, что «они банальные и задаются повсюду» — соискатели про них, в подавляющем большинстве, не знают. А если человек, в ответ на одну из них тут же говорит «да-да, знаю, можно и два „потерянных“ числа найти и общий алгоритм для работы с этими кувшинами есть» — то это, в общем-то, хороший признак…
                                                                                                                          +1
                                                                                                                          Иногда натыкаюсь в сети на тестовые задания или вопросы по алгоритмам на собеседованиях, обычно стараюсь сохранять ссылки и текст задачи (авось пригодится).
                                                                                                                          В основном встречаются скучные типовые задачи под конкретный стек технологий, но есть и достаточно необычные (по крайней мере, для меня):

                                                                                                                          Задания
                                                                                                                          1/ Ссылка 1, Ссылка 2
                                                                                                                          Написать метод merge, который принимает в качестве параметров два ArrayList a и b.
                                                                                                                          Данные коллекции можно представить в виде a=[a1,a2,a3,...] и b=[b1,b2,b3,...].
                                                                                                                          По результату выполнения программы надо получить в коллекции а следующее a=[a1,b1,a2,b2,a3,b3,...].
                                                                                                                          При этом необходимо написать метод, который экономный к процессорному времени и памяти.


                                                                                                                          2/ Ссылка
                                                                                                                          Суть задания, есть XML файл:

                                                                                                                          <?xml version=«1.0» encoding=«UTF-8»?>
                                                                                                                          <Orders>
                                                                                                                          <AddOrder book=«book-1» operation=«SELL» price=«100.50» volume=«81» orderId=«1» />
                                                                                                                          <AddOrder book=«book-3» operation=«BUY» price=" 99.50" volume=«86» orderId=«2» />
                                                                                                                          <AddOrder book=«book-1» operation=«BUY» price=" 99.70" volume=«16» orderId=«3» />
                                                                                                                          <DeleteOrder book=«book-1» orderId=«1» />
                                                                                                                          … 2 776 399 строк
                                                                                                                          </Orders>

                                                                                                                          Описаны три операции:
                                                                                                                          1. заказ Sell
                                                                                                                          2. заказ Buy
                                                                                                                          3. удалить order
                                                                                                                          Суть сделать парсинг за 6 секунд и выдать итог в другой файл уже без удаленных orders.
                                                                                                                          Как мне объяснили нужно самому парсить что бы успеть за 6 секунд никакие инструменты SAX, DOM и прочее не дадут этого результата.


                                                                                                                          3/ Ссылка
                                                                                                                          1. Отсортировать большой массив (4 террабайта, скажем) int32_t, свободной памяти — 10 Mb
                                                                                                                          2. Упаковать (не заархивировать) файлы в архив. Распаковать потом. Что будет с каталогами. Чем похожее на tar — тем лучше.
                                                                                                                          3. Геометрия всякая, даны стенки, найти пересечения, тесты на попадание точки в треугольник и проекции на стороны…


                                                                                                                          4/ Ссылка
                                                                                                                          Требуется выполнить сортировку файла, размером 4 Гб, используя всего 512 Мб оперативной памяти. Язык — Java, время выполнения задания (НЕ время работы алгоритма) — 4 часа. В файле строки из трех столбцов, второй столбец — дата и время в формате ISO, по нему нужно сортировать.



                                                                                                                          Ссылки на типовые задания, может, кому пригодятся (на пару-тройку дней выполнения):
                                                                                                                          Ссылки на задания
                                                                                                                          1/ Java: ООП и JUnit (на английском) ссылка
                                                                                                                          2/ PHP: файлообменник ссылка
                                                                                                                          3/ Java: веб-приложение (на английском) ссылка
                                                                                                                          4/ Java: ООП, «аквариум» ссылка
                                                                                                                          5/ Java: веб-приложение (сервис обмена дисками) ссылка
                                                                                                                          6/ C#, ASP.NET: парсер сайта ссылка
                                                                                                                          7/ Java: модульное веб-приложение ссылка
                                                                                                                          8/ Java: веб-приложение «телефонный справочник» ссылка
                                                                                                                          9/ Java: Rest, веб-приложение ссылка
                                                                                                                          10/ C#, ASP.NET, веб-приложение ссылка
                                                                                                                          11/ PHP: интернет-магазин ссылка
                                                                                                                          12/ Java: ООП, «сосуды» ссылка
                                                                                                                          13/ Java: микрофрейворк ссылка
                                                                                                                          14/ PHP: скрипт генерации jpg ссылка
                                                                                                                          15/ Python, Django, сервис проведения тестирования ссылка
                                                                                                                          16/ PHP: гостевая книга ссылка
                                                                                                                          17/ PHP: ООП, деревья ссылка
                                                                                                                          18/ RoR, PostgreSQL, SPA ссылка
                                                                                                                          19/ Java: веб-приложение ссылка
                                                                                                                          20/ PHP: Yii2 ссылка
                                                                                                                          21/ PHP: бонусные карты ссылка
                                                                                                                          22/ Java: ООП «контрольные мероприятия» ссылка
                                                                                                                          23/ C++, ООП «покупка товара» ссылка

                                                                                                                            +2

                                                                                                                            Из первого списка первая задача — zip+flatten, называть её merge не очень, если не предполагать имплицитно специальный компаратор, базирующийся на индексах в коллекциях.
                                                                                                                            Во втором SAX/StAX вполне должен укладываться в нужные характеристики. DOM и использование XSLT с большой вероятностью не взлетит.
                                                                                                                            3.1 — внешняя сортировка по вкусу. В 3.2 явная хрень в условии, тут либо использовать общепринятые термины (архивация/компрессия, ибо тот же tar — архиватор, но не компрессор), либо явно указывать что понимается под каждым термином…
                                                                                                                            4 — опять внешняя сортировка с парсингом, вполне нормальный вариант на поговорить. Хотя 4 часа выглядят сильно избыточно, если не нужно писать в блокноте.

                                                                                                                            +3

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

                                                                                                                              0
                                                                                                                              Ну здесь как раз есть ответ: в 1894 году.
                                                                                                                                0

                                                                                                                                А он выводится из исходных данных хоть как-то?

                                                                                                                                  0

                                                                                                                                  Швейк рассказал свою задачу в 1914 году. Год кончины бабушки равен произведению общего числа окон этого дома на число труб и на возраст (в 1914 году) одного из квартирантов, лично присутствовавшего на похоронах. Итак, в каком же году умерла у швейцара бабушка?
                                                                                                                                  На самом деле, это такой своеобразный фольклор про странные задачи.

                                                                                                                                    0

                                                                                                                                    Про "на самом деле" — это было ещё прямо в книге. А вот приведенное вами решение требует дополнительных данных, которых в исходной постановке нет (про квартиранта — про него Швейк в книге не сказал ЕМНИП ничего). Значит, задача не является математической. (А вот примером странной задачи — является, ещё как.)


                                                                                                                                    Спасибо, кстати, за решение, мне ещё не попадалось.

                                                                                                                                    0
                                                                                                                                    На самом деле, всё просто: один мой хороший знакомый как раз потомок этого швейцара))) (кстати, он британский учёный и, по совместительству, русский хакер, — то есть источник, как вы понимаете, надёжный)

                                                                                                                                    В остальном же прав Arastas: это классика идиотских задач и тут решения из исходных заведомо нет. Хотя можно собрать материальчик на историческое расследования, чтобы вычислить наиболее вероятный диапазон: как уже сказано, задача рассказана в 1914 году, вероятно несколькими днями позже 28-го июня, действие происходит в Праге и исходя из характера Швейка можно с большой долей вероятности утверждать, что дом этот — именно в Праге, а время — немногим ранее… и т.д… но зачем? если правильный ответ: 1894, и тут уж ничего не поделаешь!
                                                                                                                                      0
                                                                                                                                      Проблема только в том, что правильный ответ там 1904. А 1894 на 28 не делится.
                                                                                                                                        0
                                                                                                                                        — Я думаю, вполне достаточно,-- сказал председатель комиссии. — Можете отвести обвиняемого на прежнее место.
                                                                                                                                        — Благодарю вас, господа,-- вежливо сказал Швейк,-- с меня тоже вполне достаточно.
                                                                                                                                –1

                                                                                                                                А где в первой задаче сказано что доступны обе коллекции — исходная и перемешанная?

                                                                                                                                  +2

                                                                                                                                  Про задачу с обменом чисел:


                                                                                                                                  опять же, много допущений: в варианте со сложением вычитанием нужно исходить из того, что отключен креш при переполнении;
                                                                                                                                  в варианте с XOR — исходим из того, что вычисление производятся на компьютере с бинарной логикой (а где вообще в задаче сказано, что вычисления будут производиться на компьютере, а не на листе бумаги или компьютере с троичной логикой?).


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


                                                                                                                                  Получаем то, что называется "преждевременной оптимизацией":
                                                                                                                                  При введении переменной-буфера мы всего лишь вводим одну переменную, и операция копирования значения — из одной ячейки памяти в другую — весьма быстрая (если речь о переменной 32/64 бита, а не BigInteger — а где это оговорено в условии?).


                                                                                                                                  Давайте не забывать, что операции сложения/вычитания, битового маскирования явно помедленнее — нужно поместить значения из памяти в регистры процессора, выполнить собственно операции, считать это обратно в память.
                                                                                                                                  И еще надо разобраться, не введет ли при этом компилятор промежуточные переменные на стеке (а тогда за что боролись)?


                                                                                                                                  И что значит два числа? Где оговорено, что это int, не float? Для float результат сложения/вычитания будет вообще долгим и неточным, а XOR для float вообще будет неприменим (хотя, конечно, можно интерпретировать float как бинарные данные и привести с int, а потом обратно к float — это тоже куча лишний операций, в результате которых теряется смысл задачи).

                                                                                                                                    –3
                                                                                                                                    Ох…
                                                                                                                                    Эти неверные постановки задачи. Первая задача — найдите число. Но не уточнили — нам нужна ссылка на удаленное число в первом списке\массиве или просто значение этого числа. Во втором случае конечно достаточно разницы сумм, но вот я к примеру подумал, что прежде всего по смыслу задачи нужно найти позицию индекс удаленного числа в первом списке, и в этом случае сортировка и линейная сверка один из оптимальных и быстрейших решений.
                                                                                                                                      +5
                                                                                                                                      Найти удаленное число.

                                                                                                                                      Как? Как тут можно подумать об индексе удаленного числа? о_О
                                                                                                                                        +3
                                                                                                                                        индекс в первоначальном массиве, хотя, най мой взгляд, четко сказано найти число(то бишь значение), а не индекс.
                                                                                                                                          –4
                                                                                                                                          Отвечу обоим. Сказано найти число, которое потерялось. Число, в памяти. Оно еще есть в какой-то ячейке — нужно найти ячейку с этим числом. А что не так с такой интерпретацией?

                                                                                                                                          Скажем так, если бы формулировка была — вычислить, тогда вопросов бы вообще не возникло. Там написано — найти удаленное число. Для меня это двояко.
                                                                                                                                            +3
                                                                                                                                            С чего вы решили, что это число есть в памяти? Возможно — на листке бумаги записано.
                                                                                                                                            нужно найти ячейку с этим числом

                                                                                                                                            Если-бы нужно было найти ячейку — формулировка задачи звучала-бы как у вас, но в задаче довольно точное описание — найти удаленное число.

                                                                                                                                            P.S.: странно, что с такой логикой вы не дошли до «найти операционную систему, в которой удалено число» ;)
                                                                                                                                              –1
                                                                                                                                              Ну просто в моем языке программирования число — это объект, а объект ищут по ссылке.
                                                                                                                                                +3
                                                                                                                                                А как связана задача и конкретный язык программирования? о_О
                                                                                                                                                Кроме того — вы действия «в своем языке программирования» совершаете над объектами или над значениями?
                                                                                                                                                  0
                                                                                                                                                  Вот именно что обычно над ссылками на объекты
                                                                                                                                                    +3
                                                                                                                                                    Вы складываете ссылки вместо значений?))) Нууу, ок.
                                                                                                                                                      0
                                                                                                                                                      Смотрите, действие — найдите удаленное число для меня звучит в отрыве от типов. Для меня это фраза — найдите потерянный объект в массиве, т. е. указатель на него\индекс в исходном массиве.
                                                                                                                                                        +1
                                                                                                                                                        Каких типов? Какой объект? Вы вообще о чём?!
                                                                                                                                                        Перестаньте думать в критериях языков программирования! Думайте логически и математически. Язык — это всего-лишь инструмент выражения знаний и опыта. Переводя каждую задачу в область одного ЯП вы лишаетесь гибкости рассуждений. Как так можно?!

                                                                                                                                                        найдите потерянный объект в массиве

                                                                                                                                                        Даже тут — откуда взялся объект и почему вдруг надо искать индекс, если речь о числе? Ну ок, предположим… Тогда почему массив 1..N не может лежать в памяти с адресацией от 1 до N? Так вам проще?

                                                                                                                                                        P.S.: вообще — это очень, очень плохая привычка — додумывать задачи. Вот честно, по работе сталкиваюсь с подобным и ни разу это не привело ни к чему хорошему. Из-за подобных привычек задачи выполняются дольше и сложнее, и как следствие, сложны в поддержке в будущем.
                                                                                                                                                          0
                                                                                                                                                          Поддержу.

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

                                                                                                                                                          В результате это ведет к множественным недопониманием друг друга, заваливание сроков и реализации некорректной логики.

                                                                                                                                                          Логические задачки для того и нужны, чтобы их решать логически.
                                                                                                                                                            –4
                                                                                                                                                            В чем вообще проблема? Я ничего не додумывал, и формулировка действительно двоякая. То, что для вас очевидно и однозначно, вполне может быть не очевидным и не однозначным для других. И навыки программирования тут совершенно не при чем. В контексте вычисления потерянного значения — берем суммы, в контексте _поиска_ потерянного числа — находим индекс. Проще уточнить задачу, и она будет уточнена, если это будет реальный разговор меня и собеседника.
                                                                                                                                                              +2
                                                                                                                                                              Уточнять желательно — тут полностью согласен. Но уточнять в данной задаче — это что-то новое. Если-бы было сказано «найдите то, что убрано» — да, появляется двоякость. В задаче-же четко сказано — найдите удаленное число. Удаленное число! Где тут «двоякая формулировка»? Не понимать (с)…
                                                                                                                                                                –2
                                                                                                                                                                найдите то, что убрано
                                                                                                                                                                найдите удаленное число
                                                                                                                                                                Вот читаю и вижу одно и то же.
                                                                                                                                                                То что по разному выглядит для вас, одинакого может выглядеть для других, и наоборот. Люди разные, ничего страшного.
                                                                                                                                                                  +2
                                                                                                                                                                  найдите то, что убрано
                                                                                                                                                                  найдите удаленное число
                                                                                                                                                                  Вот читаю и вижу одно и то же.


                                                                                                                                                                  Хм… А если задача найти недостающее слово в тексте — тоже позицию искать будете?

                                                                                                                                                                  Тут дело не в том, что люди разные, а в том, что вы додумываете задачу под свои критерии. Именно этому я и удивляюсь, если честно. Заметьте, кроме вас никто не прочел задачу подобным образом (либо я этого не увидел в комментариях).

                                                                                                                                                                  Как-бы там ни было, давайте на этом и закончим.
                                                                                                                                                                    0
                                                                                                                                                                    Эээ, я уточню что искать, позицию или слово. Я не очень понимаю, что клиенту даст слово, без места, где оно должно было стоять или было убрано.

                                                                                                                                                                    Больше того, в таких задачах просят подчеркнуть слово, а не просто написать его, т. е. все таки найти позицию.
                                                                                                                                                                      0
                                                                                                                                                                      Ха… Снова додумываете, хоть и не хотите себе в этом признаваться…

                                                                                                                                                                      А если задача найти недостающее слово в тексте

                                                                                                                                                                      Вот в задаче сказано — найти недостающее слово. Для чего и что с ним будут делать потом — абсолютно не важно. Есть задача — найти слово. Что подразумеваете вы?

                                                                                                                                                                      я уточню что искать, позицию или слово
                                                                                                                                                                      Я не очень понимаю, что клиенту даст слово, без места
                                                                                                                                                                      Больше того, в таких задачах просят подчеркнуть слово, а не просто написать его, т. е. все таки найти позицию.


                                                                                                                                                                      Откуда вдруг взялась позиция?)))) Ясно и четко написано — найти удаленное слово. Для чего вы пытаетесь придумать себе новую задачу, не решив поставленную?))))

                                                                                                                                                                      Вас удивляет что у нас разные критерии, но я точно ничего не додумываю.


                                                                                                                                                                      Критерий всегда(!) один — решение поставленной задачи.

                                                                                                                                                                      но это не значит что меня нет или я в чем-то не прав.


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

                                                                                                                                                                      Я понимаю, что вам хочется проявлять инициативу, но чаще всего это путь к проблемам. Найдите в себе силы и избавьтесь от подобной привычки. Это мое искреннее пожелание.
                                                                                                                                                                        0
                                                                                                                                                                        Пожалуй я сохраню привычку уточнять задание, прежде чем потенциально сделать то, что потом придется переделывать из за возможной двусмысленной трактовки задачи.
                                                                                                                                                                        Заметьте, я не утверждал что условие именно найти позицию, я указал что есть такой вариант, и в этом варианте решение будет более общим, хоть и алгоритмически более медленным.
                                                                                                                                                                        Привычка уточнять дух задачи, а не формулировку, обдумывание наперед того, какие задачи возникнут в будущем — хорошая привычка.
                                                                                                                                                                          0
                                                                                                                                                                          Прочтите мои ответы выше. Я не предлагал избавиться от привычки уточнять, я предлагал избавиться от привычки додумывать. И, как я уже говорил выше, уточнять — это хорошая привычка.
                                                                                                                                                                            0
                                                                                                                                                                            Можете указать, где я хоть раз что-то додумывал? Я лишь поставил вопрос — есть такая трактовка, и гипотетически рассуждал в этом направлении.
                                                                                                                                                                            Если проблема в этом, то наконец пожимаем руки, я рад что мы поняли друг друга.
                                                                                                                                                                              0
                                                                                                                                                                              Можете указать, где я хоть раз что-то додумывал?


                                                                                                                                                                              Здесь, здесь, здесь и здесь

                                                                                                                                                                              Я лишь поставил вопрос — есть такая трактовка

                                                                                                                                                                              Так вот тут и непонятка… Как(!) в текущем изложении(!!) можно трактовать иначе?! Вот блин — я честно не понимаю этого.

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

                                                                                                                                                                              А проблемы в принципе нет. Просто была моя попытка понять как и о чем рассуждает человек, когда переворачивает исходную задачу. К сожалению, так и не понял, хотя очень-очень пытался ((((

                                                                                                                                                                              И тут вдруг менеджер начинает действительно думать, а не понадобится ли что-то еще.

                                                                                                                                                                              Увольняйте такого менеджера. Поверьте — это добрый совет. Если поставлена задача, которая не обдумана — тратятся ресурсы не только менеджера, но и программиста, тестировщика и пр.
                                                                                                                                                                      0
                                                                                                                                                                      Вас удивляет что у нас разные критерии, но я точно ничего не додумываю. Просто вы видите условия так, а я иначе. Ниже в комментариях есть ответ, что большинство видит задачу так как вы, я с этим не спорю, я в меньшинстве, но это не значит что меня нет или я в чем-то не прав.
                                                                                                                                                                        +2
                                                                                                                                                                        У вас правда странный подход.

                                                                                                                                                                        Я прямо вижу диалог.

                                                                                                                                                                        — напиши программу которая находит недостающее слово.
                                                                                                                                                                        — А надо слово или позицию?
                                                                                                                                                                        — Слово
                                                                                                                                                                        — А надо слово, или номер статьи в словаре Даля?
                                                                                                                                                                        — Слово
                                                                                                                                                                        — В общем я тут решил задачу, моя программа подчеркивает предложение где это слово пропущено, возвращает ссылку на викисловарь и печатает номер позиции в тексте.
                                                                                                                                                                        -…
                                                                                                                                                                          –1
                                                                                                                                                                          Вы сами придумали этот диалог.
                                                                                                                                                                          — Надо слово или позицию? Какие еще метаданные к этому слову нужны?
                                                                                                                                                                          — Только слово
                                                                                                                                                                          — Ок, но если понадобится что-то еще, придется полностью переписать алгоритм с нуля.
                                                                                                                                                                          И тут вдруг менеджер начинает действительно думать, а не понадобится ли что-то еще.
                                                                                                                                                                          Если не понадобится, то
                                                                                                                                                                          — Нет, только слово
                                                                                                                                                                          — Ок.
                                                                                                                                                                            +2
                                                                                                                                                                            Нет, я взял его из диалога выше, где вы упорно доказываете что под «недостающим числом» может пониматься что угодно — от индекса до ссылок в вашем любимом языке программирования.

                                                                                                                                                                            В целом у вас как-то все очень странно. Менеджер который начинает задумыватьтся о том может ли что-то понадобиться не в момент формулировки и планирования задачи, а после вникания программиста. Система которую надо переписывать с нуля каждый раз когда требуется внести какие-то изменения.
                                                                                                                                                                              0
                                                                                                                                                                              Я не переворачиваю задачу. То, что вы считаете, что понятие числа — это его значение — единственно адекватная и верная трактовка — это заблуждение. Вы правы, что это адекватный контекст для большинства людей, но тем не менее это всего лишь контекст. Считать меньшинство людей, которые совершенно спокойно видят много контекстов, и не возвышают один над другим, вместо того уточняя какой имелся ввиду — странными — странно для меня.

                                                                                                                                                                              А что касается задумываний менеджера и системы которую надо переписывать с нуля, это как раз относилось к задаче.
                                                                                                                                                                              Если мы будем решать задачу через суммы, а в будущем окажется, что нам все таки где-то нужна не только сумма, но и сам объект, который ее содержал до этого, возникнет новая задача, в которой таки придется сортировкой и перебором искать искомый объект (с вашей точки зрения новая задача). Но это вполне очевидный и обыденный кейс для меня — сразу узнать будущие кейсы и уточнить с менеджером более удачную реализацию, подходящую для дальнейших хотелок. Такие ситуации у меня на работе штатные, и не поверите — бывают и такие формулировки как в этой задаче, и именно со смыслом находить объект, чтобы потом как-то работать с статистикой по нему.
                                                                                                                                                                                0
                                                                                                                                                                                Можете назвать компанию, в которой работаете? Я для себя, чтобы занести на будущее в черный список. Честно.

                                                                                                                                                                                То, что вы считаете, что понятие числа — это его значение — единственно адекватная и верная трактовка — это заблуждение.

                                                                                                                                                                                Вы серьезно или начали троллить?)

                                                                                                                                                                                Если первое… Да, число === значение, в контексте данной задачи. И это неоспоримый факт. Не понимаю, почему вы до сих пор пытаетесь себя и других убедить в обратном. Заметьте — никто, кроме вас, не прочел задачу в виде «найдите индекс». Думаю, хотя-бы это уже является поводом задуматься…

                                                                                                                                                                                Считать меньшинство людей, которые совершенно спокойно видят много контекстов, и не возвышают один над другим, вместо того уточняя какой имелся ввиду — странными — странно для меня.

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

                                                                                                                                                                                Если мы будем решать задачу

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

                                                                                                                                                                                и не поверите — бывают и такие формулировки как в этой задаче, и именно со смыслом находить объект, чтобы потом как-то работать с статистикой по нему.

                                                                                                                                                                                Не поверю. Либо вы лукавите, либо ваши постановщики задач не компетентны.
                                                                                                                                                                                  –1
                                                                                                                                                                                  Вы странный (:
                                                                                                                                                                                  А с моей работой все в порядке.
                                                                                                                                                                                    +1
                                                                                                                                                                                    Я странный?! )))))))))))))))) Нууу, ок.
                                                                                                                                                                                      –1
                                                                                                                                                                                      Я аккуратно намекнул на вашу нетерпимость.
                                                                                                                                                                                      Я для себя, чтобы занести на будущее в черный список.
                                                                                                                                                                                      Я не считаю это странным. Я искренне считаю это вредным.
                                                                                                                                                                                        +1
                                                                                                                                                                                        А на хабре теперь запрещено свое мнение публиковать? о_О
                                                                                                                                                                                        И что не так с моими высказываниями? То, что я не хочу никогда работать в компании, в которой менеджеры меняют условия задачи в любой момент? Или то, что сотрудники, вместо решения конкретной задачи, начинают придумывать свои условия?

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

                                                                                                                                                        Действия согласно семантике программы совершаются над значениями, согласно семантике языка — над объектами, а реально оптимизатор может много чего повыкидывать и совершать действия над регистрами и памятью вплоть до того, что новый объект числа создастся только на строчке return missing_number. «Найти число» в смысле «найти [ссылку на] число» — вполне допустимая интерпретация, «ссылку на» при разговоре часто опускают, хотя обычно это делают только когда идёт речь о более «сложных» объектах, что почти всегда передаются по ссылке.

                                                                                                                                                          +2
                                                                                                                                                          Действия, в большинстве случаев, совершаются над значениями. Даже в семантике языка. Передача объекта по ссылке — это передача ссылки на объект и тут ссылка и является значением.

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

                                                                                                                                                            Интерпретировать вполне можно и так, как Shifty_Fox. Другое дело, что большинству программистов (включая меня) это действительно не придёт в голову: почти во всех языках программирования, даже если число является объектом, всё определено так, что разница между числом x в объекте по адресу A и разница между тем же числом x в объекте по адресу B настолько мала, что нормальный программист о ней вспомнит разве что после того, как у него начнутся проблемы с производительностью на большом количестве чисел.


                                                                                                                                                            Но именно такая интерпретация мне пришла бы в голову, если бы «число», к примеру, было «клиентом».

                                                                                                                                                  –1
                                                                                                                                                  del.
                                                                                                                                              0

                                                                                                                                              Я бы решил первую задачу вычитанием двух множеств: вычтем из первого множества со всеми числами 1..N второе множество без одного числа, получим это недостающее во втором множестве число.

                                                                                                                                                0
                                                                                                                                                Мне понравилась такая задача:
                                                                                                                                                * 4 человека, с разной скоростью передвижения (1, 2, 5, 10 мин)
                                                                                                                                                * нужно перебраться всем по мосту
                                                                                                                                                * по мосту могут идти только 2 одновременно
                                                                                                                                                * по мосту можно идти только с фонариком, фонарик один
                                                                                                                                                За какое минимальное время можно перебраться всем на другую сторону?
                                                                                                                                                Ответ
                                                                                                                                                17

                                                                                                                                                  0

                                                                                                                                                  А доказательство, что данное время минимально, без полного перебора вариантов существует?

                                                                                                                                                    +1

                                                                                                                                                    Очевидно, вперед всегда идут двое, потом кто-то один возвращается с фонариком. Минимальное количество ходок — 5 (3 туда, 2 обратно). Покажем, что нет решения за 16 и меньше. Из трех ходок туда, хотя бы одна будет с 10, оставшиеся стоят не меньше 2 (ибо там 2 человека идут). Еще 2 ходки назад стоят не меньше 1 каждая. Т.е. теоретически минимальное время 16. Это только если оба раза назад идет 1. Но в этом случае туда всегда идет 1 с кем-то (и они все разные) и 3 ходки вперед стоят не 10+2+2, а 10+5+2 — уже больше 16.

                                                                                                                                                      0
                                                                                                                                                      Совсем не понимаю, каким образом у вас получилось выкинуть оттуда 5. Как минимум один раз 5 должна пройти. Время пересечения не может быть меньше времени пересечения для самого медленного звена. Если перебрались все, значит каждый как минимум раз прошел. Если мы 5 спрячем в 10, назад все равно придется 5 возвращаться. Поэтому самым рациональным является сделать минутку гонцом.
                                                                                                                                                      10> +1< +5> +1< +2> = 19
                                                                                                                                                        0

                                                                                                                                                        5 действительно может быть спрятанно за 10. Но в этом случае, как уже сказано, нельзя оба раза вернуть назад 1. При этом не обязательно, что назад идет кто-то из пары, только что пришедших. В этом случае 5 не обязано идти назад. Выше я показал, что 16 вообще оценка снизу, к тому же не достижимая. Доказать, что ответ 17 можно только приведя и сам ответ:


                                                                                                                                                        Решение

                                                                                                                                                        > 1 2
                                                                                                                                                        < 1
                                                                                                                                                        > 10 5
                                                                                                                                                        < 2
                                                                                                                                                        > 1 2

                                                                                                                                                    0
                                                                                                                                                    Что-то я не пойму, как получилось 17. Можете по пунктам объяснить?

                                                                                                                                                    У меня меньше 19 не получается.
                                                                                                                                                    В вашем решении учтено, что по крайней мере два раза кто-то с фонариком должен будет ещё и возвращаться к началу?
                                                                                                                                                      0
                                                                                                                                                      Instant return, видимо. Присоединяюсь к вопросу.
                                                                                                                                                        +1
                                                                                                                                                        Подсказка

                                                                                                                                                        Хитрость в том, чтобы с 10-кой, которая обязательно посчитается, пустить максимальный из оставшихся — 5. Таким образом, мы исключаем 5 вообще из суммы. Чтоб ему назад не идти потом, 10 и 5 идут вперед не первыми. Тогда кто-то другой уже будет на другой стороне, чтоб вернуться назад.

                                                                                                                                                        0
                                                                                                                                                        а вариант когда идет человек 10 минут с фанариком, с ним начинает идти 1-минутный, после того как выходит 1-минутный идет сразу 2 и затем так же 5-ка… и того 10 минут… или я что то не так понял?
                                                                                                                                                          0
                                                                                                                                                          Нужно всех перевести, однако, а не только бабушку и дедушку.
                                                                                                                                                          0
                                                                                                                                                          Подсказка
                                                                                                                                                          5 и 10 идут вместе один раз

                                                                                                                                                          Решение
                                                                                                                                                          > 1 + 2
                                                                                                                                                          < 1
                                                                                                                                                          > 5 + 10
                                                                                                                                                          < 2
                                                                                                                                                          > 1 + 2
                                                                                                                                                            0
                                                                                                                                                            С компьютерной точки зрения это (да и никакое) решение неверно, так как у каждого из этих людей своя скорость передвижения и, следовательно, никакие из них не могут двигаться вместе. Ведь в задаче нигде не говорится, что кто-то из них может двигаться с более низкой скоростью. Мало того, в задаче сказано, что по мосту могут идти только 2 одновременно, что можно трактовать как запрет ходить по одиночке.
                                                                                                                                                              +1
                                                                                                                                                              Изложил задачку в кратком и понятном для человека виде, для «компьютерной точки зрения» могу расписать это на 10 листах, но на хабр оно точно не нужно, вам бы лишь поприкапываться.
                                                                                                                                                              0
                                                                                                                                                              не могу понять почему не верна логика когда стартует первый с 10-ка и с ней в паре еще любой другой, пока 10-ка идет, поочередно другие заходят на мост, после того как закончат идти другие пары… Ведь по сути ваш вариант 1-ца возвращается после достижения края моста… почему в это время не может начать движение другой человек с противоположного конца моста? что в правилах задачи ему это запрещает? На мосту есть человек с фонариком, одновременно там 2… Объясните не понимающему данную задачку
                                                                                                                                                                0
                                                                                                                                                                дошло почему не верная логика, простите.
                                                                                                                                                            0
                                                                                                                                                            Есть ли устоявшееся английское название у задачи с бутылками?
                                                                                                                                                              0
                                                                                                                                                              water and jug problem или просто jug problem
                                                                                                                                                                0
                                                                                                                                                                Общий способ решения.
                                                                                                                                                                Знал о нем давно, но нагуглить без названия не получилось. Основан на равенстве суммы высот для всех точек равностороннего треугольника
                                                                                                                                                              0
                                                                                                                                                              Вторая задача прям из фильма Крепкий орешек 3, сцена у фонтана со слоном.

                                                                                                                                                              Но я не так ее решал

                                                                                                                                                              1. Наполняем 3х литровую и переливаем в 5ти
                                                                                                                                                              2. Повторяем 1й шаг, в результате после 2й итерации у нас в 3х литровой останется 1 литр
                                                                                                                                                              3. Опустошаем 5ти литровую и переливаем туда 1литр с 3х литровой
                                                                                                                                                              4. Наполняем 3х литровую и переливаем в 5ти. Получаем 4 литра
                                                                                                                                                                0

                                                                                                                                                                У меня короче — 6 шагов


                                                                                                                                                                1. Наполняем 5л
                                                                                                                                                                2. переливаем в 3л (в 5л осталось 2)
                                                                                                                                                                3. Выливаем из 3л
                                                                                                                                                                4. Переливаем из 5л в 3л (в 3л теперь 2л)
                                                                                                                                                                5. Набираем полный 5л
                                                                                                                                                                6. Переливаем из 5л в 3л (поскольку в 3л уже 2л, то вольется только 1) в 5л осталось 4л

                                                                                                                                                                а блин, там выше уже такой алгоритм рассказали

                                                                                                                                                                0
                                                                                                                                                                и что вам даст это при собеседовании кандидата на позицию, скажем, Software Engineer?
                                                                                                                                                                  0
                                                                                                                                                                  Можно будет отсеять примерно половину кандидатов за явной неадекватностью.

                                                                                                                                                                  С оставшимися нужно будет говорить на другие темы, конечно.
                                                                                                                                                                  0
                                                                                                                                                                  Забавно, мне на собеседованиях попадались все перечисленные в посте задачи :) Первую решал через разницу сумм исходной и новой последовательности, вторую и третью предложенными вариантами.
                                                                                                                                                                    +2
                                                                                                                                                                    Вот такая задача была на собеседовании

                                                                                                                                                                    Встречаются два приятеля — математика:

                                                                                                                                                                    — Ну как дела, как живешь?
                                                                                                                                                                    — Все хорошо, растут два сына дошкольника.
                                                                                                                                                                    — Сколько им лет?
                                                                                                                                                                    — Произведение их возрастов равно количеству голубей возле этой скамейки.
                                                                                                                                                                    — Этой информации мне недостаточно.
                                                                                                                                                                    — Старший похож на мать.
                                                                                                                                                                    — Теперь я знаю ответ на твой вопрос.

                                                                                                                                                                    Сколько лет сыновьям? (Ответ логичный и однозначный)
                                                                                                                                                                      +3
                                                                                                                                                                      1 и 4?
                                                                                                                                                                        +1

                                                                                                                                                                        Почему не 1 и 9 или 2 и 8? Или автор лукавит про однозначность.

                                                                                                                                                                          0
                                                                                                                                                                          Чтобы решить задачу, нужно понять — математики знали количество голубей, а мы не знаем.
                                                                                                                                                                          1) Дошкольники. Значит им от 1 до 7 лет.
                                                                                                                                                                          2) Их произведение равно известному только математикам X
                                                                                                                                                                          3) Старший похож на мать. Именно этот факт дал второму математику ответ, из чего мы знаем что, до вопроса — число голубей раскладывалось как на два одинаковых числа, так и на два разных, и тот факт то возрасты не равны — отсек вариант с одинаковыми числами, оставив два разных — 1 и 4
                                                                                                                                                                          Задача решается перебором и проверкой каждого варианта на все эти условия.
                                                                                                                                                                            +2

                                                                                                                                                                            Согласен, я упустил, что дошкольники.

                                                                                                                                                                              0
                                                                                                                                                                              Все равно осталась неоднозначность насчет того, почему им не может быть 1 и 3 или 2 и 5?
                                                                                                                                                                                0
                                                                                                                                                                                Понял. Фраза
                                                                                                                                                                                (Ответ логичный и однозначный)

                                                                                                                                                                                Это часть условия
                                                                                                                                                                                  +1
                                                                                                                                                                                  Скорее вот это условие не проходит:
                                                                                                                                                                                  «Этой информации мне недостаточно.»
                                                                                                                                                                                  1 х 3 = 3
                                                                                                                                                                                  2 х 5 = 10
                                                                                                                                                                                  Это единственные разложения при числах меньше 7, а нужно, чтобы было ровно два варианта, один из которых — одинаковые множители.
                                                                                                                                                                                  Здесь по сути вообще работают только квадраты, которые раскладываются как-то еще
                                                                                                                                                                                  2х2 = 4, 3х3 = 9, 4х4 = 16, 5х5=25, 6х6=36, 7х7=49

                                                                                                                                                                                  только в случае 2х2 подходит вариант 1 и 4, а вот все что дальше — получается 1 и 9, 1 и 16 и т. д., уже не дошкольники.
                                                                                                                                                                                0

                                                                                                                                                                                Хотя не сказано, что им целое число лет. Например 6 лет и полтора года дадут те же 9 голубей, что и два по три года. Да и то, вдруг они возраст в днях считают.

                                                                                                                                                                                  +6
                                                                                                                                                                                  И никто не сказал, что целое число голубей
                                                                                                                                                                                  0
                                                                                                                                                                                  Делаем матрицу перемножений всех комбинаций чисел от 1 до 7.

                                                                                                                                                                                  1) В фразе «мне не хватает информации» означало, что произведение X можно было получить несколькими способами.
                                                                                                                                                                                  Оставляем только варианты, где произведение можно получить хотя бы двумя способами,
                                                                                                                                                                                  остается
                                                                                                                                                                                  1x4=4, 2x2=4
                                                                                                                                                                                  1x6=6, 2x3=6
                                                                                                                                                                                  2x6=12, 3x4=12

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

                                                                                                                                                                                  Убираем варианты с перемножением одинаковых чисел, остается:
                                                                                                                                                                                  1x4=4
                                                                                                                                                                                  1x6=6, 2x3=6
                                                                                                                                                                                  2x6=12, 3x4=12

                                                                                                                                                                                  Поскольку решение задачи должно быть логичным и однозначным, логично, что единственная пара из этих вариантов, у котороых было отобран вариант с одинаковым возрастом, осталась 1 и 4
                                                                                                                                                                            0
                                                                                                                                                                            Что касается третьей задачи, то одно из значений переменных можно положить на стек или воспользоваться регистром. Когда нужно в ход идёт любой ассемблер.
                                                                                                                                                                              0

                                                                                                                                                                              И в чём будет отличие от использования переменной?

                                                                                                                                                                                0
                                                                                                                                                                                Можно подумать, вариант с xor'ами регистры процессора не использует
                                                                                                                                                                                  0

                                                                                                                                                                                  по факту, можно считать, что они уже там лежат