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

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

    КДПВ


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

    Вопросы


    1. Ice bucket challenge
      There are 3 buckets of capacities 8, 5, 3 litres in front of you. The bucket with capacity 8 is completely filled with ice water. You need to divide the 8 litres into 2 portions of 4 litre each using above 3 buckets.
      Перевод
      Перед Вами 3 ведра ёмкостью 8, 5 и 3 л. Ведро на 8 л. полностью заполнено холодной водой. Вам нужно разделить 8 литров на 2 порции по 4 л. используя эти три ведра.

    2. Torch and bridge
      There are 4 persons (A, B, C and D) who want to cross a bridge in night.

      A takes 1 minute to cross the bridge.
      B takes 2 minutes to cross the bridge.
      C takes 5 minutes to cross the bridge.
      D takes 8 minutes to cross the bridge.

      There is only one torch with them and the bridge cannot be crossed without the torch. There cannot be more than two persons on the bridge at any time, and when two people cross the bridge together, they must move at the slower person’s pace

      Can they all cross the bridge in 15 minutes?
      Перевод
      4 человека (A, B, C, D) хотять ночью перебраться через мост.

      A нужна 1 минута чтобы пройти по мосту.
      B нужно 2 минуты.
      C нужно 5 минут.
      D нужно 8 минут.

      У них только один фонарь, без которого нельзя перейти мост. Также, на мосту не может находиться больше 2-х человек, и, когда по мосту идут двое — они идут со скоростью самого медленного ходока.

      Смогут ли они перебраться за 15 минут?

    Задачи


    1. Sort an array of 0s, 1s and 2x
      Given an array A[] consisting 0s, 1s and 2s, write a function that sorts A[]. The functions should put all 0s first, then all 1s and all 2s in last.
      Examples:

      Input: {0, 1, 2, 0, 1, 2}
      Output: {0, 0, 1, 1, 2, 2}

      Input: {0, 1, 1, 0, 1, 2, 1, 2, 0, 0, 0, 1}
      Output: {0, 0, 0, 0, 0, 1, 1, 1, 1, 1, 2, 2}

      Перевод
      Дан массив A[], состоящий из 0, 1 и 2. Напишите функцию, сортирующую A[]. Функция должна располагать сначала 0, потом 1, последними — 2.

      Примеры:

      Вход: {0, 1, 2, 0, 1, 2}
      Выход: {0, 0, 1, 1, 2, 2}

      Вход: {0, 1, 1, 0, 1, 2, 1, 2, 0, 0, 0, 1}
      Выход: {0, 0, 0, 0, 0, 1, 1, 1, 1, 1, 2, 2}

    2. Select a random number from stream, using fixed space
      Given a generator producing random numbers. You are allowed to use only O(1) space and the input is in the form of stream, so can’t store the previously seen numbers.

      So how do we select a random number from the whole stream such that the probability of picking any number is 1/n. with O(1) extra space?
      Перевод
      Дан генератор случайных чисел. Позволено использовать только О(1) памяти, входные данные представлены в виде потока, так что нет возможности сохранять предыдущие числа.

      Задача — выбрать случаное число из входящего потока, обеспечив вероятность 1/n, используя только O(1) дополнительной памяти.

    3. Maximize the sum of selected numbers
      Given an array of N numbers, we need to maximize the sum of selected numbers. At each step you need to select a number Ai, delete one occurrence of Ai-1 (if exists), Ai+1 (if exists) and Ai each from the array. Repeat these steps until the array gets empty. The problem is to maximize the sum of selected numbers.

      Note: We have to delete Ai+1 and Ai-1 elements if they are present in the array and not Ai+1 and Ai-1.

      Examples:

      Input: a[] = {1, 2, 3}
      Output: 4
      Explanation: At first step we select 1, so 1 and 2 are deleted from the sequence leaving us with 3.
      Then we select 3 from the sequence and delete it. So the sum of selected numbers is 1+3 = 4.

      Input: a[] = {1, 2, 2, 2, 3, 4}
      Output: 10
      Explanation: Select one of the 2's from the array, so 2, 2-1, 2+1 will be deleted and we are left with {2, 2, 4}, since 1 and 3 are deleted. Select 2 in next two steps, and then select 4 in the last step. We get a sum of 2+2+2+4=10 which is the maximum possible.
      Перевод
      Дан массив из N чисел, нам необходимо выбрать элементы с максимальной суммой. При каждой выборке элемента (Аi), необходимо удалить одно вхождение элемента на единицу меньше и одно вхождение элемента на единицу больше (Ai-1) и (Ai+1) при их наличии и сам элемент. Эти шаги повторяются, пока массив не опустеет. Задача — обеспечить максимальную сумму выбранных элементов.
      Нужно удалять элементы со значением Ai+1 и Ai-1, а не на позиции Аi-1 и Аi+1

      Примеры:

      Вход: a[] = {1, 2, 3}
      Выход: 4
      Объяснение: На первом шаге выбираем 1, следовательно, 1 и 2 удаляются из массива. На следующем шаге забираем оставшуюся 3. Сумма выбранных элементов 1+3 = 4.

      Вход: a[] = {1, 2, 2, 2, 3, 4}
      Выход: 10
      Объяснение: Выбираем одну 2 из массива — удаляются 1 и 3 (2-1 и 2+1, соответственно), остаются {2, 2, 4}. В ходе следующих 2-х шагов выбираем оставшиеся 2 и последним шагом выбираем 4. Итоговая сумма 2+2+2+4 = 10, что является максимально возможной.

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

    Решения


    1. Вопрос 1
      Корректное решение предложено в комментарии:
      8 -> 5 (3, 5, 0)
      5 -> 3 (3, 2, 3)
      3 -> 8 (6, 2, 0)
      5 -> 3 (6, 0, 2)
      8 -> 5 (1, 5, 2)
      5 -> 3 (1, 4, 3)
      3 -> 8 (4, 4, 0)

    2. Вопрос 2
      Верное решение было найдено в комментариях.

    3. Задача 1
      Предложили верный вариант решения — сортировка подсчётом. Код может быть, например, таким.

    4. Задача 2
      Алгоритм решения был верно разъяснен в комментарии. Код может быть таким:
      // An efficient C program to randomly select a number from stream of numbers.
      #include <stdio.h>
      #include <stdlib.h>
      #include <time.h>

      // A function to randomly select a item from stream[0], stream[1], .. stream[i-1]
      int selectRandom(int x)
      {
      static int res; // The resultant random number
      static int count = 0; //Count of numbers visited so far in stream

      count++; // increment count of numbers seen so far

      // If this is the first element from stream, return it
      if (count == 1)
      res = x;
      else
      {
      // Generate a random number from 0 to count - 1
      int i = rand() % count;

      // Replace the prev random number with new number with 1/count probability
      if (i == count - 1)
      res = x;
      }
      return res;
      }

      // Driver program to test above function.
      int main()
      {
      int stream[] = {1, 2, 3, 4};
      int n = sizeof(stream)/sizeof(stream[0]);

      // Use a different seed value for every run.
      srand(time(NULL));
      for (int i = 0; i < n; ++i)
      printf("Random number from first %d numbers is %d \n",
      i+1, selectRandom(stream[i]));
      return 0;
      }


    5. Задача 3
      Правильное решение было предложено, например, тут. Код:
      // CPP program to Maximize the sum of selected
      // numbers by deleting three consecutive numbers.
      #include <bits/stdc++.h>
      using namespace std;

      // function to maximize the sum of selected numbers
      int maximizeSum(int a[], int n) {

      // stores the occurrences of the numbers
      unordered_map<int, int> ans;

      // marks the occurrence of every number in the sequence
      for (int i = 0; i < n; i++)
      ans[a[i]]++;

      // maximum in the sequence
      int maximum = *max_element(a, a + n);

      // traverse till maximum and apply the recurrence relation
      for (int i = 2; i <= maximum; i++)
      ans[i] = max(ans[i - 1], ans[i - 2] + ans[i] * i);

      // return the ans stored in the index of maximum
      return ans[maximum];
      }

      // Driver code
      int main()
      {
      int a[] = {1, 2, 3};
      int n = sizeof(a) / sizeof(a[0]);
      cout << maximizeSum(a, n);
      return 0;
      }


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

    More
    Ads

    Comments 44

      +2
      В задаче №2 требуется случайно выбрать число из потока, размер которого неизвестен.
      Судя по формулировке задачи, наш алгоритм не детерминирован, а может пользоваться генератором случайных чисел.
      Тогда, можно предложить такое решение
      Занумеруем числа из потока от 1.
      У нас есть ячейка, в которой будем хранить кандидата на финальный результат.
      При получении очередного n-го числа из потока с вероятностью 1/n заменим число в ячейке на число из потока.

      То есть, первое число генератора всегда кладём в ячейку (вероятность замены = 1), второе — с вероятностью 1/2, следующее — с 1/3, и т.д…

      Когда поток закончен, результат — число из ячейки.

      Формально доказать корректность как-то лень, но на небольших примерах (размер потока 1,2, или 3) вроде получается равномерное распределение.
        +2
        Теоретическое обоснование
        Пусть метод работает для первых n чисел, то есть для каждого из этих чисел вероятность выпадения 1/n.
        Добавим следующее (n+1) число по предложенной схеме. Вероятность его выпадения будет 1/(n+1). Вероятность того, что останется предыдущее число — n/(n+1), что по формуле условной вероятности даёт для каждого из предыдущих чисел вероятность (1/n)*(n/(n+1)) = 1/(n+1).
        Таким образом индукция работает. Поскольку для первого числа предложенный метод даёт правильную вероятность (1), то и для каждого следующего он будет работать.
          0
          Не верно. Если перезаписывать число, то вероятность того, что в ячейке осталось первое число будет 1/(n!) короче, нулевое
          Ответ
          Вероятность выбора каждого элемента = 1 / (n — i)
          Не знаю зачем вообще дополнительная память.

          Пример:
          10 элементов
          Вероятность выбрать первый элемент 1\10 — нормальное распределение
          Получаешь следующий элемент и его выбираешь уже с вероятностью 1\9, так как элементов осталось 9


          То есть, в каждом выборе гарантируется нормальное разспределение
            0
            Откуда у вас взялся факториал?
            Первый шаг: вероятность для первого числа 1.
            Второй шаг: вероятность записи нового числа 1/2, оставить старое (1-1/2) = 1/2
            Третий шаг: (1-1/3) = 2/3
            Четвёртый шаг: (1-1/4) = 3/4

            (n-1)-й шаг: (1-1/(n-1)) = (n-2)/(n-1)
            n-й шаг: (1-1/n) = (n-1)/n
            Комбинируя условные вероятности получаем
            1 * 1/2 * 2/3 * 3/4… * (n-2)/(n-1) * (n-1)/n = 1/n
          +1
          Третья задача.

          Я буду пользоваться «жадным» алгоритмом, забирая числа от больших к меньшим (чтобы не беспокоиться о Ai+1 на момент рассмотрения Ai).

          Пусть у нас есть последовательность: 1 (x5), 2 (x6), 3 (x2), 4.
          Стоит ли мне брать четвёрку? Если я её возьму, получу 4, но потеряю две тройки.
          Если я не возьму четвёрку, я должен брать 2 тройки (иначе какой смысл отказываться от четвёрки), но беря 2 тройки, я теряю 6 двоек, и т.д. Полный перебор затягивает меня к экспоненциальную яму.

          Значит, нужно применить обычное динамическое программирование.

          Обозначим S(N) — наибольшая сумма, которую можно взять из последовательности, рассматривая числа не более чем N. Обозначим K(N) — количество чисел «N» в последовательности.

          Тогда, если я решил взять число N, то число N-1 мне не доступно, но это не затрагивает все числа меньше N-1: S1(N)=N*K(N) + S(N-2).
          А если я решил отказаться от N, то к моей сумме ничего не прибавляется S2(N) = S(N-1).

          Поскольку вариантов всего 2, то S(N) = max(S1(N), S2(N)).
          Вычислим рекуррентно S(i) от 1 до макс. числа в последовательности, и запомним булевский признак T(N)=true, если S1 > S2 на шаге N (это обозначает, брать число N в ответ или нет).

          Печатаем ответ в обратном порядке: перебираем i от максимального N до 1, если T(i) = true, печатаем число i, если T(i) = false, не печатаем.
            0
            Понятно, что настоящее решение сложнее. Т.к. если в последовательности есть очень большие числа, то не нужно циклами бегать по не заполненным промежуткам между ними, а длинные последовательности нулей в S(N) не нужно хранить, заменив массив S(N) на словарь. Но это уже детали реализации.
              0
              Если бы задачу давали на соревнованиях типа TopCoder, чтобы завалить невнимательных, наверняка были бы тесты и с отрицательными числами (в условии же не сказано, что все числа положительны), которые не надо выбирать, чтобы не ухудшать себе результат :)
              +1
              Вопрос 1
              8 -> 5 (3, 5, 0)
              5 -> 3 (3, 2, 3)
              3 -> 8 (6, 2, 0)
              5 -> 3 (6, 0, 2)
              8 -> 5 (1, 5, 2)
              5 -> 3 (1, 4, 3)
              3 -> 8 (4, 4, 0)

              Вопрос 2
              Здесь неполное условие. Могут ли люди пересекать мост одновременно во встречном направлении? Если да, то можно уложиться в 15 минут:
              A+D переходят в одну сторону (8 минут)
              A+C переходят навстречу друг-другу (5 минут)
              A+B переходят в одну сторону (2 минуты)

              Задача 1
              Считаем количество нулей, единиц и двоек, затем выводим нужное количество (сортировка подсчётом).

              Задача 3
              Начинаем выбирать с максимального значения, таким образом на каждом шаге будет удаляться только max(Ai) и max(Ai)-1, если такое существует.

              В задаче 3 неверный перевод и форматирование. Удаляются не «все вхождения элементов на единицу меньше и на единицу больше (Ai-1) и (Ai+1) при их наличии и сам элемент», а по одному вхождению Ai-1 (если такое есть), Ai+1 (если такое есть) и сам элемент Ai.
              Удаляются именно значения Ai-1 и Ai+1, а не Ai-1 и Ai+1.
                0
                Здесь неполное условие. Могут ли люди пересекать мост одновременно во встречном направлении?

                Нет, во встречном направлении не могут, фонарь всего один.
                  +2
                  Тогда так
                  A + B — 2 минуты
                  A обратно — 1 минута
                  C + D — 8 минут
                  B обратно — 2 минуты
                  A + B — 2 минуты
                    0
                    Неплохо.
                      0
                      И как же так получается, что ушли

                      C + D — 8 минут

                      а потом

                      B обратно — 2 минуты

                      ?
                      Откуда там взялся B, когда туда ушли с фонарём C + D?

                      Здесь никак не вложится, так как обратное время тоже учитывается, и даже, если всех будет переводить А (ведь обратно фонарь-то всё равно нужно нести и ему быстрее всего идти обратно), то получается так:

                      A+D=8
                      A=1 (обратно)
                      A+C=5
                      A=1 (обратно)
                      A+B=2

                      Итого 8+1+5+1+2=17.
                        0
                        0. Начало, звёздочкой обозначен фонарь
                        (A, B, C, D, *) == ()
                        1. Переходят A и B
                        (C, D) == (A, B, *)
                        2. A возвращается обратно
                        (A, C, D, *) == (B)
                        3. Переходят C и D
                        (A) == (B, C, D, *)
                        4. B возвращается обратно
                        (A, B, *) == (C, D)
                        5. Переходят A и B
                        () == (A, B, C, D, *)
                          0
                          Понял, спасибо. Действительно успеют за 15
                    0

                    С фонарем решается без встречного движения.

                      0
                      По задаче 3 — спасибо, замечания приняты.
                      0
                      Первая
                      8->5 (3, 5, 0)
                      5->3 (3, 2, 3)
                      3->8 (6, 2, 0)
                      5->3 (6, 0, 2)
                      8->5 (1, 5, 2)
                      5->3 (1, 4, 3)
                      3->8 (4, 4, 0)
                        0
                        первая: да, соортировка подсчётом, только считать можно n-1 элементов, то есть 0 и 1 тогда количество 2 знаем потому что знали изначальный размер массива.

                        вторая: генерируем число 1<=x<= n, если x == 1 то выбираем число из потока, вероятность этого 1/n
                          0
                          вторая: генерируем число 1<=x<= n, если x == 1 то выбираем число из потока, вероятность этого 1/n

                          А если n заранее не известно?
                            0
                            тогда нельзя. сравни ситуации когда генератор выдаёт n и 2n. Ты получаешь первое число которое надо выбрать с вероятностью 1/n или 1/2n ты не знаешь с какой.
                              0
                              а не, я вру, оказывается можно.
                              вариант от qw1 работает для любых n.
                              нагляднее будет вариант от qw1 с деревом вероятностей
                              значение в ячейке сохраняем с вероятностью (n-1)/n то есть меняем с 1/n
                              пусть будет поток a,b,c,d
                              1) кладём a(100%)
                              2) с вероятностью 50% меняем на b: a (50%), b (50%)
                              3) с вероятностью 33% меняем значение на с: a (50%*66%), b (50%*66%), с(2 * 50% * 33%) -> a(33%) b
                              4) с вероятностью 25% меняем значение на d. а будет с веростностью 1/2*2/3*3/4 = 1/4 и т.д
                              при этом не надо считать дроби.
                              Изменить с вероятностью n значит что выпадает 1 при равномерном распределении [1..n]
                              но тогда надо считать n, и у нас, о ужас, будет две переменные заместо одной требуемой для O(1). В одну «ячейку памяти» два значения можно впихнуть написав одно число в 1/2 верхних битах, другое в нижних.
                                +1
                                O(1) — это не одна ячейка памяти, это любое фиксированное количество памяти, не зависящее от n.
                          +3
                          Второй вопрос
                          AB->(2 min)
                          <-A(1 min)
                          CD->(8 min)
                          <-B(2 min)
                          AB->(2 min)
                          1 + 2 + 8 + 2 + 2 = 15
                            0
                            Ну что же, попробуем (устроится в Google/Microsoft/Etc):

                            1) Задача Ледяного Бака
                            Переливаем 5л из 8л бака в 5л бак
                            Переливаем 3л из 5л бака в 3л бак
                            Переливаем 3л из 3л бака в 8л бак
                            Переливаем 2л из 5л бака в 3л бак
                            Переливаем 5л из 8л бака в 5л бак
                            Переливаем 1л из 5л бака в 3л бак
                            Переливаем 3л воды из 3л бака в 8л бак
                            Собственно задача решена, 4 л в 8л баке и 4л в 5л баке.
                            А почему вода ледяная, какое отношение к задаче имеет температура жидкости? Риторика.

                            2) Задача Светильника и Моста
                            Ответ, да все указанные персоны могут пересечть мост менее чем за 15 минут.
                            Персоны «A» и «B» пересекают мост совместно за 2 минуты.
                            Затем, персоны «C» и «D» пересекают мост за 8 минут.
                            Итого 10 минут на пересечение моста при указанных идеальных условиях.

                            3) Сортировка массива состоящего из значений 0,1,2.
                            Возможно, неверно интерпретирована задача или есть более оптимальные методы ее решения, но в общем случае имеет быть следующее решение — выборочная сортировка на языке pascal
                            for i:= 0 to n-1 do
                            ..for j:= i+1 to n-1 do
                            ....if a[i]>a[j] then swap(a[i],a[j]);
                            


                            4) Выбрать произвольное/случайное значение из потока используя ограниченное место хранения
                            Пропуск. Не смог определить искомый результат — «вероятность 1/n».

                            5) Максимизировать сумму выбранных чисел
                            Дано объяснение с примерами, но не указан искомый результат?! Либо пропущены данные.

                            Теперь можно и подсмотреть что у других…
                              0
                              Затем, персоны «C» и «D» пересекают мост за 8 минут.
                              Итого 10 минут на пересечение моста при указанных идеальных условиях.

                              C и D падают с моста, поскольку светильник остался на другой стороне.
                                0
                                Верно, упустил из виду, что светильник должен возвращаться.
                                  0
                                  Тогда ответ мой ответ — Нет.
                                  +8 минут для «A» и «D»
                                  +1 минута возвращение «A»
                                  +5 минут для «A» и «C»
                                  +1 минута возвращение «A»
                                  +2 минуты для «A» и «B»
                                  Итого 17 минут.
                                  +1
                                  Ice Bucket Challenge — это отсылка к соответствующему флешмобу.

                                  Задача с мостом и фонарём вполне решаема, и ответ в ней — «Да».

                                  Сортировку пузырьком здесь не стоит использовать, лучше сортировку подсчётом, так как набор возможных значений заранее известен и ограничен.
                                    0
                                    Ice Bucket Challenge — это отсылка к соответствующему флешмобу.

                                    Пожалуй. Хорошо, что в форме задачи.
                                  0
                                  Таких легких задач еще не было.
                                  Вопрос 1. Такие вопросы мы решали в 5 классе.
                                  Вопрос 2. Такой вопрос был мне задан в ЕПАМе. Самые тормознутые должны идти вместе.
                                  Задача 1. Если не применять «избыточную» оптимизацию, то легко решается в 2 прохода, считаем кол-во 0,1,2 и за второй проход расставляем по местам. Но можно решать за 1 проход, но сильно это ничего не ускорит, а вот код окажется намного сложней.
                                  Задача 2. Такая задача была в одной из книг Шилдта. Я её сам не решил. Но ответ знаю.
                                  Задача 3. Если я все правильно понял, то при выборе 3-ки во втором примере мы потеряем всего одну двойку и 1 четверку, а не все двойки. Т.е. удаляются не все элементы равные значению, а только один из них. Если так, что решение — каждый раз выбирать наибольший из оставшихся элементов.
                                    +1
                                    Т.е. удаляются не все элементы равные значению, а только один из них
                                    Удаляются все элементы с соседним значением. В условие задачи внесено изменение:
                                    Нужно удалять элементы со значением (Ai)+1 и (Ai)-1, а не на позиции А(i-1) и А(i+1)
                                    К сожалению, автор поправил русскую часть (которую никто не читает), но не поправил английскую.

                                    Но это можно было сразу понять, разбирая второй пример, в котором есть 3 двойки, и все три ушли в результат.
                                      0
                                      В английской части как раз и было:
                                      delete one occurrence of Ai-1 (if exists), Ai+1 (if exists) and Ai each from the array.

                                      Хотя вариант с удалением всех вхождений сложнее и интереснее.
                                        0
                                        Уже поправлено. На sohabr можно посмотреть снепшоты версий этой статьи ))
                                          0
                                          Да, «one occurrence». У меня неверное решение выше ((
                                        0
                                        Но можно решать за 1 проход, но сильно это ничего не ускорит, а вот код окажется намного сложней.
                                        Как это, в один проход? Одним циклом, пока читаем вход, сразу выводим результат?
                                          0
                                          Прошу прощения, что долго не отвечал. Не было времени.
                                          Там конечно получается не чистый 1 проход, скорее полтора прохода.
                                          Чистый 1 проход получился бы если в задаче были только 0 и 1.
                                          public static void sort01(int[] _array){
                                                  int leftIndex =0;
                                                  int rightIndex = _array.length-1;
                                                  while(true){
                                                      while(_array[leftIndex]==0){
                                                          leftIndex++;
                                                      }
                                                      while(_array[rightIndex]==1){
                                                          rightIndex--;
                                                      }
                                                      if(leftIndex>=rightIndex){
                                                          return;
                                                      }
                                                      _array[leftIndex]=0;
                                                      _array[rightIndex]=1;
                                                      leftIndex++;
                                                      rightIndex--;
                                                  }
                                              }

                                          Правда у такого варианта есть косяк: если массив нулевой длинный, или же если там одни 0 или 1, то выход за пределы массивы. Но это можно пофиксить либо добавив по 1 проверке в цикле, либо добавить (и запомнить) единицу и ноль в массив, а после уже вернуть в начальное значение.
                                          А так 1 проход: каждое значение (индекс) читается не больше 1 раза, и записывается не более 1 раза, за исключение чтения элементов «при встрече» индексов.
                                          Задача с 0,1,2 немного сложнее, но думаю вам самим будет интересно решить её по аналогии.
                                            0
                                            Задача с 0,1,2 немного сложнее, но думаю вам самим будет интересно решить её по аналогии.
                                            Не вижу аналогии. Здесь есть 2 фиксированные точки — начало массива и конец, откуда растут непрерывные блоки 0 и 1. От какой точки будет расти третий блок, мы не знаем, пока не проведём подсчёт.
                                              +1
                                              Мы имеем 3 указателя. index1 -движение слева направо, index2 -движение справа налево (самый правый элемент, который !=2), index0- самый левый элемент, который не равен 0.
                                              Пример. 0001102122 (жирным выделены указатели)
                                              Смотрим на что указывает указатель index1, в примере это 0.
                                              Если это ноль, то меняем значение index0 и index1 местами, и сдвигаем оба индекса на 1. Резальтат: 0000112122
                                              Если же index1 указывает на 1, то просто сдвигаем его влево на 1, если указывает на 2, то меняем местами значения в ячейках index1 и index2, и уменьшаем index2 на 1.
                                              Вот рабочий код, немного запутанный, после каждого обновления индекса приходится делать проверку, чтобы не выйти за приделы массива.
                                              public static void sort012(int[] _array){
                                                      int index0 = 0;
                                                      int index1 = 0;
                                                      int index2 = _array.length-1;
                                                      int val1 = _array[index1];
                                                      int val2 = _array[index2];
                                                      
                                                      while((val1==0)&&(index1<index2)){
                                                          index1++;
                                                          val1 = _array[index1];
                                                      }
                                                      while((val2==2)&&(index1<index2)){
                                                          index2--;
                                                          val2 = _array[index2];
                                                      }
                                                      index0 = index1;
                                                      if(index1>=index2){
                                                          return;
                                                      }
                                                      // 
                                                      while(true){
                                                          if(val1==0){
                                                              if(index1!=index0){
                                                                  _array[index0] = 0;
                                                                  _array[index1] = 1;
                                                              }
                                                              index0++;
                                                              index1++;
                                                              if(index1>index2){
                                                                  return;
                                                              }
                                                              val1 = _array[index1];
                                                              continue;
                                                          }
                                                          if(val1==2){
                                                              _array[index2] = val1;// =2
                                                              _array[index1] = val2;
                                                              val1 = val2;
                                                              index2--;
                                                              if(index1>index2){
                                                                  return;
                                                              }
                                                              val2 = _array[index2];
                                                              while(val2==2){
                                                                  index2--;
                                                                  if(index1>index2){
                                                                      return;
                                                                  }
                                                                  val2 = _array[index2];
                                                              }
                                                              continue;
                                                          }
                                                          while(val1==1){
                                                              index1++;
                                                              if(index1>index2){
                                                                  return;
                                                              }
                                                              val1 = _array[index1];
                                                          }
                                                      }
                                                  }
                                                  
                                                  public static void main(String[] _a){
                                                      //int[] ar = {0,1,2,0,1,2,0,0,2,2,1,2,0,1,1,0,2,2};
                                                      int[] ar = {2,1,0,0,1,0,0,0,0,0,1,0,0,0,1,0,0,0};
                                                      sort012(ar);
                                                      for(int i:ar){
                                                          System.out.println(i);
                                                      }
                                                  }

                                              Здесь каждый элемент массива читается 1 раз. Правда каждый элемент массива может быть изменён 2 раза. Поэтому это скорее полтора прохода.
                                                0
                                                Интересное решение. Если массив уже отсортирован, то алгоритм вообще не делает запись.
                                          0
                                          А в первой задаче не про принцип «если мы знаем элементы массива, то сортировка нам не нужна»? То есть за один проход мы с помощью трех переменных можем создать сортированный массив, а не сортировать существующий?
                                            0
                                            Мы можем сортировать его по ходу, двигаясь слева и справа, и проводить сортировку тех элементов, которые были пройдены.
                                            Поэтому сортировать именно существующий массив.
                                          0
                                          Объясните плиз, про генератор случайных. То ли лыжи не едут, то ли я не понимаю в чём сложность.
                                          буфер?
                                          Есть реальный поток данных. Если он бесконечен, то вероятность выбрать любое из чисел должна быть нулевой. Если он конечен, то у него есть длина n. Если она меньше нашего объёма буфера, то возвращаем из генератора число от 1 до n с равной вероятностью. Если больше — то возвращаем случайный момент времени из диапазона когда велась трансляция, и ровно в этот момент хватаем последнее попавшее в буфер число. Если скорость передачи не фиксирована, то просто знаем сколько раз наполнится буфер, и считаем два числа random%N и N%databuffer. Так как каждое из них независимое, то и вероятность равна для всех.
                                            0
                                            Всё просто, есть генератор случайных чисел. Длина последовательности (n) заранее неизвестна. Необходимо получить одно случайно выбранное с вероятностью (1/n) число из этой последовательности. При этом можно использовать только фиксированное количество памяти, довыделять память в дальнейшем нельзя. Поскольку генератор случайный, то повторить последовательность тоже нельзя.
                                              0
                                              Спасибо, понял. Но случай вопиющий (система с ограничениями на память — скорее всего контроллер, и на них я бы ожидал задокументированную длину пакетов со всех сторон...).

                                              Более реальный случай под ту же математическую логику — нужно делать наложенное изображение из нескольких слайдов-слоёв. Слайды загружаются поочерёдно, и неисвестно, сколько их будет всего. Как обеспечить равномерное наложение слоёв?

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