Выпуск#4: ITренировка — актуальные вопросы и задачи от ведущих компаний

    После некоторого перерыва, мы возобновляем выпуски ITренировки.

    КДПВ

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

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

    Вопросы


    1. Прямоугольный торт
      Question: How would you cut a rectangular cake into two equal pieces when a rectangular piece has already been cut out of it? The cut piece can be of any size and orientation. You are only allowed to make one straight cut.

      Перевод
      Как бы Вы разрезали прямоугольный торт на 2 равные части, если от торта уже отрезан прямоугольный кусок. Отрезанный кусок может быть любого размера и ориентирован горизонтально или вертикально. Разрешено сделать только один прямой разрез в любом направлении.

    2. Крепкое яйцо
      How Strong is an Egg?

      You have two identical eggs. Standing in front of a 100 floor building, you wonder what is the maximum number of floors from which the egg can be dropped without breaking it. What is the minimum number of tries needed to find out the solution?

      Перевод
      Вам выданы два одинаковых яйца. Стоя перед 100-этажным зданием, Вы прикидываете, какой самый высокий этаж, при падании с которого яйцо не разобьется. За какое минимальное количество попыток Вы сможете это определить?


    Задачи


    1. Подстрока с анаграммой
      Given 2 words, return true if second word has a substring that is also an anagram of word 1.
      LGE, GOOGLE => True
      GEO, GOOGLE => False

      Перевод
      Дано 2 слова. Найти, имеет ли второе слово вхождение подстроки, которая является анаграммой первого слова:
      LGE, GOOGLE => True
      GEO, GOOGLE => False

    2. Минимум автобусов (пересадок)
      A city bus station information, example, bus No. 1 stops at abcd station, bus No. 2 stops at cefg station. Then a-d you only need to take No. 1, thus return 1, a-g is 2, because you need to transfer at station c,
      Ask for a minimum bus you need to take to reach to another station. You can design any data structures.

      Перевод
      Расписание остановок маршрутов автобусов дано в следующем виде: маршрут №1 — следует по остановкам abcd, маршрут №2 — по cefg. Тогда, чтобы проехать a-d потребуется 1 автобус, а-g — потребуется 2 автобуса (пересадка на станции c).
      Найти минимальное количество автобусов, необходимое, чтобы попасть на заданную станцию. Разрешено использовать любые структуры данных.

    3. Подмассив максимальной суммой
      Sub-Array with the Largest Sum

      You are given an array with integers (both positive and negative) in any random order. Find the sub-array with the largest sum

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


    Ответы будут даны в течение следующей недели — успейте решить. Удачи!

    Решения


    1. Вопрос 1
      В комментариях верно нашли решение:
      В первой задаче находим «центр масс» исходного торта на пересечении двух диагоналей. Затем так же находим «центр масс» вырезанного куска. Проводим разрез по линии через эти «центры масс»


    2. Вопрос 2
      Первое, что приходит в голову — простой перебор; перебор с шагом 2 этажа; с фиксированным интервалом побольше. Но оптимальным является подход с уменьшением количества этажей к верхушке здания, тогда можно уложиться за максимум 14 попыток:
      Instead of taking equal intervals, we can increase the number of floors by one less than the previous increment. For example, let’s first try at floor 14. If it breaks, then we need 13 more tries to find the solution. If it doesn’t break, then we should try floor 27 (14 + 13). If it breaks, we need 12 more tries to find the solution. So the initial 2 tries plus the additional 12 tries would still be 14 tries in total. If it doesn’t break, we can try 39 (27 + 12) and so on. Using 14 as the initial floor, we can reach up to floor 105 (14 + 13 + 12 + … + 1) before we need more than 14 tries. Since we only need to cover 100 floors, 14 tries is sufficient to find the solution.

      Для интересующихся более развернутым ответом — MagnetonBora в комментарии предлагает посмотреть уроки Игоря Клейнера.

    3. Задача 1
      В комментариях были предложены верные методы:
      скользящее окно. Сложность O(n+m) дополнительная память O(n)

      bool findSubstrAnagram(string s1, string s2){
          if(s1.size() > s2.size())
              return false;
          if(s1 == s2)
              return true;
          vector<char> mark_s1(256, 0);
          vector<char> mark_s2(256, 0);
          
          for(char c : s1){
              mark_s1[c]++;
          }
          
          int count = 0;
          for(char c : s2){
              if(mark_s2[c] < mark_s1[c]){
                  count++;
                  mark_s2[c]++;
              }
              else{
                  count = 0;
                  fill(mark_s2.begin(), mark_s2.end(), 0);
              }
              if(count == s1.size())
                  return true;
          }
          return false;
      }
      


    4. Задача 2
      alexeykuzmin0 предложил верное решение использовать BFS01:
      Использовать BFS0-1 вместо алгоритма Форда-Беллмана, описанного в вашем решении. Вершины графа — маршруты, ребра — пересечения маршрутов. Изначально инициализируем 0 все маршруты, которые включают в себя начальную остановку. Ответ — минимум из расстояний до всех маршрутов, включающих в себя конечную остановку.


    5. Задача 3
      The best way to solve this puzzle is to use Kadane’s algorithm which runs in O(n) time. The idea is to keep scanning through the array and calculating the maximum sub-array that ends at every position. The sub-array will either contain a range of numbers if the array has intermixed positive and negative values, or it will contain the least negative value if the array has only negative values.

      И пример на js:
      function getMaxSubSum(arr) {
        var maxSum = arr[0],
          partialSum = 0;
        for (var i = 0; i < arr.length; i++) {
          partialSum += arr[i];
          maxSum = Math.max(maxSum, partialSum);
          if (partialSum < 0) partialSum = 0;
        }
        return maxSum;
      }
      


    Spice IT Recruitment

    70,07

    ИТ специализированное кадровое агентство

    Поделиться публикацией
    Комментарии 78
      0
      В 3й задаче некорректный перевод — там только один массив. Кроме того, как я понимаю, нужно найти неразрывный подмассив, а не подмножество, как указано в заголовке.
        0
        Исправлено.
        +2
        Вопрос 1. — Прямоугольный торт
        Прямоугольный кусок отрезали от края торта (как нормальные люди), или в произвольном месте(как я)?
          0
          Отрезали от края. Но можно попробовать и в произвольном месте вырезать :)
            0
            Тогда уж можно и повернуть, а не горизонтально/вертикально резать.
            А еще можно сделать сам торт или дырку круглыми.
              +1
              Резать нужно через центр торта и центр отверстия, тогда получим две равные части и не важно где отверстие в середине или скраю
        +1
        Честно говоря, ожидал больше от задач.

        1 вопрос — задача о бутерброде. Численно решить легко. В общем виде тоже знакомая (там 2 прямоугольника было и надо было через центры проводить).
        2 вопрос — классика. Понятно что 2 яйцо кидаем по 1 этажу вверх. Ответы и дальше не пишу (под спойлер загнать не могу).

        1 задача — скользящее окно. Сложность O(n+m) дополнительная память O(n)
        2 задача — ориентированный граф, кратчайший путь и всё просто.
        3 задача — шаблонная задача в 1 проход по массиву.
          0
          Можете подавать резюме в Google :)

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

          Задачи — я думаю, интервьюеры будут смотреть на лаконичность/оригинальность решения в том числе.
            0
            Могу сказать, что вторая задача далеко не так проста как кажется. Цель задачи — «За какое минимальное количество попыток Вы сможете это определить?». Как я понял ваш алгоритм, вы предлагаете бросать яйцо через этаж, то есть кинули яйцо на n'ом этаже, и если оно не разбилось, идете на n + 2 этаж. А если разбилось, спускаетесь на n-1 этаж, и проверяете, если не разбилось, то последний этаж n, если разбилось, то n-2. Если максимальный этаж, с которого яйцо не разобьется это 100, то вам потребуется 51 попыток. Вы через один этаж поднимаетесь до 100 этажа — это 50 попыток, плюс вернетесь на этаж ниже и сбросите яйцо, на 99 этаже, что бы убедиться, что максимальный этаж это не 90. Итого 51 попытка. То есть ответ на вопрос этой задачи, используя ваш алгоритм это — 51. Но на самом деле есть другой алгоритм, который позволяет за максимум 14 ходов узнать на каком этаже разобьется яйцо)
              0
              Речь, конечно же, о втором вопросе, а не о второй задаче.
                0
                Само упоминание цифры 14 — уже спойлер. Найти оптимальную стратегию не так сложно, и я думаю, что уважаемый ptyrss её знает. Потому как второе яйцо действительно кидается по одному этажу, не смотря на то, что стратегия первого сложнее. А вот доказать оптимальность и придти именно к 14, имхо, сложнее. Мне давали эту задачку, правда не в гугле, и к оптимуму пришлось придти перебором, хотя конечно же можно проще.
                  0
                  Не правильно понял комментарий ptyrss, и согласен, не следовало писать число.
              +3
              В первой задаче находим «центр масс» исходного торта на пересечении двух диагоналей. Затем так же находим «центр масс» вырезанного куска. Проводим разрез по линии через эти «центры масс». Легкотня (но в стрессе на собеседовании, скорее всего не нашел бы решения, как бы рекрутеры не пытались сделать собеседование максимально расслабленным).
                0
                Способ проще: любой торт с отрезанным куском есть 2 или 3 лежащих рядом прямоугольник. Если особо умные вырезали кусок из середины, то 4. Разрезаем торт на них, а потом каждый из них делим по диагонали.
                  0
                  По условию задачи, вырезанный кусок прямоугольный, но с любым соотношением сторон и ориентацией. Он может быть как угодно повернут относительно исходного торта. Остаток торта на прямоугольники не разрежешь. К тому же разрез нужно сделать единственный.
                    0
                    То есть, сделать 7 разрезов вместо одного — это способ проще?
                    А что вы будете делать, если дырка будет повернута? А если дырка или торт имеют форму круга?
                      0
                      По условию задачи — нужно обойтись одним разрезом
                    0
                    Ответы
                    Вопрос 1 — разрезать надо по толщине, поскольку «одинаковые» здесь не означает «по площади»
                    Вопрос 2 — недавно пробегала, вроде 14. Нужно кидать первое яйцо так, чтобы если оно разбивается в этом броске, оставшихся бросков хватит, чтобы проверить все этажи подряд между текущим и этажом, с которого бросали яйцо предыдущий раз (и оно не разбилось).

                    Задача 1 — нужно использовать скользящее окно (подстроку) в строке 2 длиной в строку 1, и считать количество конкретных символов в ней. Как совпадет с количествами для строки 1, возвращаем true, иначе false.

                    Задача 2 — вроде как обычный поиск на графе, только граф надо собрать правильно. Т.е. вершины будут пары станция-автобус, станция-null будут выходы, дальше орграф строим из любой (х, а) в (у, а) дистанция 0, если а не ноль, из (х, а) в (х,0) дистанция 1, из (х,0) в (х, а) дистанция 0, если а не ноль. Дальше ищем кратчайший путь от (х,0) в (у,0). Вообще эта задача на оптимизацию, и вот это решение довольно тупое — просит О(m*n) памяти, может, можно и покороче.

                    Задача 3 — эту у нас на олимпиаде в 1996м решали, по программированию, кстати. Я тогда был дуб, но решение запомнил — считаем скользящую сумму, пока больше нуля, и отслеживаем максимум, как меньше нуля стала, обнуляем и переносим начало. Решение получается в один проход по массиву чисел.
                      0

                      1 — а если торт из разных слоев? :)

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

                                image
                                  0
                                  Торт на фото как раз неоднородный — верхний слой толще, чем любые внутренние слои того же цвета.
                                    0
                                    Если вы еще не поняли — в природе не существует однородных тортов.
                                    Задачка в принципе поставлена некорректно для нестандартного мышления.
                                      0
                                      Уверены, что некорректно? В задаче сказано «торт прямоугольный», то есть, двумерный.
                                        0
                                        Вы видели когда нибудь нечто подобное — двумерный торт?
                                        Если объект двумерный — то есть абстракция — то его неприемлемо обзывать трехмерным объектом, каким есть торт…
                                        Даже у листа бумаги есть толщина. А тем более у торта.
                                        Только извращенцы думают об двумерной абстракции и обзывают ее тортом…
                                        Задачка о двумерном торте, который всегда трехмерный — однозначно не для логического, а для творческого мышления.
                                          0
                                          В задаче русским по белому сказано, что торт прямоугольный, то есть, двумерный.
                                            –1
                                            А-ха-ха…
                                            Вам гуманитариям объясняли слово синоним, нет в вашем гуманитарном училище?
                                            Тем более не объясняли термин «проекция объемного тела».
                                            Прямоугольный уж точно не синоним двумерный… :)
                                            Вот интересно — реальный торт — он какой в трехмерном случае?
                                            Параллелепипедный?
                                            А кубики магги — они ведь не кубики тоже, хотя в двумерной проекции прямоугольники.
                                              +1
                                              А-ха-ха.
                                              Мы, технари, знаем, что если написано конкретное слово, то синонимы искать незачем. Прямоугольник — двумерная фигура. Из фразы «Прямоугольный торт» однозначно следует двумерность торта.
                                                0
                                                Двумерный — это абстракция, а торт — это объективная реальность.
                                                Желаю вам в Новом Году отрезать и скушать двумерный торт…
                                                На здоровье… :)
                                                Но будьте осторожны — питаясь абстрактными вещами можно умереть с голоду. :)
                                                  0
                                                  Конечно, абстракция. Уже данная нам в условии задачи. А еще в условии задачи, например, слова по-русски написаны, что позволяет предположить, что ответ по-китайски не примут.
                                                  Странно, что приходится это кому-то объяснять.
                                                    0
                                                    Вы не правы сразу во многих вещах. Любая задача — это абстракция, и решать задачу нужно внутри этой же абстракции. Те же яйца, бросаемые с небоскреба. Ведь яйцо может упасть с 10-го этажа на песок и не разбиться, а может и с 9-го на бетон и разбиться.
                                                    Во скажите, вы часто режете торты горизонтальным разрезом? Вот вы свой торт в новом году попробуйте так разрезать, боюсь вас не поймут. В «объективной реальности» торты режут именно вертикальными разрезами, и я вам даже намекну, что это не просто так.
                                                    И ни кубики (кубик 3хмерная фигура) магги, ни гуманитарность, ни ваши «Ха-ха» здесь совершенно не причем.
                                                      0
                                                      Вот смотри — тебе абстрактный 21-слойный торт…
                                                      Каждый из супертонких слоев все равно обладает ТОЛЩИНОЙ.
                                                      Попробуй порежь ТОЛЬКО верхний слой дабы решить задачу.
                                                      Боюсь только теоретически это ты и сможешь.
                                                      … а вот практически — нет.
                                                      Странно мне другое — люди подобной задачей вроде желают найти творческих умных людей…
                                                      … а на самом деле находят решателей абстрактных задач ради абстрактной цели. :)

                                                      image
                                                        0
                                                        Уводите разговор не туда. Ваш рисунок в ОЧЕРЕДНОЙ РАЗ показывает, что по горизонтальным осям он равномерен (масса каждого слоя пропорционально площади), а вот по высоте нет. Замечу, что и на этой картинке разрезы сделаны ВЕРТИКАЛЬНО, что лишний раз должно заставить вас задуматься.
                                                          +1
                                                          kardan2, novrm,alexeykuzmin0, товарищи, двумерный ли торт или объёмный — можно выяснить на конкретном собеседовании, задав уточняющий вопрос интервьюеру.
                                                          Решение с центрами прямоугольников / центрами масс является верным, но предложение резать горизонтально довольно любопытное, мне как-то в голову не пришло :)

                                                          С наступающим :)
                                                            0
                                                            Разговор как раз туда.
                                                            Замените словосочетание «прямоугольный торт» на «прямоугольная рыба» или «прямоугольный компот»…
                                                            Что изменится?
                                                            В вашем смысле — ничего — ибо для вас прямоугольный — значит двумерный, будь то торт, рыба или компот…
                                                            Я же утверждаю — слово ТОРТ в этой задаче или совсем НЕ УМЕСТНО или привнесено специально для полета творческой мысли.
                              0
                              Вы уж извините, но либо я не понял первый вопрос, либо он тривиальнее.
                              Зачем какие-то там находить линии и прочее: просто поставьте торт ребром и разрежьте его пополам. Вот и всё:) По-другому объясняя: сделайте разрез в горизонтальной плоскости торта. Не имеет значение что там и как вырезали — куски будут одинаковы.
                              Как решить второй вопрос «правильно» я не знаю, но знаю, что яйца разбиваются, если их просто так уронить, с рук, не надо высчитывать этажи))
                                0
                                Предположим, что яйцо было обработано известной зубной пастой, не разбивается, если выронить из рук, и даже выдерживает падение с n-ного этажа :)
                                Скрытый текст
                                image
                                0
                                Ваши задачи решаются за три минуты.
                                1) Есть изначальный прямоугольник, и есть вырезанный прямоугольник. Разрез нужно провести через центры обоих. Причем положение вырезанного куска не важно, если он полностью содержится в первоначальном прямоугольнике.
                                2) Задача с яйцами стандартна. В общем случае нужно разбить весь диапазон этажей N на карманы (M), так чтобы М*М=N. Если яиц у нас три, тогда M*M*M=N. В нашем случае N=100, значит M=10. Первым делом проверяем 10 этаж, если яйцо не разбилось, тогда 20, если не разбилось, тогда 30… Т.е. первое яйцо тратим на выявление правильного десятка. А уже вторым яйцом узнаем конкретный этаж внутри этого десятка. Итого за 20 бросков мы гарантировано узнаем нужный этаж. Но этот алгоритм можно оптимизировать, если разбить этажи так, чтобы в первый карман попало больше этажей, чем в последний. Например так: 15-14-13-12-11-9-8-7-6-5. Тогда мы гарантировано узнаем нужный этаж за 16 бросков.

                                Задачи:
                                1) Переводим символы в числа. Т.е. А-1, B-2, C-3…
                                Создаем массив длинной равный количеству букв в алфавите. Записываем в него по индексу букв из первого слова количества раз, которое оно там встречается. Если букв нет, ставим 0. За первый проход по второму слову метим позиции, которые содержат буквы, которых нет в нашем первом слове(в первом примере это буква О). Этим бы быстро исключили заведомо неправильные проверки. По оставшимся позициям делаем так: предварительно создаем ещё один массив такой же длины(1 раз). Обнуляем его. И считаем сколько раз каждая буква попалась. Сверяем его с эталонным массивом (по имеющимся буквам). Если получили совпадение, то оно и есть искомый результат. Сложность O(n*m), где n-длина первого слова, m- длина второго слова. Зачему, что если требуется применить поиск несколько раз к разным словам и разным эталонам, то выделенные массивы нужно всего ли обнулять, т.е. сэкономить на процессе выделении памяти.
                                2) Я здесь вижу немного измененный волновой алгоритм поиска пути в лабиринте. Создаем массив с длиной равной количеству остановок. Забиваем их все очень большим числом. Начальную ячейку (стартовую остановку) делаем равной нулю. Теперь в цикле проигрываем каждый из автобусов. Автобус стартует с первой остановки, запоминая число в ней (K). Если на следующей остановке хранимое число больше, чем K +1, то ложим в него значение k+1.
                                Если же это число меньше чем K, то заменяем запомненное число вместо K. И так до бесконечности, тока ячейка массива финальной остановки не станет равной какому-то числу меньшему изначального. Значение этого числа и будет равно количеству автобусов. Для надежности (может быть найден не самый оптимальный путь), надо прогнать цикл ещё количество раз, которое равно количеству автобусов.
                                Хотя только счас дошло, что это не гарантирует оптимальности в случае, когда приходится пересаживаться между одними и теме же автобусами. Но можно обрабатывать только те ячейки, число в которых не больше чем номер цикла (итерации). Мне кажется, что находить оптимальный алгоритм есть смысл зная количество остановок, количество автобусов, среднее число остановок и разряженность остановок (сколько автобусов проходит через одну остановку). Алгоритмы, которые работают хорошо на плотных массивах могут работать не оптимально на разряженных.
                                Также надо ставить флаг, что за каждый цикл было изменена хоть 1 ячейка. Если флаг не сработал, то задача не имеет решения.
                                3) За один проход. Достаточно знать максимальную сумму массива, которых заканчивался предыдущей (при проходе) ячейкой. Если она больше 0, то плюсуем её со значением текущей ячейки массива, иначе оставляем только текущее значение. Решение очевидно.
                                  0
                                  Вопрос 2. Можно за меньшее число бросаний.
                                  Ключевая идея
                                  Обозначим dp(i, j) ответ на вопрос «какое минимальное количество бросаний требуется для здания высотой i этажей и j яиц?» Очевидно, что dp(i, 1) == i (если яйцо одно, нет выбора, кроме как кидать с каждого этажа). Точно так же dp(0, i) == 0 (если этажей нет, то яйцо не бьется ни с какого этажа).
                                  А дальше переход: dp(i, j) = 1 + min_k{max[dp(k-1, j-1), dp(i-k, j)]}. Почему именно так? Ну, во-первых, нам нужно будет кинуть яйцо 1 раз. Мы будем кидать его с этажа k, и это k выберем таким образом, чтобы максимальное число бросаний, которые нам оставались бы в будущем, было бы минимальным. А сколько бросаний нам останется сделать в будущем? Если яйцо разбилось при падении с этажа k, то у нас осталось для проверки k-1 этаж и j-1 яйцо. А если нет, то, соответственно, i-k этажей и j яиц. Ну и, поскольку нам может не повезти, берем максимум.
                                  Вся задача заключается в подсчете dp(100, 2).

                                  Задача 1. Можно сделать за O(n + m).
                                  Ключевая идея
                                  Незачем проверять массив каждй раз честно. Вместо того, чтобы хранить в ячейке количество вхождений буквы в подстроку, лучше хранить разность между этим количеством и количеством вхождений в искомый паттерн. Тогда «нашлось» — это массив из всех нулей.
                                  В отдельной переменной храним количество ненулевых элементов массива. При сдвиге подстроки у нас изменяется только 2 ячейки массива — изменяем их и обновляем эту переменную.

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

                                  Задача 2. У вас сложность O(n * m), а можно сделать за O(n + m).
                                  Ключевая идея
                                  Использовать BFS0-1 вместо алгоритма Форда-Беллмана, описанного в вашем решении. Вершины графа — маршруты, ребра — пересечения маршрутов. Изначально инициализируем 0 все маршруты, которые включают в себя начальную остановку. Ответ — минимум из расстояний до всех маршрутов, включающих в себя конечную остановку.
                                    0
                                    Задача 1.
                                    Итак, нам нужно проверить вхождение слова «АБ» в слове из 10 букв. Для этого нам придется сделать цикл из (10-2) итераций, и в каждом проверить на нулевые значения 2 ячейки(потому что первое слово состоит из 2-х букв). Всего 8*2 действий. Теперь нужно найти скажем слово «АБВГ». Оно потребует (10-4) итерации, в каждой из которых нужно проверить 4 элемента массива. Всего действий 6*4=24.
                                    Теперь ищем слово из 4-х букв в слове из 20 букв, т.е. увеличивает в 2 раза оба слова. В результате получаем (20-4)*4 = 64 проверки, а это увеличение в 4 раза, а не в 2!
                                    И где здесь O(n + m)? Тут явная O(n * m).
                                    И именно из-за этого я не стал дальше оптимизировать свой алгоритм, хотя приведение к нулю — просто само бросается в глаза.

                                    Задача с яйцами ваше решение почти не убежало от моего.
                                      0
                                      Всё, дошло. Вместо того, чтобы проверять массив на нули каждый раз, мы можем вести счетчик нулевых (или не нулевых) элементов, фиксируя каждое изменение массива.
                                      Итого, нам нужно сделать n операций для первоначального заполнения отрицательными значениями первого слова, затем посчитать n первых букв во втором слове (первое положение окна), а дальше сделать (m-n-1) сдвигов окна убирая из массива старую букву и прибавляя новую букву. Итого n+n+2*(m-n-1)=2m-2 действий. Но тогда почему O(m+n), а не O(m)? По моим выкладкам получается, что от длины первого слова ничего не зависит.
                                        0
                                        Но тогда почему O(m+n), а не O(m)? По моим выкладкам получается, что от длины первого слова ничего не зависит.
                                        Ваша правда
                                      0
                                      Насчет задачи с автобусами. По всей видимости я не правильно понял условия: если автобус двигается abcd, то он идет из a в b, из b в c, из с в d, а после d он уже никуда не идет. Т.е. его движение однонаправлено. Т.е. он может из a приехать в d, но не может из d приехать в a. Наверное меня сбил с толку пример, где все движение показано в одном направлении. И в таком случае это совсем иная задача.
                                    0
                                    БАЯН! задачу 2 еще в институте разбирали в рамках темы «АЦП половинного деления-последовательного приближения».
                                    Решение в лоб — последовательное приближение, но тут надо использовать комбинированный метод.
                                    Сначала нужно идти половинным приближением (1,2,4,8,16,32,64, бац!), когда первое яйцо разобьется, откатить на предыдущий цикл и продолжить последовательным приближением (33,34,35...)
                                    итого при разбитии яйца на N этаже
                                    методом последовательного приближения = N попыток
                                    методом половинного последовательного приближения = floor(log2(N))+(N-2^(floor(log2(N))))

                                    Вопрос в задаче, как и в большинстве подобных задач, поставлен некорректно. Отвечая формально на вопрос «За какое минимальное количество попыток Вы сможете это определить?» можно смело отвечать «За одну попытку! Кинули со первого этажа оно и разбилось.» Может это трудности перевода?
                                      0
                                      методом половинного последовательного приближения = floor(log2(N))+(N-2^(floor(log2(N))))
                                      При N=100 по этой формуле получается 42 попытки, при оптимальном решении в 14.
                                        +1
                                        Вас не смущает, что по вашему алгоритму этаж 63 будет найден за 7+30=37 попыток?
                                        «За одну попытку! Кинули со первого этажа оно и разбилось.» Может это трудности перевода?
                                        Имеется ввиду за какое минимальное количество попыток вы найдете гарантированно ответ. Т.е. рассматривается наихудший вариант при известном количестве этажей. Рациональней оставлять большие промежутки как раз в начале (нижние этаже), а вот на верхних наоборот уплотнять.
                                        В случае же бесконечного количества этаже, мне кажется что надо делать шаг не 2^n, а n^2.
                                        0
                                        Вопрос #2 — баян, решается либо с помощью динамического программирования, либо аналитически. Разбиралась на типичном программисте, а так же в видео уроках Игоря Клейнера (уроки по динамическому программированию и интеревью для программистов).
                                          0
                                          Да, про яйцо задача, пожалуй, классическая, как и про автобус с шариками, например. Но баян это для отдельных разработчиков, и такие вопросы ещё задают на собеседованиях, как показывает практика.
                                            0
                                            Абсолютно согласен.
                                            0
                                            Да тут все задачи боян
                                            0
                                            С яйцами решить «бинарным поиском» не лучший вариант?
                                              +1
                                              Можно сделать лучше.
                                                0
                                                И последний, это алгоритм кадана или что-то есть лучше?
                                                  0
                                                  Насколько мне известно для такой постановки ничего лучшего не придумали.
                                                    0
                                                    Легко доказать, что алгоритм Кадана асимптотически оптимален
                                                    +1
                                                    Какой блин бинарный поиск? При дихотомическом делении у вас на любом шаге может быть либо больше, либо меньше, либо равно. А в данной задаче у вас «меньше» ДОЛЖНО выпадать не больше 2-х раз, причем второй раз на последней попытке.
                                                      +1
                                                      Скорее всего автор имел в виду имея 1 яйцо максимально приблизить к промежутку этажей (т.е. бросаем с этажа N/2, если разбилось, то искомый этаж находится в промежутке от 1 до N/2-1, если нет — то в промежутке от N/2+1 до N, далее рекурсивно), в котором имеется такой, начиная с которого яйца начинают разбиваться. Дальше имея оставшееся яйцо найти сам этаж последовательным перебором. Это неоптимальное решение, но одно из первых наивных, которые обычно приходят в голову.
                                                        +1
                                                        В случае, если правильный этаж попадает в первую половину (первое яйцо сразу разбивается), то вторым яйцом придется проходить аж половину пути. Т.е. при полном значении 100 этажей, 49 этаж будет найден за 50! попыток. Это не то что не оптимальное, это одно из худших решений. Хуже только полный перебор.
                                                          0
                                                          Ну да, поэтому от кандидата, ожидают другое решение. Оно ИМХО не очень очевидное, если нет опыта решения подобных задач.
                                                          Повторюсь, бинарный поиск — это одно из наивных решений, которые, обычно первыми приходят в голову (вместе с полным перебором).
                                                            +1
                                                            Даже если есть опыт решения, то не всегда понятно что делать? Не всегда догадываешься, что вообще яйца можно бросать с этажей (и какие действия вообще можно делать). Мне кажется, что правильней показать человеку вариант полного перебора, и попросить его оптимизировать решение.
                                                        0
                                                        Предлагал самый настоящий бинарный, с делением каждый раз на 2 :)
                                                        Просто невнимательно прочитал условия задачи и пропустил самое главное — что яиц всего два.
                                                        Тут получается первое яйцо кидаем каждые 10 этажей, как разбилось то второе кидаем через этаж с последнего «целого» десятка.
                                                        Медленнее бинарного поиска, но целее будут яйца.
                                                          0
                                                          А нет, был не прав :) Ответ найден.
                                                    0
                                                    Задача #3 — одна из классических задач на динамическое программирование. Есть куча способов как ее решить. Например алгоритм Кадана (Kadane's algorithm) или с помощью техники «разделяй и властвуй». На образовательном канале Игоря Клейнера имеется несколько разделов, посвященных динамическому программированию. Там подробно разбирается эта задача, а так же задача про 2 яйца (правда там были даны 2 сферы).
                                                      0
                                                      2reci
                                                      Задача с анаграммами. Вы уверены, что ваш алгоритм работает правильно?
                                                      Мне кажется, что он не сможет найти слово АБАБВ в слове ААБАБВГД.
                                                        0
                                                            public static final int ALPHABETSIZE= 256;
                                                            public static boolean  findSubstrAnagram(String subword, String word){
                                                                if(subword.length()>word.length()){
                                                                    return false;
                                                                }
                                                                int[] array = new int[ALPHABETSIZE];
                                                                int difference =0;
                                                                for(int i=0; i<subword.length(); i++){
                                                                    char c = subword.charAt(i);
                                                                    if(array[c]==0){
                                                                        difference ++;
                                                                    }
                                                                    array[c]--;
                                                                }
                                                                for(int i=0; i<subword.length(); i++){
                                                                    char c = word.charAt(i);
                                                                    if(array[c]==0){
                                                                        difference++;
                                                                    }
                                                                    if((++array[c])==0){
                                                                        difference--;
                                                                    } 
                                                                }
                                                                if(difference==0){
                                                                    return true;
                                                                }
                                                                for(int i=subword.length(); i<word.length(); i++){
                                                                    char c = word.charAt(i);
                                                                    if(array[c]==0){
                                                                        difference++;
                                                                    }
                                                                    if((++array[c])==0){
                                                                        difference--;
                                                                    }
                                                                    
                                                                    c = word.charAt(i-subword.length());
                                                                    if(array[c]==0){
                                                                        difference++;
                                                                    }
                                                                    if((--array[c])==0){
                                                                        difference--;
                                                                    }
                                                                    if(difference==0){
                                                                        return true;
                                                                    }
                                                                }    
                                                                return false;
                                                            }


                                                        Это мой вариант. Он имеет сложность O(m). Код конечно можно причесать, выделить повторяющиеся участки…
                                                          0
                                                          Спасибо за вариант, чуть позже смогу проверить.
                                                        0
                                                        В алгоритме Кадана тоже ошибка.
                                                          0
                                                          Где именно? Можете привести пример?
                                                            0
                                                            Он не работает если массив целиком состоит из отрицательных чисел, вместо минимального числа он вернет 0.
                                                              0
                                                              Замечание принято, поправил с допущением, что массив не пустой.
                                                              +1
                                                              Если немного изменить код, то должно работать
                                                              function getMaxSubSum(arr) {
                                                                var maxCurrent = maxGlobal = arr[0];
                                                                for (var i = 1; i < arr.length; i++) {
                                                                  maxCurrent = Math.max(arr[i], maxCurrent + arr[i]);
                                                                  maxGlobal = Math.max(maxGlobal, maxCurrent);
                                                                }
                                                                return maxGlobal;
                                                              }
                                                              


                                                              Тут без проверки на пустой массив, но суть ясна :)
                                                            0
                                                            Интересная конечно, задача с яйцами, чисто математическая.
                                                            После 5 падения яйцо уже не будет тем, что прежде (происходит деформация)

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

                                                            Самое читаемое