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

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

    КДПВ

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

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

    Надеемся, что мы достигли этой цели.

    Вопросы


    1. Утка в пруду
      A duck that is being chased by a fox saves itself by sitting at the center of circular pond of radius r. The duck can fly from land but cannot fly from the water. Furthermore, the fox cannot swim. The fox is four times faster than the duck. Assuming that the duck and fox are perfectly smart, is it possible for the duck to ever reach the edge of the pond and fly away to its escape from the ground?

      Перевод
      Утка, преследуемая лисой, спасается в центре круглого пруда радиусом r. Утка может взлететь с земли, но не с воды. Лиса же не умеет плавать. Также, лиса в 4 раза быстрее утки. Предположив, что утка и лиса абсолютно разумны, возможно ли для утки достичь берега и улететь?
    2. Ящики с фруктами (и ярлыками)
      In front of you are three boxes. One contains only apples, one contains only oranges and one contains a mix of apples and oranges. Each box is incorrectly labeled, like this:
      Box 1: “apples”
      Box 2: “oranges”
      Box 3: “apples & oranges”

      Question: You get to choose one, and only one, box. I will remove a randomly selected piece of fruit from your chosen box and show it to you (so you can tell if it’s an apple or an orange). After that, you will be able to accurately and definitively relabel all three boxes

      Перевод
      Перед Вами 3 ящика. Один содержит только яблоки, второй — только апельсины, а третий — и яблоки и апельсины. На каждом ящике неправильно повешенный ярлык, вроде:
      Ящик 1: «яблоки»
      Ящик 2: «апельсины»
      Ящик 3: «яблоки и апельсины»

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

    Задачи


    1. Умножить без оператора умножения
      Write a function that takes the produce of two given integers without using the multiplication operation. Try to do this as fast as you can (O(log(n) or better)

      Перевод
      Написать функцию, которая возвращает произведение 2-х целых числе без использования оператора умножения. Постарайтесь реализовать с максимальной производительностью (O(log(n) или лучше).
      Я видел также вариацию этой задачи, где требовалось реализовать умножение без операторов умножения, деления, циклов и побитовых операторов.
    2. N-е простое число
      Write a function that returns the nth prime number. For example, nthPrime(1) should return 2 since 2 is the first prime number, nthPrime(2) should return 3, and so on.

      Перевод
      Напишите функцию, возвращающую n-ое простое число. Например:
      nthPrime(1) => 2 (поскольку 2 является первым простым числом),
      nthPrime(2) => 3
      и т.д.
    3. Найти следующее число с теми же цифрами
      Given a number N, find the next number that has same set of digits as n and is greater than N. If N is the greatest possible number with its set of digits, then print “not possible”.
      Ex:
      N = «218765» => «251678»
      N = «1234» => «1243»
      N = «4321» => «Not Possible»
      N = «534976» => «536479»

      Перевод
      Дано число N, нужно найти следующее число, имеющее тот же набор цифр и большее чем N. Если N — самое большое из возможных комбинаций, вывести «not possible».
      Пример:
      N = «218765» => «251678»
      N = «1234» => «1243»
      N = «4321» => «Not Possible»
      N = «534976» => «536479»

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

    Решения


    1. Вопрос 1
      Действительно, движение по прямой к берегу для утки не является выигрышным, поскольку лиса быстрее в 4 раза, она будет у точки выхода раньше: (π * r) < (4 * r).

      Утка может плавать кругами, а если радиус круга < r/4, то она проплывет этот круг быстрее лисы, и за несколько кругов сможет встать напротив лисы так, что между ними будет центр пруда. Допустим, что утка начала плавать на дистанции r/4-x (где x — бесконечно малая величина), тогда до точки выхода:
      — для утки 3/4r+x
      — для лисы π*r

      Очевидно, что π*r < 4 (3/4 r +x), и утка может улететь.

    2. Вопрос 2
      Необходимо выбрать 1 предмет из ящика с табличкой «Яблоки+Апельсины».
      Поскольку табличка неправильная, в этом ящике либо только яблоки, либо только Апельсины.
      Предположим, мы достали яблоко. Правильная табличка для этого ящика: «Яблоки».

      На оставшихся двух ящиках таблички «Яблоки» и «Апельсины», среди них один ящик с апельсинами и один ящик со смесью.
      Таблички по условию на них неправильные, значи апельсины находятся в ящике с табличкой «Яблоки», а смесь — в ящике с табличкой «Апельсины».
      Если бы достали из первого ящика апельсин, решение было бы аналогичным.

    3. Задача 1
      Один из вариантов решения — рекурсия:

      #include<stdio.h>
      /* function to multiply two numbers x and y*/
      int multiply(int x, int y)
      {
         /* 0  multiplied with anything gives 0 */
         if(y == 0)
           return 0;
       
         /* Add x one by one */
         if(y > 0 )
           return (x + multiply(x, y-1));
        
        /* the case where y is negative */
         if(y < 0 )
           return -multiply(x, -y);
      }
       
      int main()
      {
        printf("\n %d", multiply(5, -11));
        getchar();
        return 0;
      }


    4. Задача 2
      Вариант ответа:
      
      #include <stdio.h>
      #include <stdlib.h>
      #include <math.h>
      #define MAX 100000000
      
      void prime(int n, int *primes)
      {
          int i,j,count=0;
      
          primes[count++] = 2;
          if (count == n)
              return;
          for(i=3;i<=MAX;i+=2)
          {
              int isPrime=1;
              int jMax = sqrt(i);
              for(j=3;j<=jMax;j+=2)
              {
                  if(i%j==0)
                  {
                      isPrime=0;
                      break;
                  }
              }
              if(isPrime)
              {
                  primes[count++] = i;
                  if(count==n)
                      return;
              }
          }
      }
      
      int main()
      {
         int n,i;
      
         scanf("%d",&n);
         int arr[n];
         int maxPrime = 0;
      
         for(i=0;i<n;i++)
         {
             scanf("%d",&arr[i]);
             if (arr[i] > maxPrime)
                 maxPrime = arr[i];
         }
         int primes[maxPrime];
         prime(maxPrime, primes);
         for (i=0;i<n;i++)
         {
             printf("%d\n", primes[arr[i]-1]);
         }
         return 0;
      


    5. Задача 3
      Оригинальное решение:
      
      #include <iostream>
      #include <cstring>
      #include <algorithm>
      using namespace std;
       
      // Utility function to swap two digits
      void swap(char *a, char *b)
      {
          char temp = *a;
          *a = *b;
          *b = temp;
      }
       
      // Given a number as a char array number[], this function finds the
      // next greater number.  It modifies the same array to store the result
      void findNext(char number[], int n)
      {
          int i, j;
       
          // I) Start from the right most digit and find the first digit that is
          // smaller than the digit next to it.
          for (i = n-1; i > 0; i--)
              if (number[i] > number[i-1])
                 break;
       
          // If no such digit is found, then all digits are in descending order
          // means there cannot be a greater number with same set of digits
          if (i==0)
          {
              cout << "Next number is not possible";
              return;
          }
       
          // II) Find the smallest digit on right side of (i-1)'th digit that is
          // greater than number[i-1]
          int x = number[i-1], smallest = i;
          for (j = i+1; j < n; j++)
              if (number[j] > x && number[j] < number[smallest])
                  smallest = j;
       
          // III) Swap the above found smallest digit with number[i-1]
          swap(&number[smallest], &number[i-1]);
       
          // IV) Sort the digits after (i-1) in ascending order
          sort(number + i, number + n);
       
          cout << "Next number with same set of digits is " << number;
       
          return;
      }
       
      // Driver program to test above function
      int main()
      {
          char digits[] = "534976";
          int n = strlen(digits);
          findNext(digits, n);
          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 46

      0
      Утка не жилец, т.к. (Pi*R/4) < R
        0
        Утка может никуда не лететь, и ждать (плавать) в центре озера, пока лиса обессилит, соответственно ее скорость может снизиться :)
          +1
          точно, и вообще лисе надоест, она скажет: «Да, нафиг мне сдалась эта утка» и пойдет отжимать дом у зайца.
          0
          Утка как раз жилец, задача не была бы такой простой. Решение — сдвинуться от лисы на небольшое расстояние (например, 1/100r) и затем повернуть на 90 градусов.
          утка пройдёт. От лисы до утки в момент касания берега будет 1,2r минус маленькое число в зависимости от того, это было. 1/100 или 1/100.
          если лиса передумала бежать и сменила направление назад, то утка тоже меняет направление на 180 градусов. Итого утка не в центре, а лиса на прежнем месте. Повторяем процесс.
            0
            Я исхожу из того, что никуда утка сдвинуться не может, т.к. она находится не на острове в середине пруда, а на бесконечно малой точке в середине, такой, что любое движение на бесконечно малое расстояние из этой точки и она оказывается в воде. Т.к. в задаче не сказано, может ли она двигаться в середине острова и на какое растояние, то либо надо уточнить у интервьюера, либо рассчитывать на худший вариант, ибо в лучшем никто никуда не полетит, а лисе надоест и она уйдет.
              +3
              Ок, решение попроще (не моё). Утка двигается от центра на кольцевую линию окружности на расстоянии четверти радиуса от центра. После этого она делает круг по этому кольцу чтобы встать напротив лисы (по угловой скорости она быстрее).
              Далее плывёт к берегу.
                0
                Да, тоже нашел решение в сети, так что утка сможет выжить.
                  0
                  Ну как «тоже»… Это коллега решил со вторым кругом.
                  0

                  Что-то у меня не сходится…
                  На четверти радиуса получаем длину 1/2 Pi R
                  длина окружности озера — 2 Pi R
                  Лиса в 4 раза быстрее => скорость утки на этом радиусе и лисы одинакова. Вопрос — как утке встать в противофазу?

                    +2
                    Если утка проплывет хотя бы миллиметр к центру озера, то по новой окружности (радиус R/4 — 1) она будет быстрее, а значит может выбрать свою позицию. Поскольку это справедливо и для миллиметра и 0,1 миллиметра и даже нанометра, для краткости решения указывают просто четверть радиуса.
            +2

            Многовато ошибок в формулировках.


            "Вопрос 2" неразрешим без важнейшего условия — в начальный момент ВСЕ ящики помечены неправильно.


            В "задаче 1" также отсутствует важное условие — нужно умножить не какие-то произвольные inputs, а именно integers.

              0
              reci верно, это нужно добавить в условие.
                0
                То то я смотрю вторая задача вроде как не решается.
                  0
                  Логарифмировать, сложить, потенцировать. Любые два числа.
                    0
                    Вы правы, так логичнее. Добавил в условие
                    +1
                    Задача 1 явно недостаточно сформулирована. Какие операции можно использовать? Учитываем ли мы, что операции (сложение, скажем) могут работать разное время в зависимости от входных данных? Что такое n? Если n — это длина наших чисел, то быстрее, чем за O(n log n) мы ничего не умножим, а за эту сложность — есть БПФ.
                    А если нет ограничений на операции и выполняются они все за O(1), я могу и exp(log(a) + log(b)) написать. Сомневаюсь, что это то решение, которое имелось в виду.
                      +1
                      Если n — это длина наших чисел, то быстрее, чем за O(n log n) мы ничего не умножим, а за эту сложность — есть БПФ.
                      Да ну ладно вам… N — длина числа в битах. Скорее всего, они имеют ввиду алгоритм по мотивам того как это делается аппаратно:
                      uint_t a = 5;
                      uint_t b = 1000;
                      uint_t mask = 1;
                              
                      uint_t result = 0;
                              
                      for (uint_t n = 0; n < sizeof(uint_t) * 8; ++n) 
                      {
                          if ((a & mask) != 0)
                              res += b;
                      
                          mask <<= 1;
                          b <<= 1;
                      }

                      вполне за O(N) делается. Правда, совсем аппаратно можно и за O(1), но это не интересно.
                      Дальше из этого классического алгоритма можно сделать log(N), рекурсивно складывая вершины дерева состоящего из результатов попарных сложений.
                        0
                        А я думаю, что n — это само число. Соответственно его длинна в битах — это log(n). Кстати, в вашем примере есть оператор умножения. Но в целом решение правильное.
                        На аппаратном уровне есть ОПЕРАЦИЯ УМНОЖЕНИЯ, поэтому задача в такой постановке скорее абсурдна.
                          0

                          И где здесь быстрее, чем за O(n)? У вас в цикле битовый сдвиг и сложение, которые сами за O(N) делаются.

                            0
                            А почему битовый сдвиг и сложение делается не за O(1)? Это же 1 операция. Тут что 1+1 сложить, что 10000+10000.
                              +1

                              Потому, что у нас длина числа — не константа, а N. Оно может не уместиться в int32_t.
                              А если число короткое, то ваш код работает за O(1), ведь его время работы ограничено сверху константой.

                              0
                              Это просто базовая идея алгоритма — умножение в столбик. Дальше я описал словами, так как нужно развернуть цикл руками и получится слишком много кода. Но идея такая — в базовом варианте N — сложений и каждое не зависит от результата, а только от «своего» бита. Следовательно мы может разложить эти слагаемые:
                              (1-е + 2-е) +
                              (3-е + 4-е) +
                              (5-е + 6-е) +
                              (6-е + 7-е) +

                              будет N/2 сложений. Дальше к результатам рекурсивно применяет тот же алгоритм. В итоге получится log(N) сложений и сдвигов.
                                0
                                Если
                                будет N/2 сложений
                                то ваш алгоритм за O(n) работать ну никак не может. Потому что для одного сложения двух чисел длины n нам нужно O(n) времени.

                                А насчет дерева не понял, что вы имеете в виду. В записи
                                (1-е + 2-е) +
                                (3-е + 4-е) +
                                (5-е + 6-е) +
                                (6-е + 7-е)
                                Ровно 7 знаков сложения, столько же, сколько и при отсутствии скобок. Или вы каким-то образом бесплатно считаете суммы в скобках?
                                  0
                                  Все зависит от того, что считать элементарной операцией. Так как в изначальных условиях это не оговорено, то я считаю сложение двух N-разрядных чисел элементарной операцией, вы — нет. В рамках моей постановки, я правильно оцениваю сложность.
                                  Ровно 7 знаков сложения, столько же, сколько и при отсутствии скобок. Или вы каким-то образом бесплатно считаете суммы в скобках?
                                  Я имею ввиду, что эти суммы, на практике, можно считать параллельно, так как они не зависят друг от друга. Без конкретики, что является элементарной операцией, спор бессмыслен. Условия слишком размыты. Например, мне никто не мешает рассматривать N как константу, и тогда в железе ваши 7 сложений будут иметь сложность O(1), если есть аналог SIMD. Собственно, так и есть на практике в железе — умножение выполняется примерно как O(1).
                                    0
                                    За О(1) можно сложить только числа не более, чем константной длины. А если у нас числа константной длины, то мы можем хоть перебором искать их произведение, все равно сложность будет O(1), ибо ограничена константой. Такая постановка задачи особого смысла не имеет. Именно поэтому я предполагаю, что длина чисел произвольна (разумеется, на реальном собеседовании я бы уточнил это у интервьювера, но здесь такой возможности, увы, нет, и поэтому приходится довольствоваться наиболее вероятным объяснением).
                                    А учитывая, что число ядер у нас константно (не растет с увеличением длины числа), оно может дать рост производительности не более, чем в константу раз. То есть, асимптотическую оценку не меняет.

                                    Итого:
                                    • Если числа длиной O(1), сделать за О(1) не представляет труда — например, ваш алгоритм будет за О(1) работать.
                                    • Если числа произвольной длины, то их сложение займет O(N) времени, поэтому умножение быстрее, чем за O(N) сделать вообще нельзя. Наиболее быстрый алгоритм, известный Википедии, работает за O(n log n 2^(log* n)). Кроме того, количество ядер всегда константа, и поэтому не влияет на асимптотику решения.
                                    • Если числа у нас произвольной длины, то мы можем их умножать за O(N) операций сложения. Но зачем кому-то в здравом уме оценивать производительность умножения, используя за единицу измерения именно операцию сложения? Это какая-то странная величина, ее полезность непонятна.
                                      0
                                      Согласен с вами.
                                      Если числа у нас произвольной длины, то мы можем их умножать за O(N) операций сложения. Но зачем кому-то в здравом уме оценивать производительность умножения, используя за единицу измерения именно операцию сложения? Это какая-то странная величина, ее полезность непонятна.
                                      Я могу лишь предположить, что все эти «тесты», когда-то раньше, имели под собой практическую основу и выросли из реальных практических задач.
                                      Вот, ситуация когда сложение занимает O(N) у меня была лишь один раз — когда я реализовывал библиотеку «длинной» арифметики, и там ваш подход полностью оправдан. Во всех остальных задачах, всегда были разумные ограничения на битность числа и сложение всегда было O(1). А вот умножения, совсем еще недавно, каких-то 20 лет назад, могло вообще не быть. Я сам начинал программировать с ассемблера и именно с такой архитектуры, где не было умножения. В случае умножения констант, умножение, почти всегда, можно было заменить на сдвиги или/и сложения. Но иногда, приходилось умножать честно — вот тут и нужны все эти алгоритмы и выкрутасы.
                                        0
                                        Как задача на ассемблер или просто на умение выпутаться из сильно ограниченной ситуации — согласен, интересная. И, по-хорошему, интервьюверу стоит давать ее именно такой, «сделать быстро и красиво», а не «минимизировать асимптотическую сложность».
                          0
                          Мои решения
                          Заголовок спойлера
                          1) Просто так утке на берег не выбраться, так как у Пи<4. Но утка может двигаться по кольцу с четвертью радиуса с тойже угловой скоростью, что и лиса. Поэтому Утка переходит на колицо, радиуса чуть меньше четверти (r/4-q), по нему плывет, пока не окажется с другой стороны озера (диаметрально), а потом резко плывет к берегу. У лисы на бег уйдет времени Пи/4, а у утки (3/4+q)/1. Можно взять q очень малым (0,000001) и показать, что первое значение больше второго.
                          2) Задача баян баянный.
                          3) Писать долго, поэтому достаточно просто мыслей. Делаем побитовую обработку в цикле первое слово, начиная со старших разрядов. Если видим, что бит =0, переходим к следующей итерации, если =1, то прибавляем второй слово. После каждой итерации умножаем полученную сумму на 2 раза путем сложение с ней же.
                          Я видел также вариацию этой задачи, где требовалось реализовать умножение без операторов умножения, деления, циклов и побитовых операторов.

                          Умножения нет, деления нет, цикл можно заменить рекурсивным вызовом, а вот отказ от побитовой проверки как сделать — не знаю пока. Сложность — логарифм (двоичный).
                          4) Решение в лоб. Начинаем с 2-ки проходим все числа последовательно, проверяем каждое число на простоту. Если оно просто, то увеличиваем счетчик. Как только он достигает нужного значения возвращает текущее число. Вся фишка в том, как проверять число на простоту. До этого момента сохраняем все найденные ПРОСТЫЕ числа в списке. Последовательно проверяем дает ли деление текущего числа по модулю на одно из чисел списке 0. Если да, то число не простое. Но можно проверять не все делители, а только те, чей квадрат меньше или равен самому числу.
                          5) Очень простая задача. Разбиваем число на разряды (десятичные). Идем с конца, ищем ситуацию, когда предыдущий разряд больше следующего (т.е. когда 34, а не 43). Если разряды упорядоченны монотонно возврастающи, то решения нет. Если мы нашли такой разряд (например в числе 97154 мы нашли что «1»<«5»). То что идет до этих разрядов (97) оставляем на месте, далее находим число, следующее из уже пройденных которое больше предыдущего разряда (здесь из чисел 5 и 7 следующее после 1 идет 5). Ставим это число, а из оставшихся строим число в порядке возрастания разрядов. Т.е. 97-5-17.
                            0
                            Вариант на Java без деления, циклов и побитовых операций
                            Заголовок спойлера
                            public class Multy {
                                private int sub =0;
                                
                                public int doOperation(int a, int b){
                                    sub =0;
                                    return iteration(a, b, 1);
                                }
                                
                                private int iteration(int a, int b, int c){
                                    if(c>a){
                                        return 0;
                                    }
                                    int d = iteration(a, b, c+c);
                                    if(a-sub>=c){
                                        sub+=c;
                                        return d+d+b;
                                    }else{
                                        return d+d;
                                    }
                                }
                            }

                            Слабое место данного алгоритма — это ситуация, когда первое число является наибольшим положительным из int, а второе равно 0 или 1. Но предварительно можно сравнить входные числа, и поменять их местами в случае необходимости. Алгоритм работает только с положительными числами.
                              0
                              А вот пример кода для поиска простых чисел
                              Заголовок спойлера
                              public class SimpleValue {
                                  
                                  public static long nthPrime(int number){
                                      if(number==1){
                                          return 2;
                                      }
                                      ArrayList<Long> array = new ArrayList<>();
                                      array.add(new Long(2));
                                      long n=2;
                                      while(true){
                                          n++;
                                          if(checkSimple(n, array)){
                                              array.add(n);
                                              if(array.size()==number){
                                                  return n;
                                              }
                                          }
                                      }
                                  }
                              
                                  private static boolean checkSimple(long n, ArrayList<Long> array) {
                                      for(long l : array){
                                          if(n%l==0){
                                              return false;
                                          }
                                          if(l*l>n){return true;}
                                      }
                                      return true;
                                  }
                              }

                              +1
                              Задача 2.
                              4 варианта на плюсах
                              1. Если можно использовать битовые операции и деления
                              int foo(int a, int b)
                              {
                                if (a == 1)
                                  return b;
                                if (b == 1)
                                  return a;
                                if ((a%2==0) && (b%2==0))
                                  return foo(a>>1,b>>1)<<2;
                                if (a%2 == 0)
                                  return foo(a>>1,b)<<1;
                                if (b%2 == 0)
                                  return foo(a,b>>1)<<1;
                                return (foo(a>>1,b>>1)<<2) + a + b - 1;
                              }


                              Теперь менее практичные, но более забавные варианты.

                              2. Если нельзя деление и битовые операции
                              int foo(int a, int b)
                              {
                                return PRECALCULATED_A_MULT_B[a][b];
                              }

                              Где PRECALCULATED_A_MULT_B — думерный массив размером чтобы любые индексы a,b были корректны. Содержимое подсчитано заранее.
                              Сама функция работает за O(1).

                              3. Если надо ближе к вычислимым реалиям крутить, но все еще без умножения
                              int foo(int a, int b)
                              {
                                char t[a][b];
                                return sizeof(t);
                              }


                              4. Еще немного с побочными эффектами
                              int foo(int a, int b)
                              {
                                FILE* f = fopen("tmp", "wb");
                                void* t = calloc(a, b);
                                fwrite(t, a, b, f);
                                int r = ftell(f);
                                fclose(f);
                                remove("tmp");
                                free(t);	
                                return r;
                              }

                                0

                                Утка


                                Утка

                                Утка сдвигается в сторону противоположную лисе. Теперь лиса должна начать двигаться, иначе она гарантированно проиграет. Поскольку картинка симметрична, то лисе все равно в какую сторону двигаться. Предположим, что она решила двигаться против часовой стрелки. Как только лиса сдвигается, утка поворачивается, так чтобы быть всегда хвостом к лисе и тем самым двигаться от нее с максимальной скоростью. Лиса продолжает движение по окружности, Утка все время поворачивается от нее. В итоге — Лиса проходит дугу окружности, Утка движется по спирали из центра к окружности.
                                Ключевой вопрос, на который надо ответить — действительно ли длина дуги Лисы более чем в 4 раза превышает длину спирали Утки.
                                Лиса движется с постоянной максимальной скоростью вокруг озера. Длина дуги = 4ut, где u — скорость Утки, t — прошедшее время. Угол в радианах, на который она сместилась = lambda=4ut/pi. Получается треугольник со сторонами r (радиус пруда), ut (смещение утки) и углом pi-lambda. Угол alpha (между вертикальной линией и направлением от Утки к Лисе) = arcsos[(ut+rcos lambda) / sqrt (r^2 + u^2t^2+2utcos lambda)]. Отсюда можно подсчитать радиальную скорость Утки по направлению к краю пруда
                                ur=(ut+r cos (4t/pi)) / sqrt (r^2+u^2t^2 + 2t cos (4t/pi))
                                Понятно, что радиально Утка должна проплыть расстояние r, таким образом интеграл по t от ur = r. Дальше берем свежий математический мозг )))


                                Ящики

                                Берем ящик, где написано "Яблоки+Апельсины". Там на самом деле могут быть либо ЯБлоки, либо Апельсины. В зависимости от того, что достал помощник пишем, что в этом ящике. Например, это было яблоко. После этого у нас остались ящики с Апельсинами и "Яблоки+Апельсины". На ящиках написано "Яблоки" и "Апельсины", но мы знаем, что надпись не соответствует реальности, поэтому там где написано Апельсины, там Яблоки+Апельсины, а где написано Я+А, там Апельсины.


                                Умножение

                                Представляем оба числа в бинарном виде. Записываем в результат 0.


                                1. Смотрим, равно ли первое число 0. Если да, то завершаем работу и возвращаем результат.
                                2. Сдвигаем первое число вправо (слева подставляем 0 бит) и смотрим, какой бит самый левый бит вышел.
                                3. Если 1, то прибавляем к результату второе число.
                                4. Сдвигаем второе число влево на 1 бит (подставляем 0)
                                5. идем к шагу 1.
                                  https://repl.it/repls/WorseCalculatingBison

                                Простое число

                                В лоб перебираем все числа, пока не найдем N-ное простое
                                https://repl.it/repls/KookyUnfoldedMoray


                                Следующее число

                                Предствляем число в виде строки, сортируем цифры по убыванию и составляем их новое число. Если оно больше исходного, то возвращаем его, если нет — то пишем Not Possible.
                                https://repl.it/repls/ViolentDarkgreyGlobefish

                                  0

                                  Задача с уткой и лисой интересная. И решение с движением утки по окружности в 1/4 r до момента максимального удаления от лисы кажется логичным. Отсюда время движения лисы t1 = 3.14/4, а время утки t2 = от 3 до 3.14/4 в зависимости от расстояния от утки до 1/4 r (но не больше чем 1/7 r; большее расстояние чем (3/4 r + 1/7 r) утке не одолеть быстрее лисы).
                                  Но в условиях задачи стоял пункт про разумность утки и лисы...


                                  Кто-нибудь пробовал подсчитать количество длин окружностей, кот. пройдут лиса (и утка тоже) перед тем, как между ними будет 180° учитывая, что их скорость движения по своим окружностям практически не отличается? =)


                                  P.S. Утка может нырять и незаметно плавать под водой.

                                    0
                                    Кто-нибудь пробовал подсчитать количество длин окружностей, кот. пройдут лиса (и утка тоже) перед тем, как между ними будет 180° учитывая, что их скорость движения по своим окружностям практически не отличается? =)

                                    Там не совсем окружность — там лучше двигаться по спирали. А подсчитать несложно — нужно взять добрый интегральчик :)
                                    https://habrahabr.ru/company/spice/blog/346424/#comment_10614030

                                      +1
                                      А смысл в спирали? За пределами четверти радиуса утка двигается с меньшей угловой скорость, чем лиса. Если сравнивать прямой отрезок и спираль, то отрезок выигрывает по длине (он короче), а заканчиваются они оба в одной точке. Лисе в обоих случаях бежать одинаково. Рассуждения о спирали здесь совершенно избыточны. Другое дело, что лиса может поменять направление движения, но в этом случае утке просто придется сменить направление, и опять же двигаться по отрезку.
                                        0

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

                                          0
                                          Ничего тут математически считать не надо. Кратчайший путь между 2-мя точками — это отрезок, спираль будет длиннее. Нарисуйте на бумаге спираль (между окружностями разного радиуса), например в 1/6 оборота, а потом проведите отрезок через те же концы. Что короче? Движение по отрезку — гарантированный выигрыш утки, а вот спираль может сделать лису сытой.
                                          Оптимальный путь для утки на участке до четверти радиуса действительно будет похож на спираль, а дальше только прямая-ломанная.
                                            +1
                                            Прошу прощения, читал по диагонали и не понял с чего всё началось. В частности пропустил смысл этого
                                            Кто-нибудь пробовал подсчитать количество длин окружностей, кот. пройдут лиса (и утка тоже) перед тем, как между ними будет 180° учитывая

                                            Если рассматривать до четверти радиуса, то там всё считается очень просто. Для простоты пусть радиус равен 4, тогда интересующая нас зона имеет радиус 1. Пусть скорость утки равна V, тогда скорость лисы равна 4V. Начальная позиция утки — центр. Утка начинает двигаться в сторону противоположную лисе, и сразу между ней и лисой есть 180*. Лиса начинает двигаться, её угловая скорость равна V(учитывая предположение о единичном радиусе). Утка двигается так, чтобы иметь и радиальную скорость и поперечную. Задача утки двигаться так, чтобы между ней и лисов все время было 180*, т.е. угловая скорость утки та же, что и у лисы. Пусть r- это текущая координата утки. Тогда её поперечная скорость равна Va= r*V. А радиальная равна Vr = (V^2-Va^2)^1/2. Или dr/dt=Vr=V*(1-r^2)^1/2. Из чего получаем уравнение d(tV) =V*dt =dr*(1-r^2)^-1/2. Решением его является r=sin(Vt). Утка достигнет кольца при Pi/2=Vt. Соответственно, положение лиса-центр-утка повернется на четверть круга. Лиса пробежит длину 4V*t=2Pi. А утка пройдет в 4 раза меньше.
                                            Если надо, могу расписать почему утка должна двигаться именно по такой (оптимальной) траектории.
                                              0

                                              Распишите, интересно.

                                                +1
                                                В любой момент времени утка находится на прямой лиса-центр.
                                                1)Если утка попробует двигаться с большей угловой скоростью, то она опередит эту прямую. Но тогда лисе будет выгодно повернуть в противоположную сторону, и теперь утке придется догонять линию. В итоге утка потратила лишнее на угловую скорость, за счет потери радиальной. (могла бы уйти на больший радиус).
                                                2) Если утка будет отставать от прямой, то ей рано или поздно придется ликвидировать отставание (чтобы было 180*). Но на большем радиусе это сделать сложнее. Т.е. лучше ликвидировать сейчас, чем потом.
                                                Поэтому оптимально двигаться, находясь на одной прямой лиса-центр.
                                                Пункт 2) мне кажется очевидным, хотя наверное стоит доказать его более строго.

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

                                                  На мой взгляд, они должны двигаться как-то так:


                                                  Рисунок-спойлер

                                                  Через некоторое время красная пунктирная линия, соединяющая животных, по которой надо убегать утке, не будет проходить через центр. Утке просто перестанет хватать скорости. Как вы пишете, это случится где-то при R/4, но на мой взгляд даже раньше. И тут уравнение движения сильно усложняется.


                                                  Либо вариант, что утка движется до четверти радиуса (пока успевает быть напротив лисы), а затем быстро-быстро лапами к берегу по синей линии. Тогда утке надо преодолеть 3/4R, а лисе — πR. С учетом четверной скорости лисы, получается что время утки — 3R/4V, время лисы — πR/4V. В связи с тем, что 3 < π, утка успевает убежать. Немного, но успевает.


                                                  А вариант с синусоидой занетересовал. Интересно насколько максимально, утка может оторваться от лисы?

                                                    0
                                                    Я изначально предполагал, что утке стоит двигаться (после четверти круга) ровно по диаметру. И в принципе это дает выигрыш для утки. Но что если утка будет двигаться по прямой, но чуть в бок. Открыл Excel, забил с малым шагом углы движения утки, вычислил длину траектории, пересчитал на траекторию лисы, и сравнил конечные угловые расстояния между лисой и уткой. И как не странно, но чем больше угол, тем лучше оказывается для утки. Наверное ей имеет смысл двигаться перпендикулярно линии утка-центр. В отличии от вашего варианта, моя траектория не зависит от положения лисы в каждый момент. Изначально выбираем на окружности точку, и стремимся ровно к ней. Сравнивая оба случая, получаем, что в первом разница 0,14 радиан, во втором 0,58-0,59 радиан. Делать угол больший нет смысла, так как в этом случае утка начнет двигаться внутрь кольца (иметь отрицательную радиальную скорость) и тогда движение будет повторяться бесконечно, из-за изменения направления движения лисы. Как-то так.
                                                      0

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


                                                      Тогда движение утки состоит из 3 частей:


                                                      • по спирали — отплыть от центра на R/4 оставаясь всегда напротив лисы (относительно центра). Утка может сколь угодно долго плавать по окружности с R/4 при этом ничего в положении зверей не изменяется.
                                                      • резко повернуть в сторону берега, чтобы заставить лису побежать в какую-то сторону (предположим, что лиса продолжит сохранила направление движения по кругу, чтобы не разворачиваться и терять время), немного проплыть
                                                      • резкий поворот на 90 градусов в обратную сторону и плыть прямо к берегу. Утка всегда будет отставать от диаметра, на котором находится лиса, значит у той не будет причин для разворота.
                                      0
                                      моё решение
                                      1. Утка улетит. Для того чтобы выжить, она должна оказаться в точке pi/4 r от края круга, противоположного лисе. Тогда она успеет. Сможет ли она достичь этой точки? Конечно да, ведь точка входит в круг 1/4 от центра, где скорость утки относительно берега выше, чем у лисы, а значит она всегда сможет удерживать себя с другой стороны от центра пруда от лисы, и даже будет запас по скорости, чтобы двигаться по разворачивающейся спирали до нужной точки. А оттуда уже по прямой к берегу и всё.

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

                                      3. Задача замечанием о скорости намекает на использование логарифма. Можем использовать принцип логарифмической линейки.

                                      4. Какое-то странное задание. Так как нам нужен номер простого числа, то всё равно придётся искать их все, до текущего номера. Т.е. делать решето Эратосфена и сеять. Никак иначе…

                                      5. Вывернем число на изнанку: расположим все цифры в порядке возрастания, и заменим их на номер их порядка в исходном числе. 7123 -> 2341. Если поменять местами цифры в первом числе, то во втором они заменятся точно так же, это эквивалентные перестановки. Нам нужно переставить элементы второго так, чтобы максимальная подпоследовательность чисел идущих в обратном порядке стала длиннее. При этом начинать перебор вариантов перестановок нужно со старших значений, если следующая за ними цифра не меньше. 3 и 4 переставили — получилось. Хорошо, решение годится, выводим. В противном случае нужно было бы перебирать дальше, вниз по значениям. Для десяти и более значных чисел нужно не число другое записывать, а массив чисел. Повторяющиеся цифры подряд, всё равно в каком порядке.
                                        0
                                        2reci
                                        Вы ответы составляете сами, или берете откуда-нибудь?

                                        В задаче с умножением есть условие "(O(log(n) or better)", оцените алгоритмическую сложность вашего решения.

                                        В задаче с простыми числами просят написать конкретную функцию с конкретным набором параметров, и у вас в решении её нет. Да, конечно, по смыслу довести до нужного уровня можно, тем не менее давать такой ответ в качестве эталона не правильно. Я согласен с тем, что разумно кешировать данные, но вот какой объем памяти под это отводить? А если в качестве параметра передадут число большее, чем указанная вами граница? Не разумно ли делать «ленивые вычисления» (сохранив потокобезопасность кода)?
                                        Так же не понятно, почему вы проверяете в качестве делителя все нечетные числа, ведь у вас уже есть список простых чисел, меньших вашего.
                                          0
                                          Ответ обычно из того же источника, что и задача, и обычно с положительным фидбеком — т.е. решение принято на собеседовании, поэтому выкладываю без изменений.

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