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

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

    КДПВ

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

    Вопросы


    1. 2 kind of pills
      A man has a medical condition that requires him to take two kinds of pills, call them A and B. The man must take exactly one A pill and exactly one B pill each day. The pills are taken by first dissolving them in water.

      The man has a jar of A pills and a jar of B pills. One day, as he is about to take his pills, he takes out one A pill from the A jar and puts it in a glass of water. Then he accidentally takes out two B pills from the B jar and puts them in the water. Now, he is in the situation of having a glass of water with three dissolved pills, one A pill and two B pills. Unfortunately, the pills are very expensive, so the thought of throwing out the water with the 3 pills and starting over is out of the question. How should the man proceed in order to get the right quantity of A and B while not wasting any pills?

      Перевод
      Одному больному, согласно медицинским показаниям, необходимо принимать два лекарства, A и Б, причем нужно ежедневно принимать ровно 1 таблетку A и 1 таблетку Б. Таблетки принимаются в растворенном виде.

      У больного есть склянка с А и склянка с Б. Однажды он, растворив таблетку А в стакане, бросил туда 2 таблетки из склянки с Б и получил стакан с раствором из 1 А и 2 Б. К сожалению, лекарства дорогие, поэтому он отбросил мысль вылить этот раствор и приготовить новый. Как этому больному продолжить приём назначенных лекарств, не потеряв при этом ни таблетки?

    2. Avg Salary
      Three Employees want to know average of their salaries. They are not allowed to share their individual salaries. How can they calcalate average salary?

      Перевод
      Три сотрудника хотят узнать среднюю зараплату (среди них троих), при том, что им запрещено озвучивать индивидуальную зарплату. Как им посчитать среднюю з/п?


    Задачи


    1. Find possible compositions of a natural number

      Given a natural number n, write a program to find the number of ways in which n can be expressed as a sum of natural numbers when order is taken into consideration. Two sequences that differ in the order of their terms define different compositions of their sum.

      Examples:

      Input: 4
      Output: 8
      Explanation
      All 8 position composition are:
      4, 1+3, 3+1, 2+2, 1+1+2, 1+2+1, 2+1+1 and 1+1+1+1

      Input: 8
      Output: 128

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

      Примеры:

      Вход: 4
      Выход: 8
      Объяснение: 4, 1+3, 3+1, 2+2, 1+1+2, 1+2+1, 2+1+1 и 1+1+1+1

    2. Count numbers that don’t contain 3
      Given a number n, write a function that returns count of numbers from 1 to n that don’t contain digit 3 in their decimal representation.

      Examples:

      Input: n = 10
      Output: 9

      Input: n = 45
      Output: 31
      // Numbers 3, 13, 23, 30, 31, 32, 33, 34,
      // 35, 36, 37, 38, 39, 43 contain digit 3.

      Input: n = 578
      Ouput: 385


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

      Примеры:

      Вход: n = 10
      Выход: 9

      Вход: n = 45
      Выход: 31
      // Числа 3, 13, 23, 30, 31, 32, 33, 34,
      // 35, 36, 37, 38, 39, 43 содержат 3.

      Вход: n = 578
      Выход: 385

    3. Boolean Array Puzzle
      Write a program according with following specifications:

      Input: A array arr[] of two elements having value 0 and 1
      Output: Make both elements 0.

      Requirements: Following are the specifications to follow.

      1) It is guaranteed that one element is 0 but we do not know its position.
      2) We can’t say about another element it can be 0 or 1.
      3) We can only complement array elements, no other operation like and, or, multi, division, …. etc.
      4) We can’t use if, else and loop constructs.
      5) Obviously, we can’t directly assign 0 to array elements.

      Перевод
      Напишите программу, удовлетворяющую следующим требованиям:

      Вход: массив arr[] из 2-х элементов, имеющих возможные значения 1 или 0
      Выход: Сделать оба элемента равными 0

      Требования:
      1) Известно, что один элемент равен 0, но неизвестна его позиция
      2) Про второй элемент мы этого не можем сказать, он может быть 0 или 1.
      3) Мы можем только дополнять элементы массива, никакие другие операции, такие как or, and, умножение, деление и др. не разрешены.
      4) Нельзя использовать условные конструкции, циклы.
      5) Нельзя явно записать 0 в элементы массива.


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

    Решения


    1. Вопрос 1
      Верный ответ был дан в комментариях:
      Нужно добавить ещё одну таблетку А в стакан, перемешать и выпить полстакана, оставив половину на следующий день.


    2. Вопрос 2
      Было предложено много вариантов решения, один, например, в этом комментарии.

    3. Задача 1
      Верное решение также было найдено в комментариях.
      Путем небольшого анализа можно выяснить и доказать, что количество комбинаций равно 2n-1.

      #include<iostream>
      using namespace std;
      
      #define ull unsigned long long
      
      ull countCompositions(ull n)
      {
      	// Return 2 raised to power (n-1)
      	return (1L) << (n-1);
      }
      
      // Driver Code
      int main()
      {
      	ull n = 4;
      	cout << countCompositions(n) << "\n";
      	return 0;
      }
      


    4. Задача 2
      Рекурсивный вариант решения:
      #include <stdio.h>
       
      /* returns count of numbers which are in range from 1 to n and don't contain 3 
         as a digit */
      int count(int n)
      {
          // Base cases (Assuming n is not negative)
          if (n < 3)
              return n;
          if (n >= 3 && n < 10)
             return n-1;
       
          // Calculate 10^(d-1) (10 raise to the power d-1) where d is
          // number of digits in n. po will be 100 for n = 578
          int po = 1;
          while (n/po > 9)
              po = po*10;
       
          // find the most significant digit (msd is 5 for 578)
          int msd = n/po;
       
          if (msd != 3)
            // For 578, total will be 4*count(10^2 - 1) + 4 + count(78)
            return count(msd)*count(po - 1) + count(msd) + count(n%po);
          else
            // For 35, total will be equal to count(29)
            return count(msd*po - 1);
      }
       
      // Driver program to test above function
      int main()
      {
          printf ("%d ", count(578));
          return 0;
      }
      


    5. Задача 3
      Правильный ответ предложен в комментарии

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

    Ну. И что?
    Реклама
    Комментарии 26
    • +1
      Avg Salary
      Пусть участники A, B, C имеют зарплаты a, b, c.
      Каждый участник загадывает случайное число от 1 до 1.000.000.000.
      Участник A передаёт своё загаданное число ar участнику C (в тайне от B).
      Участник B передаёт своё загаданное число br участнику A (в тайне от C).
      Участник C передаёт своё загаданное число cr участнику B (в тайне от A).
      Затем A передаёт x1=(a+ar) участнику B.
      B прибавляет b, br и вычитает cr, передаёт x2=x1+b+br-cr=a+ar+b+br-cr участнику C.
      C передаёт x3=x2+c+cr-ar=a+ar+b+br-cr+c+cr-ar участнику A.
      A вычисляет x4=x3-br=a+ar+b+br-cr+c+cr-ar-br=a+b+c и объявляет x4 всем.
      Средняя зарплата — это x4/3 = (a+b+c)/3
      • +1
        Можно гораздо проще. Они скрыто друг от друга берут игровые фишки от любой игры в эквиваленте своей зарплаты и так, чтобы никто другой не видел (например зажав жменю фишек в руке) кладут их в непрозрачный мешок, встряхивают его для надежности, пересчитывают содержимое мешка и делят на 3.
        • +1
          Хм, интересно. Я подумал про вариант, когда каждый пишет на свою з\п на листочке и кладет в шапку. Потом достаем и считаем среднее. Вроде условия задачи выполняются.
          Интересно, прокатило бы на собеседовании?
          • +1
            Пусть все N работников скинутся каждый по 1/N своей зарплаты в непрозрачную банку. Останется посчитать.
            • 0
              Например, с помощью программы
              Можно написать программу сервер, которая принимает значения от участников (может быть N количеством), в данном случае они максимум смогут узнать о среднем! Да и зная средняя и положения сотрудников в компании можно приблизительно вычислить среднее, а таким методом можно скрыть и среднее =)
              • +3
                Первый говорит второму случайное число, второй говорит третьему это число + своя з.п, третий говорит первому то, что услышал от второго + своя з.п. Первый добавляет к услышанному свою з.п, вычитает своё случайное число и делит результат на 3
                • 0
                  Если это в открытом помещении — то первый может вычислить зарплату второго и третьего.
                • +2

                  Можно немного упростить.


                  • Первый сотрудник должен выбрать случайное число и запомнить его. К нему прибавить свою зарплату, записать на бумажку и передать следующему сотруднику.
                  • Следующий, в свою очередь, должен прибавить свою зарплату к числу на бумажке и заменить его результатом.
                  • Повторяем процесс пока не закончатся сотрудники и передаём бумажку с результатом первому
                  • первый вычитает заполненное им случайное число из результата и делит получившееся на количество сотрудников.
                    То бишь:
                    ((Seed + x1 + x2 +… + xn) — Seed ) / n
                  • 0
                    Только для безопасности нельзя «передавать» одну бумажку, нужно каждый раз заменять её новой.
                    Если все промежуточные суммы окажутся на одной бумажке, следующему легко будет понять, сколько прибавил предыдущий сотрудник.
                    • 0

                      Как я и написал, число на бумажке каждый раз заменяется. И да! Бумажка должна иметь возможность полного удаления надписи и её следов :)

                • +1
                  Boolean Array Puzzle
                  Я так полагаю, что дополнение — это инверсия: !x, или (1-x) для чисел {0,1}
                  В таком случае, решение:
                  Скрытый текст
                  arr[!arr[0]] = arr[!arr[1]]
                  • 0
                    А вы действительно решили или знали решение? Если решили — не могли бы вы описать ход мысли?
                    • 0
                      Я догадался, что при запрете использования условий и циклов, условную логику можно осуществить, используя значение массива (тем более, там 0 или 1), как индекс.
                      Я ожидал, что решение будет элементарным, типа a[!a[1]] = a[0], но точно не знал, каким.
                      Затем я накатал маленькую программку:
                      #include <stdio.h>
                      
                      int main()
                      {
                              for (int i = 0; i < 3; i++) {
                                      int a[2] = { i >> 1, i & 1 };
                                      a[a[0]] = !a[1];
                                      printf("%d %d -> %d %d\n", i >> 1, i & 1, a[0], a[1]);
                              }
                              return 0;
                      }
                      И подставлял туда разные формулы, пока не получил два столбца нулей. Это заняло 10-20 итераций, и как оказалось, формула получилась сложнее, чем я ожидал )))

                      Возможно, есть более простая формула, эту я нашёл слепым подбором.
                      • +1
                        Условия нужно дополнить указанием допустимых азыков и компиляторов.

                        В Roslyn C#, например, прямой конвертации булевых значений в числа нет: вместо этого в функции `Convert.ToInt32(bool value)` используется условная операция, что нарушает условия задачи.

                        А вывести формулу можно разложив массивы на бумаге. У нас всего три варианта: [1,0] [0,1] [0,0]. Сразу ясно, что нужно использовать структуру a[x], где x = a[y], поскольку заполняя x заранее выбранным значением мы условную логику не сможем симулировать, только перестановку. Дальше разложим наши варианты a[a[y]]: всего четыре штуки на каждый массив. Из них два примечательных: a[a[0]] всегда указывает на значение 0, a[!a[0]] всегда указывает на значение 1, если оно присутствует. Стало быть a[!a[0]] = a[a[0]] заменит 1 на 0 в тех случаях, когда 1 есть, а когда его нет — заменит 0 на 0.
                        • 0
                          На C# эта задача тоже решается.
                          Раскрыть
                          arr[arr[1]] = arr[arr[0]];

                          • 0
                            Вот именно это решение будет работать только при условии что исходные элементы числового типа. В языке нет неявного преобразования типа bool в int, поэтому всё в конце концов упрётся в декларацию arr.

                            `int[] arr = {0, 1};` вполне сработает, а `bool[] arr = {false, true};` уже нет. Так что постановка задачи как «Boolean array puzzle» в конкретно этом случае подходит не вполне. Пример.
                            • +1
                              Заголовок задачи можно считать лирическим отсуплением, но в условии написано конкретно
                              A array arr[] of two elements having value 0 and 1
                              • +1
                                Признаюсь занудой.
                    • 0
                      Да, «инверсия», пожалуй лучше подходит по смыслу
                    • +1
                      2 kind of pills
                      Просто добавить ещё одну таблетку А в стакан, перемешать и выпить полстакана..?
                      Если важна концентрация, то можно ещё добавить воды, но вроде про концентрацию ничего не сказано.
                      • +1
                        Почти тоже
                        Я подумал, что можно просто стакан разделить на 2 по половинке, далее разбавить А таблетку в новом и влить по половине в два полученный из исходного, тогда и концентрация, по идеи, также останется.
                      • 0
                        тут интересна только задача на комбинации, ибо вторая задача — на сокращённое x mod 10, а в третьей не корректное условие и с такими ограничениями не хочется решать.
                        вот корявый псевдокод:
                        обозначим combo(x,n) количество комбинаций для числа x с n цифрами.
                        например combo(4,2) = count ((1,3), (2,2), (3,1)) = 3
                        очевидно что combo(x,2) = x-1
                        тогда combo (x,n ) = summ(i = 1..(x-n+1)), combo(x-i,n-1)
                        например
                        combo (5,3 ) = (1,1,3 ), (1,2,2) (1,3,1), (2,1,2), (2,2,1), (3,1,1) = combo(4,2) + combo(3,2), + combo(2,2))) = 3 + 2 + 1
                        или
                        combo(6,4) = combo(5,3)+combo(4,3)+combo(3,3) = 6 + 3+1
                        все комбинации для числа x:
                        combo(x) = combo(x,1)+ combo(x,2) +… + combo(x,x)
                        • 0
                          import java.util.Arrays;
                          
                          public class SummCombos {
                          
                          	public static int count(int x) {
                          		calls = 0;
                          		int[][] lookup = new int[x+1][x+1];
                          
                          		for (int i = 0; i < lookup.length; i++) {
                          			Arrays.fill(lookup[i], -1);
                          		}
                          
                          		int summ = 0;
                          		for (int n = 1; n <= x; n++) {
                          			summ += count(x, n, lookup);
                          		}
                          
                          		return summ;
                          	}
                          
                          	public static int calls = 0;
                          
                          	public static int count(int x, int n, int[][] lookup) {
                          		calls++;
                          		int summ;
                          		if ((summ = lookup[x][n]) > 0) {
                          			return summ;
                          		}
                          		if (n == x || n == 1)
                          			summ = 1;
                          
                          		if (n == 2)
                          			summ = x - 1;
                          		if (summ < 0) {
                          			summ = 0;
                          			int limit = x - n + 1;
                          			int nm1 = n - 1;
                          			for (int i = 1; i <= limit; i++) {
                          				summ += count(x - i, nm1, lookup);
                          			}
                          		}
                          		lookup[x][n] = summ;
                          		return summ;
                          
                          	}
                          	
                          	public static void main(String[] args) {
                          				
                          		int maxX = 30;
                          		
                          		for (int i = 1; i < maxX; i++) {
                          			System.out.println("i: " + i + " count : " + count(i) + " calls " + calls);
                          		}
                          		
                          		
                          		
                          	}
                          }


                          и тогда видим что:
                          i: 1 count : 1 calls 1
                          i: 2 count : 2 calls 2
                          i: 3 count : 4 calls 3
                          i: 4 count : 8 calls 6
                          i: 5 count : 16 calls 12
                          i: 6 count : 32 calls 22
                          i: 7 count : 64 calls 37
                          i: 8 count : 128 calls 58
                          i: 9 count : 256 calls 86
                          i: 10 count : 512 calls 122
                          i: 11 count : 1024 calls 167
                          i: 12 count : 2048 calls 222
                          i: 13 count : 4096 calls 288
                          i: 14 count : 8192 calls 366
                          i: 15 count : 16384 calls 457
                          i: 16 count : 32768 calls 562
                          i: 17 count : 65536 calls 682
                          i: 18 count : 131072 calls 818
                          i: 19 count : 262144 calls 971
                          i: 20 count : 524288 calls 1142
                          i: 21 count : 1048576 calls 1332
                          i: 22 count : 2097152 calls 1542
                          i: 23 count : 4194304 calls 1773
                          i: 24 count : 8388608 calls 2026
                          i: 25 count : 16777216 calls 2302
                          i: 26 count : 33554432 calls 2602
                          i: 27 count : 67108864 calls 2927
                          i: 28 count : 134217728 calls 3278
                          i: 29 count : 268435456 calls 3656

                          и код можэно сократить до 2^(x-1) или 1 << (x-1)
                          • 0
                            На самом деле, задача на основы мат анализа.

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

                            По сути имеем n,n-1+1, n-2+1+1… 1+n-1, n-2+2, n-3+2+1...2+n-2...1/2n+1/2n. Остаётся только решить сигму.
                        • +1
                          Выпуск не понравился, половину заданий я не понял.
                          1 Вопрос
                          В чем суть вопроса? В том, чтобы добавить ещё одну таблетку для равновесия, и потом разделить коктель на 2 дозы вертикальной перегородкой (лекарства могут быть слоями с разными плотностями)

                          Вопрос 2
                          Не понятно зачем, и не понятно что можно делать. Для себя я понял вопрос так: нужно узнать среднюю, но чтобы никто не узнал ЗП другого работника. Первый человек говорит второму случайное число(и запоминает его). Второй прибавляет свою ЗП к числу и говорит сумму третьему. Третий также прибавляет свою ЗП и говорит первому. Первый с данному значению прибавляет свою ЗП и отнимает запомненное число. Делит на 3 и говорит всем среднюю ЗП.

                          Задача 1
                          2^(n-1). Почему так? Возмем число 7, разобьем его на семь единиц. 7 = 1 1 1 1 1 1 1. Между 7-ю единицами есть 6 промежутков. В каждом из промежутков может либо быть "+", либо не быть. Единицы, между которыми нет плюса объединяем в одно число. 7=11+1+1+111=2+1+1+3. Каждая комбинация плюсов дает 1 последовательность, и каждая последовательность дает ровно 1 комбинацию. Поэтому число их вариантов одинаково.

                          Задача 2
                          Логично такую задачу решать рекурсией. Но рекурсия обрабатывает разряды со старшего, при этом, если в старших разрядах есть 3, то от младших ничего не зависит. т.е. 35 и 38 дадут одинаковое кол-во. Поэтому, если найдена 3, то делаем число отрицательным и передаем его вверх. Не сложно заметить, что 10 — это 9 комбинаций, 100-это 9*9=81 комбинаций, 1000-это 9*9*9 комбинаций.
                          Код не причесан, но решение должно быть понятно.
                          public static boolean isRight(int _i){
                                  int h = _i;
                                  while(h>0){
                                      int hh = h/10;
                                      if(h-hh*10==3){
                                          return false;
                                      }
                                      h = hh;
                                  }
                                  return true;
                              }
                              
                              public static void main(String[] _a){
                                  for(int i=1; i<100000; i++){
                                      int z1 = bruteforce(i);
                                      int z2 = Math.abs(shum(i, 1));
                                      if(z1!=z2){
                                          System.out.println(" "+i+"   "+z1+"   "+z2);
                                      }
                                  }
                              }
                              
                              public static int bruteforce(int _h){
                                  int s = 0;
                                  for(int i=1; i<=_h; i++){
                                      if(isRight(i)){
                                          s++;
                                      }
                                  }
                                  return s;
                              }
                              
                              public static int shum(int _h, int _power){
                                  if(_h==0){return 0;}
                                  int g = _h/10;
                                  int c = _h-g*10;
                                  int d = shum(g, 9*_power);
                                  if(d<0){return d;}
                                  if(c<3){return d+c*_power;}
                                  if(c>3){return d+(c-1)*_power;}
                                  return (shum(g, 9*_power)+c*_power-1)*-1;
                              }
                          
                          

                          В коде идет проверка моего способа с полным перебором.

                          Задачу 3 не понял.
                          • +1
                            Таблетки
                            Растворить ещё одну А и выпить полстакана, тщательно перемешав. Вторую половину на завтра.

                            Зарплата
                            Сначала я подумал что каждому надо добавить случайное число, затем сложиться, и вычесть все три числа. Но тогда получается что сумму можно вычислить постфактум. Значит, им надо ещё и обменяться теми случайными числами по кругу. Пусть a, b, c — зарплаты; A, B, C — их личные случайные числа. aa<< — информация, которую получил aa.
                            bb<< (a+A)
                            cc<< (a+A+b+B)
                            aa<< (a+A+b+B+c+C)
                            bb<< (a+b+B+c+C)
                            cc<< (a+b+c+C)
                            Теперь сс вычитает своё число и делит на три.

                            1
                            Можно написать слегка оптимизированный перебор — перебрать упорядоченные наборы, умножая каждый новый на количество перестановок.

                            2
                            def not3(x):
                                if x < 3:
                                    return x
                                b = 1
                                a = -1
                                while b < x:
                                    b *= 10
                                    a += 1
                                b //= 10
                                res = x//b
                                if res > 3: res -= 1
                                res2 = 0
                                for i in range(a):
                                    res2 *= 9
                                    res2 += 10**i
                                res = res * b - res * res2 + not3(x % b)
                                return res
                            


                            Более непонятного чем 3 задание ещё ничего не было) Что значит дополнение? В оригинале более интересный термин, дополнить до укомплектовки. Что есть укомплектованное число?

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

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