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

    Мы подготовили для вас новый сет задач и вопросов, задаваемых на собеседованиях в ведущих IT-компаниях.

    КДПВ

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

    Вопросы


    1. Transport the bananas
      A person has 3000 bananas and a camel. The person wants to transport maximum number of bananas to a destination which is 1000 KMs away, using only the camel as a mode of transportation. The camel cannot carry more than 1000 bananas at a time and eats a banana every km it travels. What is the maximum number of bananas that can be transferred to the destination using only camel (no other mode of transportation is allowed).
      Перевод
      У человека есть 3000 бананов и верблюд. Он хочет отвезти максимум бананов в пункт назначения, находящийся в 1000 км, используя верблюда в качестве транспорта. Верблюд не может перевозить более 1000 бананов за раз и ест по одному банану за каждый километр пути.
      Какое наибольшее количество бананов удастся доставить таким способом (другие способы перевозки не разрешены)?
    2. Measure forty-five minutes using wires
      How do we measure forty-five minutes using two identical wires, each of which takes an hour to burn. We have matchsticks with us. The wires burn non-uniformly. So, for example, the two halves of a wire might burn in 10 minute and 50 minutes respectively.
      Перевод
      Имеется 2 идентичных шнура, каждый из которых сгорает за час. Спички у нас с собой, шнуры сгорают неравномерно. Так, например, половина может сгореть за 10 минут и оставшаяся половина за 50 минут. Как, используя эти шнуры, нам отсчитать 45 минут?

    Задачи


    1. Elephants lifetime
      Given life time of different elephants. Find the period when maximum number of elephants were alive.

      Input: [2005, 2010], [2006, 2015], [2002, 2007]
      Output: [2006, 2007] .
      Перевод
      Дано время жизни нескольких слонов. Найти период, в который жило наибольшее количество слонов.

      Вход: [2005, 2010], [2006, 2015], [2002, 2007]
      Выход: [2006, 2007] .

    Pythagorean Triplet
    Given an array of integers, write a function that returns True if there is a triplet (a, b, c) that satisfies a^2 + b^2 = c^2.

    Example:

    Input: arr[] = {3, 1, 4, 6, 5}
    Output: True
    There is a Pythagorean triplet (3, 4, 5).

    Input: arr[] = {10, 4, 6, 12, 5}
    Output: False
    There is no Pythagorean triplet.
    Перевод
    Дан массив целых чисел, нужно написать функцию, возвращающую True, если в массиве содержится тройка чисел (a, b, c), так, что a^2 + b^2 = c^2

    Пример:

    Вход: arr[] = {3, 1, 4, 6, 5}
    Выход: True
    Пифагорова тройка — (3, 4, 5).

    Вход: arr[] = {10, 4, 6, 12, 5}
    Выход: False
    Пифагоровской тройки в массиве нет.

    Anti-clockwise rotated array
    Consider an array of distinct integers sorted in increasing order. The array has been rotated (anti-clockwise) k number of times. Given such an array, find the value of k.

    Array rotation:

            *                     *
            0                     1                      
        5        1    =>      0        2
        4        2            5        3
            3                     4
    

    Examples:

    Input: arr[] = {15, 18, 2, 3, 6, 12}
    Output: 4
    Initial array must be {2, 3, 6, 12, 15. 18}. We get the given array after rotating the initial array twice.

    Input: arr[] = {7, 9, 11, 12, 5}
    Output: 1

    Input: arr[] = {7, 9, 11, 12, 15};
    Output: 0

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

    Поворот массива означает:

            *                     *
            0                     1                      
        5        1    =>      0        2
        4        2            5        3
            3                     4
    

    Примеры:

    Вход: arr[] = {15, 18, 2, 3, 6, 12}
    Выход: 4
    Исходны массив должен быть — {2, 3, 6, 12, 15. 18}. Мы получим входной массив, если повернем исходный 2 раза.

    Вход: arr[] = {7, 9, 11, 12, 5}
    Выход: 1

    Вход: arr[] = {7, 9, 11, 12, 15};
    Выход: 0

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

    Решения


    1. Вопрос 1
      На первый взгляд кажется, что верблюд, могущий везти только 1000 бананов при расходе 1 банан/км, придёт пустым к 1000-километровой отметке. Однако ключ к решению — в промежуточных остановках. Будем исходить из предположения, что верблюд потребляет 1 банан/км будучи груженым и порожним. Тогда, остановки на расстоянии >=500 км не имеет смысла делать (минимум, 2 остановки), получается такой план маршрута:
                         ===туда===>
                        <===сюда====    ===туда===>
      И (исходная точка) ===туда===> А <===сюда==== Б ===туда===> Ц (цель)
                        <===сюда====    ===туда===>
                         ===туда===>	 
      

      Обратим внимание, что стоимость километра на отрезке ИА — 5 бананов, на отрезке АБ — 3 банана, на отрезке БЦ — 1. Чтобы сохранить максимум бананов, мы должны постараться сократить наиболее затратные отрезки.
      Из точки А верблюд сможет увезти максимум — 2000 бананов, следовательно в точку Б должно быть доставлено 2000 бананов, откуда можно получить длину ИА: 3000 — 5ИА = 2000, т.е. ИА = 200 км.
      Расчёт АБ аналогичен. Поскольку, из Б верблюд увезёт максимум — 1000 бананов, длина АБ получается 2000-3АБ = 1000, т.е. АБ = 333⅓. Длина БЦ — 466⅔, а к цели будет доставлено 533⅓ бананов.

      Правильный ответ также был предложен в комментариях.

    2. Вопрос 2
      В комментарии был дан верный ответ. Действительно, как бы неравномерно ни сгорал шнур, если зажечь его с двух сторон — он сгорит за полчаса. Следовательно, сначала нужно зажечь один шнур с двух сторон, один — только с одной. Когда первый догорит (значит прошло полчаса) — поджечь второй шнур со второго конца, он будет гореть еще 15 минут. Итого — 45 минут.

    3. Задача 1
      В комментариях были предложены верные алгоритмы, но не было примеров кода.
      Вариант решения:

      #include <iostream>
      #include <iomanip>
      #include <iterator>
      
      using namespace std;
      
      typedef struct{
          int birthYear;
          int deathYear;
      }LIFE;
      
      typedef struct{
          int startYear;
          int endYear;
      }PERIOD;
      
      int FindMinStartYear(LIFE* anmimals, int len)
      {
          int startYear = anmimals[0].birthYear;
      
          for(int i = 1; i < len; ++i){
              if(anmimals[i].birthYear < startYear){
                  startYear = anmimals[i].birthYear;
              }
          }
      
          return startYear;
      }
      
      int FindMaxEndYear(LIFE* anmimals, int len)
      {
          int endYear = anmimals[0].deathYear;
      
          for(int i = 1; i < len; ++i){
              if(anmimals[i].deathYear > endYear){
                  endYear = anmimals[i].deathYear;
              }
          }
      
          return endYear;
      }
      int FindPeriodOfMaxAnimal(LIFE* anmimals, int len, PERIOD& p)
      {
          int startYear = FindMinStartYear( anmimals, len);
          int endYear = FindMaxEndYear( anmimals, len);
      
          int* period = new int[endYear - startYear + 1];
          for(int i = 0; i < endYear - startYear + 1; ++i){
              period[i] = 0;
          }
      
          for(int i = 0; i < len; ++i){
              for(int j = anmimals[i].birthYear; j <= anmimals[i].deathYear; ++j){
                  period[j - startYear]++;
              }
          }
      
          cout << endl;
          copy(period, period + endYear - startYear + 1, ostream_iterator<int>(cout, "  "));
          cout << endl;
      
          int maxAnimals = period[0];
          int maxStart = 0;
          int maxEnd = 0;
      
          for(int i = 0; i <= endYear - startYear; ++i){
              if(period[i] > maxAnimals){
                  maxStart = i;
                  maxAnimals = period[i];
              }
      
              if(period[i] == maxAnimals){
                  maxEnd = i;
              }
          }
      
          delete[] period;
      
          p.startYear = maxStart + startYear;
          p.endYear = maxEnd + startYear;
      
          return maxAnimals;
      }
      
      int main(int argc, char* argv[])
      {
          LIFE testCases[] = {
              {5, 11},
              {6, 18},
              {2, 5},
              {3, 12}
          };
      
          PERIOD p;
          int maxAnimals = FindPeriodOfMaxAnimal(testCases, sizeof(testCases)/sizeof(testCases[0]), p);
      
          cout << "In the period " << p.startYear << " and ";
          cout << p.endYear << ", there are " << maxAnimals << endl;
      
       return 0;


    4. Задача 2
      Вариант решения с сортировкой:
      // A C++ program that returns true if there is a Pythagorean
      // Triplet in a given array.
      #include <iostream>
      #include <algorithm>
      using namespace std;
       
      // Returns true if there is a triplet with following property
      // A[i]*A[i] = A[j]*A[j] + A[k]*[k]
      // Note that this function modifies given array
      bool isTriplet(int arr[], int n)
      {
          // Square array elements
          for (int i=0; i<n; i++)
              arr[i] = arr[i]*arr[i];
       
          // Sort array elements
          sort(arr, arr + n);
       
          // Now fix one element one by one and find the other two
          // elements
          for (int i = n-1; i >= 2; i--)
          {
              // To find the other two elements, start two index
              // variables from two corners of the array and move
              // them toward each other
              int l = 0; // index of the first element in arr[0..i-1]
              int r = i-1; // index of the last element in arr[0..i-1]
              while (l < r)
              {
                  // A triplet found
                  if (arr[l] + arr[r] == arr[i])
                      return true;
       
                  // Else either move 'l' or 'r'
                  (arr[l] + arr[r] < arr[i])?  l++: r--;
              }
          }
       
          // If we reach here, then no triplet found
          return false;
      }
       
      /* Driver program to test above function */
      int main()
      {
          int arr[] = {3, 1, 4, 6, 5};
          int arr_size = sizeof(arr)/sizeof(arr[0]);
          isTriplet(arr, arr_size)? cout << "Yes": cout << "No";
          return 0;
      }
      


    5. Задача 3
      При внимательном рассмотрении задачи, можно заметить, что число поворотов массива равно длине массива — индекс минимального элемента, который можно найти бинарным поиском. Вариант решения:

      // Binary Search based C++ program to find number
      // of rotations in a sorted and rotated array.
      #include<bits/stdc++.h>
      using namespace std;
       
      // Returns count of rotations for an array which
      // is first sorted in ascending order, then rotated
      int countRotations(int arr[], int low, int high)
      {
          // This condition is needed to handle the case
          // when array is not rotated at all
          if (high < low)
              return 0;
       
          // If there is only one element left
          if (high == low)
              return low;
       
          // Find mid
          int mid = low + (high - low)/2; /*(low + high)/2;*/
       
          // Check if element (mid+1) is minimum element.
          // Consider the cases like {3, 4, 5, 1, 2}
          if (mid < high && arr[mid+1] < arr[mid])
             return (mid+1);
       
          // Check if mid itself is minimum element
          if (mid > low && arr[mid] < arr[mid - 1])
             return mid;
       
          // Decide whether we need to go to left half or
          // right half
          if (arr[high] > arr[mid])
             return countRotations(arr, low, mid-1);
       
          return countRotations(arr, mid+1, high);
      }
       
      // Driver code
      int main()
      {
          int arr[] = {15, 18, 2, 3, 6, 12};
          int n = sizeof(arr)/sizeof(arr[0]);
          int sizearr = n -1 ;
          int countr = sizearr -countRotations(arr, 0, sizearr);
          cout << countr;
          return 0;
      }
      


    Spice IT Recruitment
    82.22
    ИТ специализированное кадровое агентство
    Share post
    AdBlock has stolen the banner, but banners are not teeth — they will be back

    More
    Ads

    Comments 88

      +2
      Второй вопрос простой:

      1) Сначала зажигаем первую веревку с обоих концов, а вторую с одного.
      2) Когда первая сгорит (а это произойдет ровно через 30 минут!) зажигаем вторую веревку с другого конца. Как догорит, так и 45 минут.
        0
        Есть другой способ
        Зажигаем первую с двух сторон — она сгорит за 30 минут, затем зажигаем вторую с двух сторон и из центра, т.о. огонь будет идти в 4-х направлениях и веревка сгорит за 15 минут, а в сумме как раз 45 искомых.
          +1
          Не сработает. Поджигание верёвки одновременно с концов и посередине не гарантирует, что каждая половина сгорит за одно и то же время. Первая половина может сгореть за 5 минут, а вторая за 25.
            0
            Да, согласен, не предусмотрел этот момент
            +1
            Есть ещё другой способ:
            При условии, что обе веревки имеют неравномерные сгорания одинаково, то поджечь первую с обеих сторон, а вторую с обеих сторон и с точно того же места, где догорела первая. Так 30+15=45
              0
              В комменарии автора (где-то ниже ) написано, что концы неотличимы, но, по условиям задачи, веревки одинаковые.

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

              Вот тут бы и помогла идентификация концов — 30 мин можно было бы померять положив веревки «навстречу» друг други и зажечь их опять же навстречу друг другу. Как точки горения совпадут так и 30 мин. Потом опять их сдвигаем конец к началу и опять ждем совпадения точек горения. Но вот если концы таки неотличимы, я пока не понимаю, что делать.
          0
          3000 бананов
          В итоге получится перевезти 500 бананов, скормить верблюду 2400 и 100 останется в пустыне, если первые 500км каждые 100км провозить все что есть, возвращаясь назад.
          0. 3000 бананов
          100км. 2500 бананов (взял 1000 бананов с отметки 0 привез 900 бананов, взял 100 бананов, поехал на отметку 0, повторил)
          200км. 2000 бананов
          300км. 1700 бананов
          400км. 1400 бананов
          500км. 1100 бананов
          Далее берем 1000 бананов и едем в конечный пункт
          600км. 900 бананов
          700км. 800 бананов
          800км. 700 бананов
          900км. 600 бананов
          1000км. 500 бананов

            0
            А почему это максимум?
              +1
              Ага, можно больше довезти таким способом, а именно:

              1) Тащим бананы на отметку 200 км за 5 ходок, где окажется 3000-200*5=2000 бананов.
              2) Тащим бананы далее на 333 км за 3 ходки до отметки 533 км, где окажется 1001 банан.
              3) Тащим 1000 бананов до конца. Дистанция 467 км. Итого довозим 1000-467 = 533.

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

                На х километров возможно перевезти только (1000-2х) бананов, при условии что нужно возвращаться. Стоимость перевозки при этом окажется бананов, которые будут съедены.
                Целевая функция оптимизации — это количество полезной нагрузки делить на количество съеденных бананов.
                f(x)= (1000-2x)/2x -> max
                Берем производную, приравниваем к нулю и находим х

                Это — обычная гипербола, которая стремиться к бесконечности около нуля. Ответ — максимальная производительность при минимальном шаге. Проверим численно:
                Едем на 500 километров — получаем 0 полезной нагрузки и 1000 бананов съедено
                Едем на 1 километр — получаем 998 полезной нагрузки и 2 съеденных банана.
                Получается, все итерационные циклы выгоднее всего делать с минимальным шагом. Допустим, наш минимальный шаг будет 1 (в случае дробного шага результат будет почти таким же — но об этом в конце)

                Дальше — excel, хотя сейчас я понимаю, что можно и мысленно было:
                Этап 1 — перевозим все доступные бананы за 3 ходки на 1 километр за каждый шаг.
                Этап 1. Шаг 1. Перевозим все бананы на 1-ый километр. Расход — 6 бананов за три ходки. Итог — доступно 2994, все находятся на 1-ом километре.
                Этап 1. Шаг 2. Перевозим все доступные бананы с 1-ого на 2-ой километр. Расход — 6 бананов. Итог — доступно 2988, все находятся на 2-ом километре.


                Этап 2. На 167 километре у нас будет доступно 1998 бананов. С этого момента, стоимость перевозки всех бананов на следующий километр будет 4 банана.
                Этап 2. Шаг 1. Перевозим все бананы с 167-ого на 168-ой километр. Расход — 4 банана, итог — доступно 1986 бананов.


                Этап 3. На 666 километре у нас остается 1000 бананов. С этого момента вся модель перестает работать, потому что нам больше не нужно возвращаться. Это то самое краевое условие, которым мы пренебрегли. Берем все бананы и едем до конца.
                Расход — 334 банана, итог — 666 бананов на 1000-ом километре.

                Если бы бананы были бесконечно делимы, то с почти нулевым шагом мы бы перевезли 2/3 всех бананов как предел ряда. Точно ряд сейчас не сформулирую, но думаю ход мысли понятен.
                  0

                  "На 666 километре у нас остается 1000 бананов". Почему? На 167 было было 1986. Перевоз на 1км занимает 4 банана. Тогда 986/4=246 км, то есть 1к можно доставить только до 167+246=413км

                    +2
                    Ваша правда, спасибо. В таком случае, ответ 533, который уже был озвучен ранее. Смысл целевой функции сохраняется, получается просто теоретическое обоснование максимального результата
                    0
                    Этап 1. Шаг 1. Перевозим все бананы на 1-ый километр. Расход — 6 бананов за три ходки. Итог — доступно 2994, все находятся на 1-ом километре.


                    Ну, на этом шаге Вы посчитали один лишний банан, потому что, чтобы увезти все 3000 бананов на 1 км верблюд пройдет 5 км — 3 раза туда и 2 обратно.

                    Этап 2. На 167 километре у нас будет доступно 1998 бананов. С этого момента, стоимость перевозки всех бананов на следующий километр будет 4 банана.


                    На 200-м километре останется 2000 бананов, далее километр будет стоить 3 банана.

                    Этап 3. На 666 километре у нас остается 1000 бананов.


                    Это как??? 10001 банан останется на отметке 200+333=533 км. Даже если начинать с 200 км…

                      +1
                      Итого 534/533 банана в зависимости от алгоритма верблюда. Кстати везти можно не по километру, а до точки слома модели. Т.е. первых три перехода в точку 200км, тогда от первой и второй 1000 остается 600, а от третьей 800.
                      Далее два перехода в точку 533 км.
                      Остается вопрос — нет ли точки где выгодно выбросить часть бананов. Точнее не возвращаться за ними. Имеется ввиду что мы изменим длины переходов как-то таким образом, что при последнем переходе в целевую точку, на предыдущей точке останется бананов столько же сколько стоит доставка из нее. Можно подумать что выбрав такие точки мы можем увеличить полезную загрузку.
                      Предположим что есть такой участок в пределах первых 200км и в точку 200км можно прийти не 3, а 2 раза. Но придя два раза, при любой загрузке невозможно получить более 1998 бананов, а у нас уже есть решение которое позволяет получить в этой точке 2000 бананов, что больше. Аналогичные рассуждения можно привести и для точки 533 км. И того максимум это 533 или 534 банана в зависимости от алгоритма верблюда, так как в точке 533 км становится важным ест ли верблюд свой банан авансом.
                    0

                    Тут можно было получить 534 банана: не обязательно давать верблюду банан после того как он достиг километра 1000

                      0
                      Это зависит, от от того, как устроен верблюд: «утром деньги, вечером стулья» или «утром стулья — вечером деньги» :)
                        +1

                        Если он сперва ест а потом идет, то пре переходе из шага 2 в 3 сьест банан номер 1001 на старте и потратит 466 на остаток пути

                          0
                          Он еще может только на половине километра его есть. Или непрерывно есть. А по условиям задачи бананы могут ехать только на верблюде. Так что, как повезет.
                      0
                      Так-то
                      1) 200 км за 5 ходок = 200*5*2, верблюду надо возвращаться и его надо тоже кормить. За 200км мы теряем 2000 бананов, а не 1000.
                        0
                        Моя «ходка» — это в одну сторону, Т.е верблюду надо пройти 200*5=1000 км и сожрет он при этом именно что 1000 бананов.
                          0
                          Согласно задаче у нас есть только 1 верблюд. Чтобы вторую ходку сделать, ему надо вернуться. Это стоит учитывать.
                            0
                            Все учтено.

                            Еще раз, туда 200 км, обратно 200 км, туда 200 км, обратно 200 км, туда 200 км. Итого 5 раз по 200 км. Что не так то?
                      +1
                      Если идти по одному километру то получається 533 банана.
                        0
                        Не понимаю, как так получается, потому что при таком подходе верблюд значительную часть времени будет недогруженным (как решении IgnisDeus), а жрать все равно по банану на километр, в то время как у меня получились те же 533 банана при 100% загрузке верблюда.

                        Хотя результаты моего первого шага совпадают с результатом 2-х первых шагов решения IgnisDeus, где верблюд тоже в конце второго шага тащил лишь 500 бананов.
                          0
                          А верблюд потребляет бананы только тогда, когда ходит нагруженный? Когда ходит пустой — не потребляет?
                            0
                            По условиям задачи — всегда. 1 банан на 1 километр.
                            +2
                            А неважно какой именно отрезок проходить. Важно то, что пока бананов больше 2000 расход 5 бананов на километр. Больше 1000 — 3 банана на километр.
                            Следовательно, на первой тысяче бананов верблюд пройдёт 1000/5= 200 км. На второй тысяче — 1000/3= 333.(3) километров. После чего у него останется идти 1000 — 533 = 467 км, на которые он потратит 467 бананов. Значит останется 533 банана. Всё. По сколько именно идти в пределах этих километров значения не имеет.
                              0
                              Этот вариант мне каженся самым простым решением. Если задасться вопросом об оптимальном расстоянии то тут важны точки излома. То есть првое перемещение должно быть 0 < X <=200. Если например перенести на 201 км. то мы потеряем на нем два банана (5 — 3) т.к. ходок на последнем километре будет 5 а могло уже быть три.
                              0
                              А если взять эталонную дистанцию в районе 300-400кма затем каждую следующую часть переносить на несколько меньшую дистанцию.? Верблюд все равно будет есть в процессе а значит можно будет попутно добирать бананы с чекпоинтов.
                                0
                                В вашем варианте верблюд будет по дороге съедать свой груз. Полностью он загружен только в начале каждого этапа, а, например, в точке 100км на первом этапе он будет нести 900 бананов.
                                  +1
                                  Всё просто. Первые 200 км верблюду нужно пройти пять раз, независимо от того, будет он делать ходки по 200 или по одному километру. Следующие 333⅓ километра необходимо пройти три раза, и остаток пути — один раз. Таким образом, пройденное расстояние будет 200×5 + 333⅓×3 + (1000 — 200 — 333⅓) = 2466⅔ километра. Если за последние ⅔ км верблюду банан не дать, то в конечный пункт прибудет 534 банана.
                                0
                                Как донести 750 бананов
                                (считаем, что верблюд не потребляет бананы, не будучи нагруженным)

                                1. Берём 1000 бананов, каждый километр один банан съедаем, один кладём. На 500 км поворачиваем назад
                                2. Берём 1000 бананов, проходим 500 км (остаётся 500 бананов), раскладываем бананы ещё на 250 бананов ещё на 250 км.
                                3. Берём последнюю тысячу бананов, первые 750 км питаемся разложенными бананами, последние 250 съедаем, 750 доносим.
                                  0
                                  И даже 833 ⅓
                                  Опять таки, по аналогии с другими решениями — пустой верблюд бананов не потребляет

                                  1. Идём 333 ⅓ км, оставляем каждый километр по два банана (на отметке 333 ⅓ оставляем две трети банана, треть съедаем), идём назад пустые
                                  2. Проходим 333 ⅓ на оставленных бананах (один остаётся лежать), далее раскладываем ещё на 500 км вперёд по одному банану на километр
                                  3. Проходим 833 ⅓ на оставленных бананах, съедаем 166 ⅔ банана на оставшиеся километры, доносим 833 ⅓
                                    +2

                                    С таким предположением можно и больше: двигаемся по 1 км до 333км. Получаем 2001 банан. Выкидываем 1. Движемся на км 833 (сейчас км стоит 2 банана). Получаем 1000. Движемся оставшиеся 167км. Доставляем 834 банана (последний банан верблюду не даем т.к. мы уже у цели).

                                    0
                                    А на возвращение верблюд не тратит бананы?
                                      0
                                      533/534 банана
                                      Пока бананов больше 2000, расход идёт 5 бананов/км. Проходим 200 км.
                                      Пока бананов больше 1000, расход идёт 3 банана/км. Проходим ещё 333 км.
                                      Итого на точке 533 км остаётся 1001 банан и остаётся пройти 467 км.
                                      +2
                                      Первая задача тоже была бы легкая, если бы было указано, что все даты (годы?) разные — тогда надо смешать годы рождения и смерти в общий список и отсортировать его по возрастанию года (не забывая, это год рождения или смерти) а потом пробежаться по списку, прибавляя или отнимая единицу от изначально нулевого счетчика в зависимости от того, что это за дата. Ответ ищется в том же проходе. Пока счетчик растет, запоминаем/передвигаем начало периода, как упадет, запоминаем период и число живых слонов. И так далее (может встретиться второй максимум)…

                                      А вот если год смерти одного слона совпадает с годом рождения другого слона, тут непонятно, был ли момент времени, что оба слона были живы?
                                        0
                                        Задача не до конца определена как мне кажется. Но есть пример который показывает как поступать с границами периодов. Поэтому я бы решал так. В сначала пришёлся бы по всем слонам и создал бы массив год -> число слонов. Потом нашёл бы в этом массиве максимум возможно не один и представил уже в виде интервалов. Если быть уже совсем строгим то год рождения и смерти нужно исключать т.к. мы показывает в интервале период о 0101 00:00:00 и рождениеслона в этот момент невероятно.
                                        +1
                                        А что такого сложного в третьей задаче? Идем по массиву, как i-й элемент оказался меньше предыдущего, так и все. Если дошли до конца, ответ — 0

                                        P.S. Ну, можно еще после нахождения k дойти до конца, для проверки валидности входных данных…
                                          +1
                                          думаю, что важно упомянуть о том, что решений может быть бесконечно много с периодом, равным длине массива
                                            0
                                            Думаю, что нет. В примерах к 3-й задачи есть ответы. И в этих ответах (то чего хотят поручить) есть всего 1 значение. Поэтому и мы должны давать 1 значение в качестве ответа.
                                            0
                                            Предположим, 2-й элемент оказался меньше предыдущего, тогда каков будет ответ?
                                              0
                                              Ответ 1.
                                              0
                                              Наверное предполагалось что будет небольшая оптимизация. Фактически нужно сравнивать границы последовав ателье ости если сортировка нарушена то делить пополам или другим способом и брать отрезок где сортировка опять же нарушена. Пока не останется отрезок длинной два.
                                              0
                                              Вопрос 2. — Видел задачу в другом месте (хотя сам не решил)
                                              Задача 3. — Поиск минимума? Или пары рядом стоящих чисел, когда первое больше второго.
                                              Задача 2. За 1 проход заносим в Хэш значения квадратов элементов. А далее двойным циклом складываем квадраты элементов и проверяем наличие такого же значения в Хэше.
                                              Задача 1. Необходимо определиться, как интерпретировать [2000,2010],[2010,2020], т.е. случай когда год смерти одного слона совпадает с годом рождения другого слона. Можно ли считать, что [2000,2020] жил ровно 1 слон, или же [2010,2010] жило 2 слона.
                                              Предположим первое. Заводим Хэш, где год — ключ, а значение — +1 если это дата рождения, -1 если это дата смерти. Если в 1 год родилось 5 слонов, а умерло 2, тогда в хеше будет 5-2=3. Затем выгружаем все не нулевые значения Хэша в массив, сортируем его, и за 1 проход получаем решение. Сложность O(n*lon(n)) за счет сортировки.
                                              Можно по иному пойти, выгрузить даты рождения в 1 массив, а смерти в другой массив. Отсортировать оба, и совместным прохождением по обоим массивам найти ответ. Сложность та же.

                                              Про бананы и верблюда ещё думаю.
                                                0
                                                Можно по иному пойти, выгрузить даты рождения в 1 массив, а смерти в другой массив. Отсортировать оба, и совместным прохождением по обоим массивам найти ответ. Сложность та же.

                                                Если работать с массивами дат, то наглядней перевести их в множества (set в Python) и найти результирующее множество сделав пересечение множеств. Потом берем минимум и максимум из этого результирующего множества.
                                                0
                                                У меня получилось максимум всего лишь 416 бананов.
                                                Сначала забрасываем бананы на 250-ый километр в три этапа, итого там будет 1500 бананов, половину мы потеряем, скормили прожорливому верблюду.
                                                Затем закидываем на 416-ый километр остальные 1000 бананов, потеряв 500 бананов.
                                                Основная цель — это найти максимальный километр, куда можно закинуть 1К бананов.
                                                Дальше грузим всю тысячу и идем до конца, в итоге довозим всего лишь 416 бананов.
                                                  0
                                                  Если забрасывать бананы сразу на 250км то теряется лишние 100=(250-200)*2 банана
                                                    0
                                                    Хотя я чуть неправильно посчитал, на 250 у меня будет 1750.
                                                    Ну да, если на 200-ый, то мы там будем иметь там 2000 бананов.
                                                    Едем на 333 км еще, оставляем на 533-ем 333 банана, возвращаемся, берем 1К, в итоге привозим 533 банана.

                                                    По моей схеме имеем 1750 на 250-ом км.
                                                    Отвозим еще на 250 км, на 500-й 250 бананов, возвращаемся за 1К, едем в конечную точку, подбираем на 500-ом 250 бананов, в итоге получается привезем 500 бананов.

                                                    Да, получается, что на 200-ый лучше сначала.
                                                      0
                                                      Важны только точки когда кончается очередная тысяча бананов. То есть можно везти до 200 через несколько перевалочных пунктов
                                                  0
                                                  Anti-clockwise rotated array
                                                  По-моему у вас ошибка в примерах ответа: в первом случае ответ — 4, во втором — 1 и в третьем все правильно — 0

                                                  my $arr = [ 15, 18, 2, 3, 6, 12 ]; 
                                                  
                                                  sub get_turn_count
                                                  {
                                                      my $arr = shift;
                                                      my @sorted = sort { $a <=> $b } @$arr;
                                                  
                                                      my $k = 0;
                                                      while( 1 )
                                                      {
                                                          last if( join( ',', @$arr ) eq join( ',', @sorted ) );
                                                  
                                                          $k++;
                                                          unshift( @$arr, pop( @$arr ) );
                                                      }
                                                  
                                                      return $k
                                                  }
                                                  
                                                  print get_turn_count( $arr ), " \n";
                                                  
                                                    0
                                                    Вы правы, почему-то мысленно поворачивал по часовой, поэтому не заметил расхождения условий с примером. Исправлено.
                                                      0
                                                      Да, зря я поленился написать код с unit-тестами, в результате чего, чего, честно говоря, тоже «решил» задачу про поворот по часовой стрелке. Т.е. правильный ответ будет что-то типа n-i, где i — результат «моего» вчерашнего алгоритма.

                                                      P.S. Ваш код, наверное (я даже язык не могу угадать) правильный, но сильно неэффективный. Сначала сортировка массива, а потом в цикле еще и циклический сдвиг. Т.е. сложность типа O(N^2). А можно O(N).
                                                        0
                                                        Язык Perl.
                                                        Сортировка — это O(log N) один раз.
                                                        А дальше стандартные функции для работы с массивами, со списками добавление элемета в начало массива и выталкивание последнего. Не могу точно сказать какая тут сложность, но если это динамический массив, то тоже O(N) получается.
                                                          0
                                                          Сортировка — это O(log N) один раз.


                                                          Сортировка O(log N)? Скорее O(N*log N). а это уже больше O(N)…

                                                          Ну, стоимость прокрутки массива, если это не плоский массив, а список, действительно может стоить фиксированное время, но уж сравнение двух массивов длиной N на равенство (в прошлый раз не заметил), опять N/2 раз, это уж точно получится O(N^2).
                                                            0
                                                            Хотя сортировка — это O(n log n)
                                                            А сравнение двух массивов — это O(2N), причем по сортированному не нужно было мне проходится в цикле каждый раз, можно было бы join его вычислить перед циклом, так что сложность сравнения тут O(N)
                                                            Итого O(n log n) + k * O(N)
                                                              0
                                                              Да, но в худшем случае k=N, в среднем k=N/2. А ответ ищется одним линейным проходом по массиву. Как нашли a[i-1] > a[i], так и ответ нашли (N-i, если индексация начинается с нуля). Если не нашли, ответ 0.
                                                                0
                                                                В задаче кажется требовался только ответ с числом в условии. Но линейный проход не обязателен можно искать делением массива пополам.
                                                                  0
                                                                  А можно на код посмотреть?
                                                                    0
                                                                    Буду рядом с компьютером напишу. А что есть подозрение что будут проблемы?
                                                                      0
                                                                      Были. Я по scientific computing специализируюсь, А тут, вроде и не поиск корня, или экстремума у выпуклой функции, поэтому и самому в голову не пришло, и в Вашем подходе, мягко говоря, засомневался.

                                                                      Только после третьего вашего сообщения решил на всякий случай картинку на бумажке нарисовать и теперь на могу с Вами не согласиться. Действительно O(log N), причем независимо ни от чего. Снимаю шляпу.

                                                                      P.S. А код напишите для фиксации рекорда.
                                                                        0
                                                                        Код я имел в виду такой. Но теперь я понимаю что Ваш вариант был правильный а мой нет. Весь вопрос как трактовать тексо возрастающая последовательность. Я могу ошибаться но кажется возрастающая и неубывающая это разные вещи. То есть возрастающая не подразумевает повторения значений. Но не сказана что последовательность возрастающая а сказано отсортирована по возрастанию. То есть она неубывающая в строгом смысле. Если значения будут повторяться (неубывающая) то вот такой массив будет проанализировать проще протым перебором при этом от начала и до конца
                                                                        [5,5,5,5,5,5,5,5,5]
                                                                        [5,5,5,5,5,2,5,5,5].

                                                                        Я так понимаю что давая такую задачу тестирующий хочет понять какие у тестируемого будут варианты проверки и будет ли он проходить массив от начала и до конца и остановится ли на первом равестве 5 = 5 значит ротация была 0.

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

                                                                        var array = [2,3,6,7,8,9,1]
                                                                        
                                                                        console.log(rotatedBy(array));
                                                                        
                                                                        function rotatedBy(array) {
                                                                          var left = 0; 
                                                                          var right = array.length - 1;
                                                                          var middle;
                                                                          if (array.length <=1 || array[left] < array[right]) {
                                                                            return 0;
                                                                          }
                                                                          while (right - left > 1 && array[left] > array[right]) {
                                                                            middle = Math.floor((left + right) / 2);
                                                                            if (array[left] > array[middle]) {
                                                                               right = middle;
                                                                            } else {
                                                                               left = middle;
                                                                            }
                                                                          }
                                                                          return array.length - right;
                                                                        }
                                                                        
                                                                          0
                                                                          и кстати для массива [5,5,5,5,5,5,5,5] задача как бы вырождается и вариантов будет от 0 до длины массива минус один. А может быть это тест на адекватность? Если тестируемый начинает задавать тестирующему такие вопросы то он в каждой задаче будет видеть проблемы там где их нет?
                                                                            0
                                                                            Все нормально, в условии задачи сказано, что все числа разные.
                                                                              0
                                                                              Да посмотрел — of distinct integers. Я читал только русский перевод. И немного затормозил на этом.
                                                                    0
                                                                    Да, вы правы, вот так гораздо эффективнее:
                                                                    my $arr = [ 15, 18, 2, 3, 6, 12 ]; 
                                                                    
                                                                    sub get_turn_count
                                                                    {
                                                                        my @arr = @_;
                                                                        my $min = List::Util::min( @arr );
                                                                    
                                                                        my $k = 0;
                                                                        foreach ( @arr )
                                                                        {
                                                                            if( $arr[ 0 ] == $min and $arr[ - 1 ] != $arr[ 0 ] )
                                                                            {
                                                                                last;
                                                                            }
                                                                            unshift( @arr, pop( @arr ) );
                                                                            $k++;
                                                                        }
                                                                    
                                                                        return $k;
                                                                    }
                                                                    
                                                                    print get_turn_count( @$arr ), " \n";
                                                                    
                                                                    
                                                            0
                                                            По условию задачи, массив был отсортирован и потом «повернут» несколько раз. Т.к. он отсортирован, первый элемент — минимальный. Каждый поворот смещает первый элемент на 1 влево (первый раз — в конец массива). Таким образом, за один проход ищем минимальный элемент и запоминаем его позицию. Ответ n-k+1. Отдельно обрабатывается случай когда минимальный — первый элемент, значит поворотов не было (или было n).
                                                            Для поворота в другую сторону ответ k-1.
                                                            P.S. Возможно, я неправильно понял условие задачи, но мне непонятно зачем в решении поворачивать входной массив. Нам ведь не надо восстановить отсортированный? Также мое решение исходит из того, что на входе — корректные данные, т.е. это действительно отсортированный массив, который «повернули». Для восстановления исходного массива достаточно сделать еще один проход (в копию ставим элементы на нужный индекс), для проверки сортировки — тоже один с попарным сравнением с предыдущим элементом.
                                                              0
                                                              Да, вы правы, переставлять элементы тут лишнее.
                                                              use List::Util ();
                                                              
                                                              my $arr = [ 15, 18, 2, 3, 6, 12 ]; 
                                                              
                                                              sub get_turn_count
                                                              {
                                                                  my @arr = @_;
                                                                  my $min = List::Util::min( @arr );
                                                              
                                                                  my $k = 0;
                                                                  foreach ( 0 .. $#arr )
                                                                  {
                                                                      if( $arr[ $k ] == $min and $arr[ $k - 1 ] > $el )
                                                                      {
                                                                          last;
                                                                      }
                                                                      $k++;
                                                                  }
                                                              
                                                                  return scalar( @arr ) - $k;
                                                              }
                                                              
                                                              print get_turn_count( @$arr ), " \n";
                                                              
                                                            0
                                                            У меня вопросы по шнурам:
                                                            1. То что одна половина горит 10 мин, а другая 50 мин — это конкретные условия задачи или просто как пример, на самом деле время может отличаться и оно не известно?
                                                            2 Если целиком шнур горит неравномерно, то половины горят равномерно?
                                                            3. Можно ли отличить концы шнуров, т.е. с какой стороны быстрее, а с какой медленнее сразу же, до зажигания?
                                                              0
                                                              1. Функция длины сгоревшей части шнура — монотонно возрастающая непрерывная функция, равная нулю при T=0 и равная длине шнура при T=1 час. Все.
                                                              2. Половины по длине? Нет. См. п.1
                                                              3. Нет. см. п.1
                                                                0
                                                                1. Точное время горения половин неизвестно. Может быть 15/45, например. А могут и равномерно, я думаю.
                                                                2. Нет.
                                                                3. Нет.
                                                                  0
                                                                  И как же нам тогда решать такую задачу прикажите? Может быть вы что-то не договариваете?
                                                                  Даже если ее и можно решить, то решение на порядок не очевидней, по сравнению с другими задачами, у них ответ лежит почти на поверхности.
                                                                    +1
                                                                    Так она уже решена. См. первый комментарий.
                                                                0
                                                                Задачу с массивом можно решить за O(log N) бинарным поиском. Сначала берем первый элемент и средний (в одну из сторон, тут неважно), если средний больше первого, минимум в верхней части массива, если меньше, то в нижней. Продолжаем, пока длина массива не станет 2, тогда тот элемент, что меньше из двух, и будет минимальным. Индексы считаем параллельно нахождению минимума, и выдаем индекс наружу, потом если он 0, то массив не сдвинут, если не ноль, то вычитаем его из длины (так как массив сдвигался влево), получаем ответ.
                                                                  0
                                                                  Возможно, я неправильно понял алгоритм, но мне кажется он сломается на примерах {2,3,4,5,1} и {5,1,2,3,4}.

                                                                  Проблема с бинарным поиском в том, что числа расположены не монотонно. Например, для {3,4,5,1,2} ряд возрастает до третьего элемента, а потом убывает.

                                                                  Поправьте меня, если я ошибся.
                                                                    0
                                                                      0
                                                                      В данном случае бинарный поиск как раз ищет это расхождение но не прямым перебором а делением отрезка на два. Процесс заканчивается когда отрезок будет иметьровно два элемента. Из них правый элемент это и будет бывший первый эемент списка.
                                                                    0
                                                                    Задачу с верёвкой я бы решал «сложением» :)
                                                                    Нужно сложить одну верёвку пополам, а вторую — вчетверо.
                                                                    Когда первая верёвка полностью сгорит, пройдёт 30 минут. Когда вторая — ещё 15 минут.
                                                                      0
                                                                      Про бананы мне кажется можно проще объяснить, чем через функции. Пока условно предположим, что перевозим максимум на 1 км. потом возвращаемся. На первые километры тратится по 5 бананов на километр (пока не останется 2000, или потратить 1000), затем по 3 (пока не останется 1000 или снова потратить 1000) и дальше по одному.
                                                                      Итого первую тысячу (5 бананов на км) мы потратим за 200 км. вторую за 333 (1 банан теряем так как его перевозка дороже его самого) ну и последнюю 1000 везем оставшиеся 467км, значит с тысячи довезем 533.
                                                                        0
                                                                        Расстояния не обязательно кратны километра и нет уверенности что такой ответ действительно максимум и не даёт ключа к решению в общем случае. Например сколько будет от 3007 бананов.
                                                                          0
                                                                          сколько будет от 3007 бананов

                                                                          На семь бананов при макс.загрузке 1000 проехать удастся только 1км., т.е. привезем на один банан больше (534).


                                                                          нет уверенности что такой ответ действительно максимум и не даёт ключа к решению в общем случае.

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


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

                                                                            0
                                                                            Целый банан не означает целого километра в одну сторону. Это мтожет быть три ходуи по 1/3 километра. Я просто мог немного подготовить данные так чтобы эти части бананов накапливались и у вашего способа получилось расхождение. Но даже не это главное. Главное что в общем методе все решается проще и точнее.
                                                                            +1
                                                                            Согласен — такое объяснение сработает только в целых числах. В случае деления километров и бананов превратиться в:
                                                                            Итого первую тысячу (5 бананов на км) мы потратим за 200 км. вторую за 333.(3), ну и последнюю 1000 везем оставшиеся 466.(6) км, значит с тысячи довезем 533,(3). При условии «непрерывного потребления» в конце.
                                                                          0
                                                                          Про бананы прочитал несколько неправильных решений. Почему-то многие забывают кормить верблюда на обратном пути в промежуточных ходках…
                                                                          Верблюды
                                                                          Моё решение в 444 банана, и я не знаю как больше. Отнесём 333 банана на треть пути, съев треть от тысячи на пути туда, и треть — обратно. Отнесём 444 банана на 444 км, съев 444 банана. Ещё 111 съедим на пути назад до 333 километра, там подбираем оставленые бананы, чтобы хватило добраться до дома. Берём последнюю 1000 бананов и везём на 444 километр, там подсаправляемся до упора и идём на целевую точку. Эфективность веблюда получается меньше 15% =(


                                                                          Задачу со шнурами видел слишком много раз

                                                                          Слоны:
                                                                          создадим из данных вида [2006, 2010] записи вида 2006-тру, 2010-фолс. Отсортируем записи со всех слонов по году. Теперь пройдемся от начала до конца, создавая список. Каждому новому интервалу времени между фактами рождения/смерти слона добавляем новый элемент списка вида [ количество_слонов = запись[i].ключ? список[i-1].количество_слонов + 1: список[i-1].количество_слонов + 1;
                                                                          где нулевой элемент создаётся с нулем слонов.
                                                                          Потом ищем номер элемента с большим числом слонов. Он равен номеру записи с началом соответствующего интервала времени. Конец — в следующем элементе массива записей.
                                                                          Задача решается за две сортировки по всем данным. Дополнительно можно оптимизировать обработку одинаковых годов, но если таких много, то быстрее создавать меньший массив из всех годов. Зависит от того, какие данные — больше чем один слон в год, или меньше. Также разумно встроить дополнительную проверку на ноль в последнем элементе списка.

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

                                                                          ...и последняя
                                                                          Тут мы просто идём по массиву и сравниваем значение с предыдущим, пока неравенство не сработает. Можно идти от начала к концу и вычесть потом из длинны массива, а можно сразу идти с конца и инкрементировать счётчик оборотов, потом просто брейкануть цикл и вывести его.
                                                                            0
                                                                            В чем ошибка такого решения: habrahabr.ru/company/spice/blog/348122/#comment_10653124 (533.5 банана)?
                                                                              0
                                                                              Все верблюды накормлены. Были правда попытки зажать полбанана после работы но это уже наш менталитет. Нести бананы на треть пути сразу невыгодно ту передаются лишние бананы. Первая остановка должна быть максимум на 200 км
                                                                                0
                                                                                Да, я нашёл меньшее решение. Но я не понял почему именно столько в том решении.
                                                                                Если мы предполагаем что «перевезти больше всего бананы на некоторую промежуточную базу 1, использую ровно тысячу, перевезти больше всего бананов на базу 2, используя ровно тысячу, овезти все бананы до конца» — это оптимальная стратегия, то я разобрался почему именно 534 — это максимум. Но почему эта стратегия оптимальна? Где доказательства что перевозка на одну базу а не две, или на 6, или через каждый км не будет эффективнее? Как именно формально доказать что это наиболее эффективно?
                                                                                  0
                                                                                  Никто не говорит что должно быть три базы Главное что базы обязательно должны быть в указанных трёх точках. Если мы сделаем 199 баз до 200 км и следующую на 201 км то. 5-кратная ходка будет сделана на 1км больше что повлечет за собой расход лишних двух бананов

                                                                            Only users with full accounts can post comments. Log in, please.