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

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

    КДПВ

    В подборку попали вопросы, встречающиеся на собеседованиях в Adobe (да, вопрос про цвет включён в подборку :). Задачи различного уровня сложности, но все решаемые. Особенно, если Вы уже ответили на вопросы из прошлых выпусков.

    Надеемся, что приведённые задачи помогут Вам качественно подготовиться к предстоящим собеседованиями.

    Вопросы


    1. 8 marbles
      Let’s say you have 8 marbles and a two-pan balance.
      All of the marbles look the same. Each marble weighs 2.0 grams except for one, which is slightly heavier at 2.05 grams.
      How would you find the heaviest marble if you are only allowed to weigh the marbles 2 times using the balance scale?

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

    2. Falling bear
      A bear fell from a height of 10m on the ground in √2 seconds. But somehow, it didn’t get hurt. What is the colour of bear?

      Перевод
      Медведь, падая с высоты 10м, достигает земли за √2 seconds и, почему-то, остаётся без повреждений. Какого цвета медведь?

      Прим: Я некоторое время подумал, и всё-таки заглянул в ответ. Вопрос немного с подвохом, но ответить можно. Решил привести здесь, если такое на собеседованиях встречается.

    Задачи


    1. Product of max and min in 2 arrays
      Given two arrays of integers, the task is to calculate the product of max element of first array and min element of second array.

      Ex:
      Input: arr1[] = {5, 7, 9, 3, 6, 2},
      arr2[] = {1, 2, 6, -1, 0, 9}
      Output: max element in first array
      is 9 and min element in second array
      is -1. The product of these two is -9.

      Input: arr1[] = {1, 4, 2, 3, 10, 2},
      arr2[] = {4, 2, 6, 5, 2, 9}
      Output: 20.

      Перевод
      Даны 2 массива целых чисел. Задача — вычислить произведение максимального элемента из первого массива и минимального из второго массива.

      Примеры:
      Даны: arr1[] = {5, 7, 9, 3, 6, 2}, arr2[] = {1, 2, 6, -1, 0, 9}
      Ответ: максимальный элемент первого массива — 9, минимальный элемент второго -1. Произведение -9.

      Даны: arr1[] = {1, 4, 2, 3, 10, 2},
      arr2[] = {4, 2, 6, 5, 2, 9}
      Ответ: 20.

    2. Maximum Chocolates
      You have $15 with you. You go to a shop and shopkeeper tells you price as $1 per chocolate. He also tells you that you can get a chocolate in return of 3 wrappers. How many maximum chocolates you can eat?

      Write a program to find solution for variable inputs. Given following three values, the task is to find the total number of maximum chocolates you can eat.

      money: Money you have to buy chocolates
      price: Price of a chocolate
      wrap: Number of wrappers to be returned for getting one extra chocolate.

      It may be assumed that all given values are positive integers and greater than 1.

      Перевод
      У Вас есть $15. В магазине у продавца Вы узнаёте цену за шоколадку — $1. Продавец также сообщает, что за 3 обертки выдаст вам ещё шоколадку. На какой максимум шоколадок Вы можете рассчитывать?

      Напишите программу для переменных входных данных, задачей которой будет найти максимум шоколадок:

      money: Имеющиеся деньги
      price: Цена за шоколадку
      wrap: Количество обёрток нужное, чтобы получить ещё одну шоколадку.

      Можно считать, что все входные данные являются целыми и больше 1.

    3. Sort array larger than RAM
      Given 2 machines, each having 64 GB RAM, containing all integers (8 byte). You need to sort the entire 128 GB data. You may assume a small amount of additional RAM.

      Перевод
      Имеются 2 компьютера, у каждого по 64 Гб ОЗУ, занятых целыми числами (8 байт). Вам необходимо отсортировать все 128 Гб данных. Можно использовать небольшое количество дополнительной памяти ОЗУ.


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

    Решения


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

    2. Вопрос 2
      В оригинале, цвет медведя — белый, поскольку он падал с ускорением 10 м/c2, что может быть на полюсах. Правильное решение было найдено, и предложено несколько альтернативных :)

    3. Задача 1

      Решение с сортировкой массивов не является оптимальным. Простой проход по массивам в поисках min/max лучше:
      // C++ program to find the to calculate
      // the product of max element of first 
      // array and min element of second array
      #include <bits/stdc++.h>
      using namespace std;
       
      // Function to calculate the product
      int minMaxProduct(int arr1[], int arr2[], 
                               int n1, int n2)
      {
          // Initialize max of first array
          int max = arr1[0];
       
          // initialize min of second array
          int min = arr2[0];
       
          int i;
          for (i = 1; i < n1 && i < n2; ++i) {
       
              // To find the maximum element 
              // in first array
              if (arr1[i] > max)
                  max = arr1[i];
       
              // To find the minimum element
              // in second array
              if (arr2[i] < min)
                  min = arr2[i];
          }
        
          // Process remaining elements
          while (i < n1)
          {
              if (arr1[i] > max)
                 max = arr1[i];  
              i++;
          }
          while (i < n2)
          {
              if (arr2[i] < min)
                 min = arr2[i];  
              i++;
          }
       
          return max * min;
      }
       
      // Driven code
      int main()
      {
          int arr1[] = { 10, 2, 3, 6, 4, 1 };
          int arr2[] = { 5, 1, 4, 2, 6, 9 };
          int n1 = sizeof(arr1) / sizeof(arr1[0]);
          int n2 = sizeof(arr1) / sizeof(arr1[0]);
          cout << minMaxProduct(arr1, arr2, n1, n2) << endl;
          return 0;
      }


    4. Задача 2
      Решение с рекурсией — не самое оптимальное в данном случае. В оригинальном решении путём наблюдения была выведена формула totalChoc = (choc-1)/(wrap-1) и программа в таком случае приняла вид:
      // Efficient C++ program to find maximum
      // number of chocolates
      #include <iostream>
      using namespace std;
       
      // Returns maximum number of chocolates we can eat
      // with given money, price of chocolate and number
      // of wrapprices required to get a chocolate.
      int countMaxChoco(int money, int price, int wrap)
      {
          // Corner case
          if (money < price)
             return 0;
       
          // First find number of chocolates that
          // can be purchased with the given amount
          int choc = money / price;
       
          // Now just add number of chocolates with the
          // chocolates gained by wrapprices
          choc = choc + (choc - 1) / (wrap - 1);
          return choc;
      }
       
      // Driver code
      int main()
      {
          int money = 15 ; // total money
          int price = 1; // cost of each candy
          int wrap = 3 ; // no of wrappers needs to be
          // exchanged for one chocolate.
       
          cout << countMaxChoco(money, price, wrap);
          return 0;
      }
      


    5. Задача 3
      В качестве решения задачи предлагается External merge sort:

      // C++ program to implement external sorting using 
      // merge sort
      #include <bits/stdc++.h>
      using namespace std;
       
      struct MinHeapNode
      {
          // The element to be stored
          int element;
       
          // index of the array from which the element is taken
          int i;
      };
       
      // Prototype of a utility function to swap two min heap nodes
      void swap(MinHeapNode* x, MinHeapNode* y);
       
      // A class for Min Heap
      class MinHeap
      {
          MinHeapNode* harr; // pointer to array of elements in heap
          int heap_size;     // size of min heap
       
      public:
          // Constructor: creates a min heap of given size
          MinHeap(MinHeapNode a[], int size);
       
          // to heapify a subtree with root at given index
          void MinHeapify(int);
       
          // to get index of left child of node at index i
          int left(int i) { return (2 * i + 1); }
       
          // to get index of right child of node at index i
          int right(int i) { return (2 * i + 2); }
       
          // to get the root
          MinHeapNode getMin() {  return harr[0]; }
       
          // to replace root with new node x and heapify()
          // new root
          void replaceMin(MinHeapNode x)
          {
              harr[0] = x;
              MinHeapify(0);
          }
      };
       
      // Constructor: Builds a heap from a given array a[]
      // of given size
      MinHeap::MinHeap(MinHeapNode a[], int size)
      {
          heap_size = size;
          harr = a; // store address of array
          int i = (heap_size - 1) / 2;
          while (i >= 0)
          {
              MinHeapify(i);
              i--;
          }
      }
       
      // A recursive method to heapify a subtree with root
      // at given index. This method assumes that the
      // subtrees are already heapified
      void MinHeap::MinHeapify(int i)
      {
          int l = left(i);
          int r = right(i);
          int smallest = i;
          if (l < heap_size && harr[l].element < harr[i].element)
              smallest = l;
          if (r < heap_size && harr[r].element < harr[smallest].element)
              smallest = r;
          if (smallest != i)
          {
              swap(&harr[i], &harr[smallest]);
              MinHeapify(smallest);
          }
      }
       
      // A utility function to swap two elements
      void swap(MinHeapNode* x, MinHeapNode* y)
      {
          MinHeapNode temp = *x;
          *x = *y;
          *y = temp;
      }
       
      // Merges two subarrays of arr[].
      // First subarray is arr[l..m]
      // Second subarray is arr[m+1..r]
      void merge(int arr[], int l, int m, int r)
      {
          int i, j, k;
          int n1 = m - l + 1;
          int n2 = r - m;
       
          /* create temp arrays */
          int L[n1], R[n2];
       
          /* Copy data to temp arrays L[] and R[] */
          for(i = 0; i < n1; i++)
              L[i] = arr[l + i];
          for(j = 0; j < n2; j++)
              R[j] = arr[m + 1 + j];
       
          /* Merge the temp arrays back into arr[l..r]*/
          i = 0; // Initial index of first subarray
          j = 0; // Initial index of second subarray
          k = l; // Initial index of merged subarray
          while (i < n1 && j < n2)
          {
              if (L[i] <= R[j])
                  arr[k++] = L[i++];
              else
                  arr[k++] = R[j++];
          }
       
          /* Copy the remaining elements of L[], if there
             are any */
          while (i < n1)
              arr[k++] = L[i++];
       
          /* Copy the remaining elements of R[], if there
             are any */
          while(j < n2)
              arr[k++] = R[j++];
      }
       
      /* l is for left index and r is right index of the
         sub-array of arr to be sorted */
      void mergeSort(int arr[], int l, int r)
      {
          if (l < r)
          {
              // Same as (l+r)/2, but avoids overflow for
              // large l and h
              int m = l + (r - l) / 2;
       
              // Sort first and second halves
              mergeSort(arr, l, m);
              mergeSort(arr, m + 1, r);
       
              merge(arr, l, m, r);
          }
      }
       
      FILE* openFile(char* fileName, char* mode)
      {
          FILE* fp = fopen(fileName, mode);
          if (fp == NULL)
          {
              perror("Error while opening the file.\n");
              exit(EXIT_FAILURE);
          }
          return fp;
      }
       
      // Merges k sorted files.  Names of files are assumed
      // to be 1, 2, 3, ... k
      void mergeFiles(char *output_file, int n, int k)
      {
          FILE* in[k];
          for (int i = 0; i < k; i++)
          {
              char fileName[2];
       
              // convert i to string
              snprintf(fileName, sizeof(fileName), "%d", i);
       
              // Open output files in read mode.
              in[i] = openFile(fileName, "r");
          }
       
          // FINAL OUTPUT FILE
          FILE *out = openFile(output_file, "w");
       
          // Create a min heap with k heap nodes.  Every heap node
          // has first element of scratch output file
          MinHeapNode* harr = new MinHeapNode[k];
          int i;
          for (i = 0; i < k; i++)
          {
              // break if no output file is empty and
              // index i will be no. of input files
              if (fscanf(in[i], "%d ", &harr[i].element) != 1)
                  break;
       
              harr[i].i = i; // Index of scratch output file
          }
          MinHeap hp(harr, i); // Create the heap
       
          int count = 0;
       
          // Now one by one get the minimum element from min
          // heap and replace it with next element.
          // run till all filled input files reach EOF
          while (count != i)
          {
              // Get the minimum element and store it in output file
              MinHeapNode root = hp.getMin();
              fprintf(out, "%d ", root.element);
       
              // Find the next element that will replace current
              // root of heap. The next element belongs to same
              // input file as the current min element.
              if (fscanf(in[root.i], "%d ", &root.element) != 1 )
              {
                  root.element = INT_MAX;
                  count++;
              }
       
              // Replace root with next element of input file
              hp.replaceMin(root);
          }
       
          // close input and output files
          for (int i = 0; i < k; i++)
              fclose(in[i]);
       
          fclose(out);
      }
       
      // Using a merge-sort algorithm, create the initial runs
      // and divide them evenly among the output files
      void createInitialRuns(char *input_file, int run_size,
                             int num_ways)
      {
          // For big input file
          FILE *in = openFile(input_file, "r");
       
          // output scratch files
          FILE* out[num_ways];
          char fileName[2];
          for (int i = 0; i < num_ways; i++)
          {
              // convert i to string
              snprintf(fileName, sizeof(fileName), "%d", i);
       
              // Open output files in write mode.
              out[i] = openFile(fileName, "w");
          }
       
          // allocate a dynamic array large enough
          // to accommodate runs of size run_size
          int* arr = (int*)malloc(run_size * sizeof(int));
       
          bool more_input = true;
          int next_output_file = 0;
       
          int i;
          while (more_input)
          {
              // write run_size elements into arr from input file
              for (i = 0; i < run_size; i++)
              {
                  if (fscanf(in, "%d ", &arr[i]) != 1)
                  {
                      more_input = false;
                      break;
                  }
              }
       
              // sort array using merge sort
              mergeSort(arr, 0, i - 1);
       
              // write the records to the appropriate scratch output file
              // can't assume that the loop runs to run_size
              // since the last run's length may be less than run_size
              for (int j = 0; j < i; j++)
                  fprintf(out[next_output_file], "%d ", arr[j]);
       
              next_output_file++;
          }
       
          // close input and output files
          for (int i = 0; i < num_ways; i++)
              fclose(out[i]);
       
          fclose(in);
      }
       
      // For sorting data stored on disk
      void externalSort(char* input_file,  char *output_file,
                        int num_ways, int run_size)
      {
          // read the input file, create the initial runs,
          // and assign the runs to the scratch output files
          createInitialRuns(input_file, run_size, num_ways);
       
          // Merge the runs using the K-way merging
          mergeFiles(output_file, run_size, num_ways);
      }
       
       
      // Driver program to test above
      int main()
      {
          // No. of Partitions of input file.
          int num_ways = 10;
       
          // The size of each partition
          int run_size = 1000;
       
          char input_file[] = "input.txt";
          char output_file[] = "output.txt";
       
          FILE* in = openFile(input_file, "w");
       
          srand(time(NULL));
       
          // generate input
          for (int i = 0; i < num_ways * run_size; i++)
              fprintf(in, "%d ", rand());
       
          fclose(in);
       
          externalSort(input_file, output_file, num_ways,
                      run_size);
       
          return 0;
      }


    Spice IT Recruitment 97,88
    ИТ специализированное кадровое агентство
    Поделиться публикацией
    Ой, у вас баннер убежал!

    Ну. И что?
    Реклама
    Комментарии 55
    • –1
      ответ на первый вопрос
      1. кладем 8 шариков на весы по 4 на каждую чашу.
      2. выкидываем 4, которые оказались легче.
      3. кладем оставшиеся 4 шарика на весы по 2 на каждую чашу.
      4. убираем по одному шарику с каждой чаши, выкидывая тот, что был взят с более легкой чаши.
      5. в зависимости от от того, как изменится баланс весов, нужный шарик будет тот, который либо остался на более тяжелой чаше, либо окажется в руках.
      • +2
        Это всё-таки три взвешивания :)
        Можно обойтись двумя.
        • +5
          другой ответ на первый вопрос
          1. берем шесть шариков по 3 на каждую чашу
          2. если чаши равны, то искомый шарик в оставшихся двух
          3. если не равны, то выкидываем три самых легких
          4. взвешиваем 2 из оставшихся трех — задача решена :)
          • +1
            Правильно. Это старая задачка. Более внушительно выглядит если нужно найти 1 шарик из 27 за 3 взвешивания.
            • +2
              более внушительно выглядит найти 1 шарик из 13 за 3 взвешивания, если не известно легче он или тяжелее.

              В целом из задач только над 3 можно подумать. Остальные явно на позицию юниора не выше. Ну или во 2 искать точную формулу и пытаться убрать цикл (а возможно ли это?).
              • 0
                Возможно.
                Для примера из условия:

                Доллар даёт одну шоколадку; шоколадка даёт одну обертку; одна обёртка даёт 1/3 шоколадки.

                Тогда, при условии, что у нас бесконечное количество долларов, мы за каждый доллар получим:

                1 + 1/3 + 1/9 + 1/27… шоколадок. Это убывающая геометрическая прогрессия. Если посчитать её сумму, то получим 1.5 шоколадки за каждый потраченный доллар.

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

                x<=3: 1
                3<x<=9: 1 + 1/3
                9<x<=27: 1 + 1/3 + 1/9


                Тогда решение задачи для примера из условия выглядит так:

                x = 25
                3^1 = 3 < x
                3^2 = 9 < x
                3^3 = 27 > x => нужно вычислить три шага

                1 + 1/3 + 1/9 = 13/9

                Теперь просто перемножаем: 15 * 13/9 = 21,6666666 ~ 21 (округляем всегда в меньшую сторону). Решение можно представить в обобщенном виде для любых «money, price, wrap».
                • +1
                  Я не прав. В написанном выше не учитываются возможные остатки на разных итерациях. После исправлений удалось найти решение для частного случая данных условий, но обобщить не получается :(
                  • 0

                    Приведите, пожалуйста, пример, где указанный вами выше подход не работает? Как один пример, когда формула работает: возьмем 14 уе, тогда 14*13/9=20.2(2), в ручную: 14 + 4 (две обертки в остатке) + 2 (2 обертки остатка, 4 обертки от второй партии) = 20.

                    • 0
                      Даже для исходного примера неправильно, как ниже заметил s_suhanov. Вроде удалось обобщить, проверил для 1 <= money <100000, 1 < price < 50, 2 < wrappers < 50— расхождений с итеративным алгоритмом нет. Буду рад, если кто-нибудь опровергнет.

                      Решение
                      Сначала нужно определить, сколько денег мы вообще можем потратить, так как обёртки в доллары не конвертируются.

                      На первой итерации каждый потраченный доллар гарантированно принесёт нам 1/price шоколадок. На второй: 1/price*wrappers и так далее. Снова получается геометрическая прогрессия. Первый шаг не зависит от wrappers, поэтому в прогрессию мы его не включаем. Теперь нужно посчитать s(n), — где n — это степень, при которой wrappers^n >= workMoney (по-хорошему, здесь должно быть просто «больше», но из-за потери точности даже в Decimal и округления вниз в некоторых ситуациях получается число вроде 47.9999999996 вместо 48), a0 = 1/wrappers * price.

                      Финальный шаг: сложим 1/price и s(n) и умножим на workMoney. Округляем в меньшую сторону.

                      Примеры:

                      money = 15, price = 1, wrappers = 3
                      workMoney = 15
                      n = 3, s(3)=1/3 + 1/9 + 1/27 = 14/27 ~ 0.4815
                      1 + 0.4815 = 1.4815

                      result = 15 * 1.4815 ~ 22.22 = 22

                      money=17, price = 3, wrapers = 5
                      WorkMoney = 15
                      n = 2, s(2) = 1/5*3 + 1/25*3 = 1/15 + 1/75 = 7/75
                      1/3 + 7/75 = 32/75 ~ 0.427

                      result = 15 * 0.427 ~ 6,3 = 6

                      Код:

                      private static int ChocolateCount(int money, int price, int wrappersPerOneChoco)
                      {
                      	var workMoney = money - (money % price);
                      
                      	var stepsCount = 0;
                      	int wrappers = 1;
                      
                      	while (wrappers <= workMoney)
                      	{
                      		stepsCount++;
                      		wrappers = wrappers * wrappersPerOneChoco;
                      	}
                      
                      	var chokosPerDollar = 1 / (double)price;
                      	var additionalChokosByCurrentStep = 1 / (double)price;
                      
                      	for (int i = 0; i < stepsCount; i++)
                      	{
                      		additionalChokosByCurrentStep = additionalChokosByCurrentStep / wrappersPerOneChoco;
                      		chokosPerDollar = chokosPerDollar + additionalChokosByCurrentStep;
                      	}
                      
                      	return (int) (workMoney * chokosPerDollar);
                      }
                      • 0
                        Ну получается же, что нужно брать на один шаг глубже, т.е. если более 9 уе (3^2), то глубина 3 шага: 1+1/3+1/9+1/27, если более 27 уе (3^3), то 4 шага итд, в самом принципе я не вижу проблемы.
                  • 0

                    Но ведь ответ не 21, а 22.


                    15 долларов == 15 шоколадок.
                    15 оберток == 5 шоколадок. (нарастающий итог == 20)
                    5 оберток == 1 шоколадка и 2 обертки (нарастающий итог == 21)
                    1 обертка от шоколадки и 2 обертки с пред. шага == 1 шоколадка (итог == 22).

                    • +1
                      Ответил в ветке выше.
                      • 0

                        Да, сорри. Был невнимателен. :(

                      • 0
                        + одна обёртка, эквивалентная 0.5 шоколадки, итого 22.5
                        • +1

                          Одна обертка эквивалентна 1/3 шоколадки. :) Итого 22.333333333… :)

                    • 0
                      Формула проста. Как было сказано, мы меняем 3 обвертки на 1 шоколадку+обвертку. Или по другому, мы получаем новую шоколадку ценой потери 2-х оберток. Но последние 2 обвертки мы поменять на шоколадку не можем, поэтому нужно 1 обвертку вычесть.
                          public static int calcChocoCount(int money, int price, int wrap){
                              int chocoByMoney = money/price;
                              return chocoByMoney + (chocoByMoney-1)/(wrap-1);
                          }
                • 0
                  1. по 3 шарика
                  или весики уравновесятся или будет перевес
                  1.1 если уравновешены — значит тяжелый шарик один из двух оставшихся, просто взвешиваем их, находим нужный
                  1.2 если какие-то три перевесили, снова взвешиваем любые 2 из них
                  1.2.1 если весы уравновешены — тяжелый третий из этой выборки
                  1.2.2 если весы уехали — ниже тяжелый

                  Получили за 2 взвешивания
                • 0
                  технически это три взвешивания)
                • +1
                  возможный ответ на второй вопрос
                  если медведь упал с 10 метров за √2 секунды, то значит ускорение свободного падения в его местности равно 10 м/с^2, что немного расходится со всеми известными значениями для планеты Земля :) Но если брать максимальное значение, то оно находится на полюсе, а значит медведь скорее всего белый, так? :)
                  • 0
                    Еще один вариант на второй вопрос
                    Если медведь падает с ускорением меньше ускорения свободного падения, значит есть какая-то сила, действующая вверх, которая позволяет приземлиться без повреждений. Моя версия — это Винни-Пух спускается на шарике. Цвет возьмем из американской версии мультика — желтый/оранжевый.
                    • 0
                      Думается, всё несколько проще
                      Это бурый медведь, иначе где вы видели в Арктике деревья?
                    • +1
                      Так 10 — это больше, чем ускорение свободного падения. Оно 9.8 (различия полюс/экватор во втором знаке после запятой). Думаю, это просто округление до целых.
                      Возможно, дело в том что
                      под ground имеется ввиду не земля (в смысле почва), а некоторое основание, поверхность. Но раз медведь почему-то не получил повреждений (а падал без всяких шариков, о чем мы можем судить по ускорению, с которым он падал), то упал он на что-то мягкое. Например на толстый слой снега. Поэтому медведь белый.
                    • 0
                      Как-то все сложно…
                      Заголовок спойлера
                      Думаю, он просто упал в снег. Потому он белый. А свободное падение тут не при чем.
                      • +1
                        Бурые медведи живут там, где есть зимы и снег. А вот в местах обитания белых медведей деревьев не особо.
                        • 0
                          Деревьев нет, зато есть торосы и скалы. Впрочем, про снег подмечено верно.
                          Возникла еще мысль, что
                          повреждений нет, потому что медведь очень маленький. Птенцы выпадают из гнезд и порой остаются целыми. Маленькая масса — низкая энергия — нет повреждений. Самые мелкие детенышы у сумчатых (вики говорит, что у коалы — 5г), при этом детеныши розовые.
                          • 0
                            А еще нигде не сказано, что медведь не игрушечный.

                            Но больше всего смущает ускорение свободного падения. При нормальном ускорении он бы 10 метров пролетел за секунду с небольшим. А √2 это 1.414 примерно, так где он по пути задержался? Но опять же не сказано, что он мог по пути что-то задевать.

                            А еще можно сказать, что и бурые, и белые медведи с черной кожей, поэтому они черные!

                            В любом случае вопрос мне кажется довольно странным.
                            • +1
                              Вообще-то наоборот, он не задержался по пути (при нормальном ускорении он упал бы за где-то 1.43), а чуть быстрее прилетел. Но я думаю, что это упрощение для того, чтобы показать, что он как раз таки нигде не задерживался.
                              • 0
                                Мда, все-таки в арифметических задачах я, мягко говоря, не силен.
                    • –1
                      Задача 3
                      int total_chocolate_count(int money_, int price_, int wrap_) {
                          int total_count = money_ \ price_;
                          int prev_count = total_count;
                          do {
                              total_count += prev_count \ wrap_;
                              prev_count = prev_count \ wrap_ + prev_count % wrap_;
                          }
                          while (prev_count \ wrap_ == 0)
                          return total_count;
                      }
                      • 0
                        Обычно оператор деления всё же "/". Но по существу с решением согласен.
                        • 0
                          Конечно же имелась в виду задача №2
                        • 0

                          За 1 доллар можно купить 1 1/3=4/3 шоколадки, за 15 долларов — 15*4/3=20 шоколадок. 2 фольги можно превратить в шоколадку: показать их продавцу и попросить шоколадку, которая будет тут же съедена и все 3 фольги отданы продавцу

                          • +1
                            исправление: за 3 фольги можно получить то же, что за 1 доллар, значит фольга стоит 1/3 доллара, а шоколадка без фольги — 2/3 доллара. За 15 долларов можно съесть 15/(2/3)=22.5 шоколадки без фольги. если есть фольга, то можно съесть 0.5 шоколадки следующим образом: найти компаньона с 1 фольгой, прийти в магазин, показать 2 фольги продавцу и попросить его шоколадку, отдать 2 фольги плюс фольгу из шоколадки продавцу, фольгу без шоколадки разделить с компаньоном
                            • 0
                              Хех, а я через рекурсию делал, а можно было так просто посчитать.
                          • 0
                            А для какого языка первая задачка вообще может представлять трудность?
                            Хотя вроде бы в чистом C, если не ошибаюсь, сих пор нет массивов и задачка предполагает что человек быстро накидает алгоритм сортировки байтиков?
                            • 0

                              Задача решается без массивов :)

                              • 0
                                Эффективнее было бы решить без использования массивов. Например, числа могут быть даны генератором.
                                А уж решение с сортировкой 100% будет завернуто как неэффективное.
                                • 0
                                  Но ведь для определения кто из них меньший, а кто больший, мы уже должны иметь все цифры на руках? А готовый набор данных сам по себе является массивом по определению?
                                  Прошу прощения, если вопрос глупый, я больше ит-менеджер и программированием интересуюсь только контексте автоматизации рутинных задач.
                                  • +1
                                    Но ведь для определения кто из них меньший, а кто больший, мы уже должны иметь все цифры на руках?
                                    Да, должны. Но нам не обязательно их в массив сохранять, можем просто пробежаться циклом, экономия памяти выйдет. Представьте, например, что мы получаем 1 млрд 64-битных чисел по сети и из них нужно найти минимум. Просто сохранить их в массиве займет ~8 гб оперативной памяти, а пробежаться по ним циклом займет три переменных.
                                    Ну а насчет сортировки — она делается за O(NlogN), что гораздо дольше, чем O(N).

                                    Провел эксперимент:
                                    Пусть у нас есть
                                    генератор, выдающий числа
                                    unsigned long long generator() {
                                        static unsigned long long x = 0; // Предыдущее сгенерированное число
                                        return x = x * 239017u + 170239u; // Текущее сгенерированное число
                                    }

                                    И мы хотим найти минимум и максимум среди первых 1 млрд чисел, порожденных этим генератором.
                                    Вариант 1: отсортировать и взять первый и последний элементы
                                    double start = clock(); // Запоминаем момент начала
                                    std::vector<unsigned long long> numbers; // Массив для чисел
                                    numbers.reserve(SIZE); // Выделяем память, без этого будет работать дольше
                                    std::generate_n(std::back_inserter(numbers), SIZE, generator); // Генерируем 1 млрд чисел
                                    std::sort(numbers.begin(), numbers.end()); // Сортируем
                                    std::cout << numbers[0] << ' ' << numbers[SIZE - 1] << std::endl; // Выдаем ответ
                                    std::cout << (clock() - start) / CLOCKS_PER_SEC << std::endl; // Выдаем время
                                    На моем ноутбуке этот код использует 7.6 ГБайт оперативной памяти и работает за 187 секунд.
                                    Вариант 2: найти минимальный и максимальный элементы циклом
                                    double start = clock(); // Запоминаем момент начала
                                    std::vector<unsigned long long> numbers; // Массив для чисел
                                    numbers.reserve(SIZE); // Выделяем память, без этого будет работать дольше
                                    std::generate_n(std::back_inserter(numbers), SIZE, generator); // Генерируем 1 млрд чисел
                                    auto mm = std::minmax_element(numbers.begin(), numbers.end()); // Находим минимум и максимум
                                    std::cout << *mm.first << ' ' << *mm.second << std::endl; // Выдаем ответ
                                    std::cout << (clock() - start) / CLOCKS_PER_SEC << std::endl; // Выдаем время
                                    На моем ноутбуке этот код использует 7.6 ГБайт оперативной памяти и работает за 9 секунд.
                                    Вариант 3: найти минимальный и максимальный элементы циклом, не запоминая их в массив
                                    double start = clock(); // Запоминаем момент начала
                                    unsigned long long min = std::numeric_limits<unsigned long long>::max();
                                    unsigned long long max = std::numeric_limits<unsigned long long>::min();
                                    for (int i = 0; i < SIZE; ++i) { // Цикл по всем числам
                                        unsigned long long x = generator(); // Генерируем очередное число
                                        min = std::min(min, x); // Обновляем минимум
                                        max = std::max(max, x); // Обновляем максимум
                                    }
                                    std::cout << min << ' ' << max << std::endl; // Выдаем ответ
                                    std::cout << (clock() - start) / CLOCKS_PER_SEC << std::endl; // Выдаем время
                                    На моем ноутбуке этот код использует 6 МБайт оперативной памяти и работает за 1.5 секунды.
                                    Вот и получается: можно использовать гораздо (асимптотически) меньше как памяти, так и времени работы. Поэтому вариант решения «запомнить все в массив, отсортировать, взять первый и последний» я называю неоптимальным.
                              • 0
                                А для какого языка первая задачка вообще может представлять трудность?
                                Хотя вроде бы в чистом C, если не ошибаюсь, до сих пор нет массивов и задачка предполагает что человек быстро накидает алгоритм сортировки байтиков?
                                • 0
                                  .
                                  • 0
                                    то ли я лагаю, то ли хабр. Ну пусть буду я. Про C уже посмотрел, что там есть массивы
                                    • 0
                                      1. Вопрос.
                                      Взвешиваем любые 3 и 3. Если они одинаковые, то взвешиваем оставшиеся 2. Находим тяжелый.
                                      Если одна из троек тяжелее, то взвешиваем два шарика из «тяжелой» тройки. Любые. В результате искомый шар будет или одним из двух, или оставшимся, не взвешенным.
                                      • 0
                                        2. Любого или грязного. Например, если медведь игрушечный.
                                        • 0
                                          3. 22 шоколадки. Сначала 15, потом 5, потом 1. Потом остается две обертки от 5 и одна от последней. Итого 22.
                                          • –1
                                            остаётся ещё 1 обёртка, на которую можно съесть ещё 0.5 шоколадки, выше написано как. итого 22.5
                                            • 0

                                              1 обертка == 1/3 шоколадки. :)

                                              • +1
                                                Нет. 1 обертка == 1/3 шоколадки с оберткой == 1/2 шоколадки без обертки.
                                                • 0
                                                  здесь имелось в виду, что 1 обёртка эквивалентная 0.5 шоколадки без обертки
                                                  • 0
                                                    Логично. я предположил, что должны быть только целые числа. Исходя из того, что продавец выдает шоколадки, а не пол-шоколадки.
                                                    Но про половинку, конечно, весело.
                                            • 0
                                              Да уж. В этом выпуске задачи просто поразили.

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

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

                                              Решения мои
                                              Заголовок спойлера
                                              Вопрос 1.
                                              Заголовок спойлера
                                              В общем виде за n взвешиваний можно найти шарик среди не более 3^n штук. Таким образом за 2 взвешивания можно найти нужный шарик из 9. Кол-во 8 дано с целью запутать человека, чтобы он решал вопрос в степенях двойки.

                                              Вопрос 2.
                                              Заголовок спойлера
                                              Я вижу 2 формально удовлетворяющих заданию ответа, которые дают взаимоисключающие результаты. g=10м/c^2 — это округление (также как и пи не равно 3.14). Цель этой части показать, что гравитация в зоне медведя существует, т.е. он в нормальных условиях свернет себе шею.
                                              белый
                                              Медведь не разбивается, если приземлится в снег или воду( есть ещё песок, но это так). Если бы он приземлился в воду, тогда в условиях написали бы «достиг воды», а не земли. Значит он находится где-то заполярном круге. И Обычно это белые медведи.

                                              Медведь желтый, розовый, коричневый, фиолетовый. Какой угодно, но не белый. Потому что ...
                                              это мишка Гамми.
                                              image


                                              Задача 1. Решение слишком очевидно, чтобы его приводить.
                                              Задача 2. Там тоже все просто, переводим бабло в шоколадки. А дальше в цикле переводим шоколадки в обвертки, а их опять в шоколадки по курсу.
                                              Задача 3.
                                              Заголовок спойлера
                                              А вот тут нужно знать, чего от тебя хотят. Получить алгоритм с лучшим классом алгоритмической сложности, алгоритм за меньшее время (при данных условиях важна константа), или подойдет самый примитивный алгоритм. В принципе, если работа единовременная, то написать решение за 5 минут, и оставить работать обе машины на ночь — это будет самым разумным вариантом. В каждом из 3-х случаев я бы дал разное решение.

                                              Предположим, что у нас уже есть 2 компа с уже отсортированными (на каждом из них) данными. В цикле проходим по обоим массивам на первой машине начинаем с начала, а на второй с конца. Рано или поздно число в на первой машине станет меньше числа на второй. Вот мы и нашли ту границу, по которой нужно числа со второго компа отправлять на первый, и наоборот. Могу написать алгоритм, который без дополнительной памяти (ну несколько переменных) путем замены ячеек сделает из двух упорядоченных массивов один за линейное время.
                                              Но если мы можем это сделать(из 2-х упорядоченных сделать один), то автоматом решается и все предыдущие этапы задачи. Т.е. сначала разбиваем весь массив на пары и упорядочиваем. Затем пары объединяем в четверки, их уже в 8-ки и так далее, пока не получим цельный алгоритм. Если алгоритм слияния линейный, тогда сложность всего алгоритма — N*ln2(N).

                                              С другой стороны можно пройтись по всему не отсортированному массиву, посчитать кол-во значений у которых первый бит =1. Зная это значение, можно перенести такие значения вверх, а оставшийся вниз. Хотя наверное, для этого даже считать их кол-во не нужно, нужно только знать границы массива. Далее в каждом из получившихся групп проводим сортировку по второму биту и так далее. Каждая операция сортировки по биту выполняется за O(n). Итого на подготовительную операцию уходит O(N*ln2(M)), где M — это максимальное значение типа, а ln2(M)- количество бит. И пусть M>N, но разница не большая, и будет важна константа алгоритмической сложности.
                                              Надо будет посмотреть, сколько займет на этих данных пузырьковая сортировка, ради интереса.

                                              • +3
                                                >Задача с произведением мин-макс меня вгоняет в ступор
                                                Видимо, расчёт на то, что кандидат будет 2 часа искать подвох в задаче :)
                                              • 0
                                                .

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

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