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

Мы подготовили для Вас новый выпуск, ставшей уже традиционной, ITренировки — подборки задач с собеседований в IT-компании мира.

В отобранные задачи попали задачи с собеседований Samsung. Соискателю также могут задать вопрос про шифр и Шерлока Холмса (нет, не пляшушие человечки, как можно было подумать). Уровень сложности мы постарались варьировать — от простых до серьезных.

Вопросы

1. Faulty machine
   

   We have 10 machines that produce screws, each weighing 1 gram. One of the machines, however, produces screws weighing 0.9 grams only. We are allowed only one weighing and need to determine which machine is faulty.

   
   
   Перевод

   У нас есть 10 машин, производящих винты, каждый весом в 1 грамм. Правда, одна из машин производит винты весом 0,9 грамм. Нам разрешено произвествие только одно взвешивание (прим. винтов), чтобы найти машину, производящую бракованные винты.
   
2. Holmes and cipher
   

   Sherlock Holmes was decoding an encrypted message. If in the encryption, DISTANCE is written as IDTUBECN and DOCUMENT is written as ODDVNTNE.
   
   Can you help him decipher HTTQYAD?
   

   
   
   Перевод

   Шерлок Холмс разгадывает зашифрованное сообщение. В шифре, DISTANCE обозначено как IDTUBECN, а DOCUMENT — как ODDVNTNE.
   
   Сможете ли Вы помочь ему расшифровать HTTQYAD?

Задачи

1. Research center and rare elements
   

   A Research team want to establish a research center in a region where they found some rare-elements.They want to make it closest to all the rare-elements as close as possible so that they can reduce overall cost of research over there.It is given that all the rare-element’s location is connected by roads.It is also given that Research Center can only be build on road.Team decided to assign this task to a coder.If you feel you have that much potential..Here is the Task :- Find the optimal position of research center from given locations of rare-elements.
   
   Locations are given in the matrix cell form where 1 represents roads and 0 no road. Number of rare-element and their location was also given(number<=5) and order of square matrix was less than equal to (20).
   

   
   
   Перевод

   Исследовательская команда хочет основать центр исследований в регионе, где найдены некоторые редкие элементы. Они хотят расположить его максимально близко ко всем источникам элементов, чтобы снизить общие затраты. Источники элементов соединены дорогами. Также, исследовательский центр может быть построен только возле дороги. Команда решает поручить задачу разработчику, и, если Вы чувствуете свой потециал — найдите оптимальное расположение центра, исходя из локаций элементов.
   
   Локации даны в виде матрицы, где 1 в ячейке означает наличие дороги, а 0 — её отсутствие.
   Также даны локации элментов (числом <= 5). Порядок квадратной матрицы <= 20.
2. Stack down or up
   

   In a typical process, a stack segment of program contains local variables along with information that is saved each time a function is called. Each time a function is called, the address of where to return to and certain information about the caller’s environment, such as some of the machine registers, are saved on the stack. The newly called function then allocates room on the stack for its automatic and temporary variables.
   
   Stack may grow downward or upward depending on environment for which code is compiled, i.e., depends on compiler. Write down the program to determine whether stack grows downward or upward?

   
   
   Перевод

   Обычно, сегмент стека программы содержит локальные переменные с информацией, сохраняемой при каждом вызове функции. Когда вызывается функция, в стек сохраняется адрес возврата и информация об окружении — например, некоторые регистры. Затем вызываемая функция занимает место в стеке для своих автоматических и временных переменных.
   
   Стек может расти вниз или вверх в зависимости от среды, для которой скомпилирован код, т. е. зависит от компилятора. Реализуйте программу для определения, растет ли стек вниз или вверх.
3. Next greater element
   

   Given an array, print the Next Greater Element (NGE) for every element. The Next greater Element for an element x is the first greater element on the right side of x in array. Elements for which no greater element exist, consider next greater element as -1.
   
   Examples:
   a) For any array, rightmost element always has next greater element as -1.
   b) For an array which is sorted in decreasing order, all elements have next greater element as -1.
   c) For the input array [4, 5, 2, 25], the next greater elements for each element are as follows.
   

   Element       NGE
      4      -->   5
      5      -->   25
      2      -->   25
      25     -->   -1
   

   
   d) For the input array [13, 7, 6, 12], the next greater elements for each element are as follows.
   

     Element        NGE
      13      -->    -1
      7       -->     12
      6       -->     12
      12     -->     -1
   

   
   

   
   
   Перевод

   Дан массив, напечатайте следующий больший элемент (NGE) для каждого из элементов. Следующим большим элементом для x является первый больший элемент с правой стороны от x в массиве. Если такого элемента не существует — NGE считается -1.
   Примеры:
   a) Для любого массива, крайний правый элемент всегда имеет NGE = -1.
   b) Для любого массива, отсортированного по убыванию, все элементы имеют NGE = -1.
   c) Для элементов массива [4, 5, 2, 25] NGE будет следующим:
   

   Элемент       NGE
      4      -->   5
      5      -->   25
      2      -->   25
      25     -->   -1
   

   
   d) Для элементов массива [13, 7, 6, 12] NGE будет следующим:
   

    Элемент         NGE
      13      -->    -1
      7       -->     12
      6       -->     12
      12     -->     -1
   

   
   

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

Решения

1. Вопрос 1

   jmdorian дал правильный ответ — взвесить для каждой машины число болтов равное ее номеру. Внимания заслуживает и вариант со сбаланированным диском.
   
   
   
2. Вопрос 2

   Ответ: THURDAY.
   Принцип решения.
   
   
   
3. Задача 1

   Вариант решения с потенциалом для оптимизации:
   

   using namespace std ;
   
   bool ar[21][21]; bool visited[21][21]; int ans[21][21]; int xa[]={0,-1,0,1}; int yb[]={1,0,-1,0}; int n;
   
   typedef struct Point{ int x,y;
   }P;
   
   typedef struct C { int x,y; int dis; } C;
   
   bool issafe(int x,int y) { return (x>=0 && x<n &&="" y="">=0 && y<n && ar[x][y] && !visited[x][y]); }
   
   void bfs(int x,int y) { queue<c> q; C in; in.x=x; in.y=y; in.dis=0; q.push(in); visited[x][y]=1;
   
   while(!q.empty())
   {
       C c=q.front();
       q.pop();
       int a=c.x;
       int b=c.y;
       int d=c.dis;
       ans[a][b]=d;
   
       for(int i=0;i<4;i++)
       {
   
           int nx=a+xa[i];
           int ny=b+yb[i];
           if(issafe(nx,ny))
           {
               visited[nx][ny]=1;
               in.x=nx;
               in.y=ny;
               in.dis=d+1;
               q.push(in);
           }
    }
   
   }
   
   }
   
   int main() {
   
   cin>>n;
   for(int i=0;i<n;i++)
   {
       for(int j=0;j<n;j++)
       {
           cin>>ar[i][j];
       }
   }
   
   int q;
   cin>>q;
   
   P rare[q];
   
   int fans=10000;
   int mx=-1;
   
   
   for(int i=0;i<q;i++)
   {
   
       int a,b;
       cin>>a>>b;
   
       rare[i].x=a;
       rare[i].y=b;
   }
   
   
   for(int i=0;i<n;i++)
   {
       for(int j=0;j<n;j++)
       {
           memset(ans,10000,sizeof(ans));
           int flag=0;
           memset(visited,0,sizeof(visited));
           mx=-1;
           if(ar[i][j])
           {
               bfs(i,j);
               for(int k=0;k<q;k++)
               {
                   if(ans[rare[k].x][rare[k].y]==10000)
                   {
                       flag=1;
                       break;
                   } 
               }
               if(!flag)
               {
                   for(int k=0;k<q;k++)
                   {
                       mx=max(mx,ans[rare[k].x][rare[k].y]);
                   }
               }
               fans=min(fans,mx);
           }
       }
   }
   
   cout<<fans<<endl;
   
   }

   
   
   
   
4. Задача 2

   Многие ответили верно. Исходный вариант:
   

   
   void stupdown(int *main_local_addr)
   {
       int fun_local;
       if (main_local_addr < &fun_local)
           printf("Stack grows upward\n");
       else
           printf("Stack grows downward\n");
   }
    
   int main()
   {
       // st's local variable
       int main_local;
    
       stupdown(&main_local);
       return 0;
   }
   

   
   
   
   
5. Задача 3

   Исходный вариант решения:
   

   
   // A Stack based C++ program to find next
   // greater element for all array elements.
   #include<bits/stdc++.h>
   using namespace std;
    
   /* prints element and NGE pair for all
      elements of arr[] of size n */
   void printNGE(int arr[], int n)
   {
       stack<int> s;
    
       /* push the first element to stack */
       s.push(arr[0]);
    
       // iterate for rest of the elements
       for (int i=1; i<n; i++)
       {
           int next = arr[i];
    
           if (s.empty() == false)
           {
               // if stack is not empty, then
               // pop an element from stack
               int element = s.top();
               s.pop();
    
               /* If the popped element is smaller
                  than next, then
                  a) print the pair
                  b) keep popping while elements are
                  smaller and stack is not empty */
               while (element < next)
               {
                   cout << element << " --> " << next
                        << endl;
                   if (s.empty() == true)
                      break;
                   element = s.top();
                   s.pop();
               }
    
               /* If element is greater than next,
                  then push the element back */
               if (element > next)
                   s.push(element);
           }
    
           /* push next to stack so that we can find
              next greater for it */
           s.push(next);
       }
    
       /* After iterating over the loop, the remaining
          elements in stack do not have the next greater
          element, so print -1 for them */
       while (s.empty() == false)
       {
           cout << s.top() << " --> " << -1 << endl;
           s.pop();
       }
   }
    
   /* Driver program to test above functions */
   int main()
   {
       int arr[] = {11, 13, 21, 3};
       int n = sizeof(arr)/sizeof(arr[0]);
       printNGE(arr, n);
       return 0;
   }