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

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



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

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

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

Вопросы

1. Утка в пруду
   

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

   
   
   Перевод

   Утка, преследуемая лисой, спасается в центре круглого пруда радиусом r. Утка может взлететь с земли, но не с воды. Лиса же не умеет плавать. Также, лиса в 4 раза быстрее утки. Предположив, что утка и лиса абсолютно разумны, возможно ли для утки достичь берега и улететь?
   
2. Ящики с фруктами (и ярлыками)
   

   In front of you are three boxes. One contains only apples, one contains only oranges and one contains a mix of apples and oranges. Each box is incorrectly labeled, like this:
   Box 1: “apples”
   Box 2: “oranges”
   Box 3: “apples & oranges”
   
   Question: You get to choose one, and only one, box. I will remove a randomly selected piece of fruit from your chosen box and show it to you (so you can tell if it’s an apple or an orange). After that, you will be able to accurately and definitively relabel all three boxes
   

   
   
   Перевод

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

Задачи

1. Умножить без оператора умножения
   

   Write a function that takes the produce of two given integers without using the multiplication operation. Try to do this as fast as you can (O(log(n) or better)
   

   
   
   Перевод

   Написать функцию, которая возвращает произведение 2-х целых числе без использования оператора умножения. Постарайтесь реализовать с максимальной производительностью (O(log(n) или лучше).
   Я видел также вариацию этой задачи, где требовалось реализовать умножение без операторов умножения, деления, циклов и побитовых операторов.
   
2. N-е простое число
   

   Write a function that returns the nth prime number. For example, nthPrime(1) should return 2 since 2 is the first prime number, nthPrime(2) should return 3, and so on.

   
   
   Перевод

   Напишите функцию, возвращающую n-ое простое число. Например:
   nthPrime(1) => 2 (поскольку 2 является первым простым числом),
   nthPrime(2) => 3
   и т.д.
   
3. Найти следующее число с теми же цифрами
   

   Given a number N, find the next number that has same set of digits as n and is greater than N. If N is the greatest possible number with its set of digits, then print “not possible”.
   Ex:
   N = «218765» => «251678»
   N = «1234» => «1243»
   N = «4321» => «Not Possible»
   N = «534976» => «536479»
   

   
   
   Перевод

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

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

Решения

1. Вопрос 1

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

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

   Один из вариантов решения — рекурсия:
   
   

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

   
   
   
   
4. Задача 2

   Вариант ответа:
   

   
   #include <stdio.h>
   #include <stdlib.h>
   #include <math.h>
   #define MAX 100000000
   
   void prime(int n, int *primes)
   {
       int i,j,count=0;
   
       primes[count++] = 2;
       if (count == n)
           return;
       for(i=3;i<=MAX;i+=2)
       {
           int isPrime=1;
           int jMax = sqrt(i);
           for(j=3;j<=jMax;j+=2)
           {
               if(i%j==0)
               {
                   isPrime=0;
                   break;
               }
           }
           if(isPrime)
           {
               primes[count++] = i;
               if(count==n)
                   return;
           }
       }
   }
   
   int main()
   {
      int n,i;
   
      scanf("%d",&n);
      int arr[n];
      int maxPrime = 0;
   
      for(i=0;i<n;i++)
      {
          scanf("%d",&arr[i]);
          if (arr[i] > maxPrime)
              maxPrime = arr[i];
      }
      int primes[maxPrime];
      prime(maxPrime, primes);
      for (i=0;i<n;i++)
      {
          printf("%d\n", primes[arr[i]-1]);
      }
      return 0;
   

   
   
   
   
5. Задача 3

   Оригинальное решение:
   

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