Выпуск#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;
      }
      


    Spice IT Recruitment

    69,98

    ИТ специализированное кадровое агентство

    Поделиться публикацией
    Комментарии 44
      +2
      А почему во втором вопросе ответ
      2
      thurday
      ?
        +1
        Я точно не знаю, но я получил ответ так — первые две буквы надо поменять местами, последние 3 записать в обратном порядке, а каждую букву в центре заменить на следующую в алфавите.
          0
          вот только в вопросе каждая буква в центре заменяется на предыдущую. Кажется, в задаче ошибка… Ну либо правильный ответ Thursday, а алгоритм сложнее.
            +1
            На Thursday букв не хватает. В задаче их 7, а не 8.

            У меня THSPDAY получилось
              0
              Дело в том, что предыдущие слова все по 8 символов. Так что, скорее всего, тут ошибка в условии (даже две).
            0
            По идее для расшифровки буквы в центре надо заменять на предыдущие в алфавите: в шифре IDTUBECN в центре это будут DISTANCE. Поэтому в зашифрованном HTTQYAD это должны быть THSPDAY. Похоже на ошибку в вопросе
              0
              У меня получилось THURDAY, а для того, чтобы было THURSDAY, в вопросе должно было быть слово HTTQRYAD.
                0
                я тож в уме прикинул, если так сделать будет th???day а единственное слово в английском которое подходит это thursday,, буквы в центре рандомные для запутывания?
                +2
                написавший был русским шпионом, поэтому сделал ошибку в слове. Но ответ такой, да.
                +1
                1
                Взвесить для каждой машины число болтов равное ее номеру.

                2
                THSPDAY тоже вышло, вероятно ошибка
                  +1
                  Задача 2
                  Поправьте, если я не прав: каждая локальная переменная помещается в стек. Так почему не сделать например так
                  void checkStack() {
                   int a;
                   int b;
                   if (&a < &b) {
                     cout << "Up" << endl;
                   } else {
                     cout << "Down" << endl;
                   }
                  }

                    +2
                    Думаю, не верно. В рамках одного вызова ни кто не гарантирует (даже не упоминает) порядок расположения локальных переменных в стеке.

                    Ну и сравнение указателей так просто не сработает. Надо к интам закастить.

                    Примерно так:

                    bool CheckStack(int *p)
                    {
                    	int var;
                    	if ((int)p == 0)
                    		return CheckStack(&var);
                    	return (int)(&var) < (int)p;
                    }
                    


                    Вызвать исходно с нулем. Если вернет 1, значит стек растет сверху вниз.

                    Тут рекурсия — последовательный вызов, так что гарантировано локальная переменная из первого экземпляра раньше по стеку, чем та же переменная из второго экземпляра.
                      0
                      Согласно этому указатели таки можно сравнивать as is.
                        0
                        Да. Я не прав. С какой стати это мне пришло в голову — понятия не имею.

                        Действительно, указатели одного типа можно сравнивать на больше/меньше непосредственно.
                  +1
                  А если нет никаких уточнений про механизм «weighing», почему бы не
                  1
                  сделать весы в виде сбалансированного горизонтального диска на центральном подвесе с равномерно расположенными по внешнему краю отверстиями для шурупов?
                    +1
                    Потому что в этом нет необходимости и всё решается с обычными весами :)
                      +1
                      Весы одни. Взвешивание одно.

                      1
                      Берём 1 шуруп с 1-й, 2 шурупа со второй… 10 с 10-й.
                      Сваливаем всё в кучу и идем взвешивать.
                      Ответ: 10 — (wight % 1) * 10.
                        +1
                        Ну это тривиальное решение которое я заведомо знал подсмотрел бы в комментариях выше. Моё — альтернативное и с инженерной точки зрения по некоторым критериям даже более подходящее.
                          +1
                          Я если честно немного сомневаюсь что люди, задающие такие задачи на собеседованиях, придерживаются такого же мнения :)
                            0
                            Я тоже сомневаюсь, что у них там есть несколько вариантов решения, скорее всего одно. В чём и проблема для таких тестов — только да/нет. Если же общаешься с реальным заинтересованным человеком — его может весьма заинтересовать необычный подход к проблеме.

                            В реальной жизни — почти любую задачу можно решить не одним, а 3-мя вариантами как минимум. В результате:
                            1) В уме: «Это ответ не правильный, у меня такого в вариантах нет», вербально: «Не правильно».
                            2) В уме: «Я тут начальник, не понял, слишком умный что-ли?», вербально: «Вы нам не подходите».
                            3) В уме: «Хм… интересно, как я до этого не додумался...»
                              0
                              Если же общаешься с реальным заинтересованным человеком — его может весьма заинтересовать необычный подход к проблеме.

                              Это если вас берут на должность где требуется необычный подход. А вот если вас берут на должность программиста, а вы каждый раз вместо того чтобы использовать существующие решения/программы/фреймворки, начинаете придумывать свои «альтернативные», то не думаю что это обрадует вашего работодателя :)

                              В реальной жизни — почти любую задачу можно решить не одним, а 3-мя вариантами как минимум. В результате:

                              А в результате всех интересует тот, который наиболее эффективен(при учёте всех необходимых требований естественно). А ваш способ эффективным назвать сложно.

                              П.С. И поймите меня правильно, я не говорю что ваша идея глупа или не нужна в принципе. Я сам иногда тендирую к поиску «нестандартных решений». Но в контексте задач для собеседований такой подход не особо правильный.
                                0
                                У нас тоже довольно большая команда, давно уже.
                                И перехожу уже с темы набора — от претендентов на реальную работу.
                                По претендентам максимальный плюс может выдать только TL или кто там главный в проекте. Но до него не дойдёт, отсеют по формальным признакам. Шлак. Тест не прошёл.

                                Мы отказались от этого.
                                  0
                                  Ну если переходить на конкретику, то мы от подобных задач на собсеседованиях отказались. Потому что умение их решать на мой взгляд ничего не говорит ни о том как человек может работать в команде, ни о том насколько хорошо и грамотно он умеет программировать.
                                  Максимум что мы делаем это даём потенциальным сениорам пример «кривого» на наш взгляд кода и спрашиваем что человек в нём поменял бы и почему. А потом просто смотрим куда приведёт обсуждение.
                            +2
                            Полностью согласен. Эта первая задачка тривиальна — для затравки, наверно.
                            Да, ваше решение действительно красивое и креативное, если понятие «весы» не определено.
                        0
                        Не знаю, какой хитрый алгоритм подразумевался в 3-й задаче, но через моё дерево двоичного поиска делается легко и красиво:
                        Python
                        import collections
                        import aa_sbst # Дерево, можно поиметь через "pip install aa_sbst"
                        
                        def NGEs(arr):
                            ans = [-1]*len(arr) # Здесь накопим результат
                            t_el = collections.namedtuple('t_el', 'v, pos')
                            t = aa_sbst.sbst()
                            for pos, v in enumerate(arr):
                                # Цикл по ранее встреченным меньшим элементам
                                for el in t.backward_from(t_el(v, 0), False):
                                    ans[el.pos] = v
                                    t.remove(el) # Второй раз обрабатывать не будем
                                t.add(t_el(v, pos))
                            return ans
                        

                        По скорости: 100000 за секунду с О(n*ln(n)) в худшем случае.
                          0
                          Хитрость в том,
                          Спойлер
                          что начинать надо с конца.
                          def nge(arr):
                              result = [-1] * len(arr)
                              current_greater = arr[-1]
                              for i in range(len(arr) - 2, -1, -1):
                                  if arr[i] < current_greater:
                                      result[i] = current_greater
                                  else:
                                      current_greater = arr[i]
                              return result
                          


                          4000000 за секунду. O(n).
                            0
                            Валится на первом тесткейсе:
                            >>> nge([4, 5, 2, 25])
                            [25, 25, 25, -1]
                            А должно быть [5, 25, 25, -1]
                              0
                              Тоже рассматривал в точности такой вариант. Решение простое, но неверное.
                              Для массива [1,2,3] оно выдаст [3,3,-1], а надо [2,3,-1].
                                0
                                Упс. Ошибочка вышла
                                Спойлер
                                def nge(arr):
                                    result = [-1] * len(arr)
                                    current_greater = arr[-1]
                                    for i in range(len(arr) - 2, -1, -1):
                                        if arr[i] < arr[i+1]:
                                            current_greater = arr[i+1]
                                        if arr[i] < current_greater:
                                            result[i] = current_greater
                                        else:
                                            current_greater = arr[i]
                                    return result
                                


                                Так, вроде, работает правильно.
                                  0

                                  WA на тесте [3, 1, 2, 4]

                                    0

                                    [-1, 2, 4, -1]
                                    да вроде все верно выдало

                                      +2
                                      Должно быть [4, 2, 4, -1]
                                  • НЛО прилетело и опубликовало эту надпись здесь
                                      0
                                      Идея идти с конца появилась, чтобы получить линейную сложность.
                                      Если сложность решения всё равно O(n^2), зачем что-то запутывать?

                                      Можно решить самым простым и наглядным способом, тоже за O(n^2): идти от начала вперёд, и от каждого элемента снова вперёд, пока не найдёшь больший, чем текущий.

                                      • НЛО прилетело и опубликовало эту надпись здесь
                                0
                                Задача про стек
                                www.onlinegdb.com/HJuG7efkX
                                  0

                                  Это вопросы из корейского самсунга что ли, или почему английский такой корявый? Или вы сами придумываете задачи, потом их коряво переводите и выдаёте за оригинал?

                                    0
                                    Что Вы имеет против корейского Самсунга? )
                                    Английский вариант обычно публикуем без изменений, если ошибки не влияют на смысл.

                                    ps. Кстати, большая часть вопросов — из азиатского сегмента (Индия, Китай, Япония, Корея)
                                      +1

                                      Ничего не имею. Просто если так, то понятно, а от американского Сансунга (а именно там много software и R&D отделов) странно было бы такое получить.

                                    0
                                    в1 - дефект массы

                                    1 винт от 1 машины, 2 винта от 2 машины и т.д.
                                    найти дефект массы и поделить на единичный дефект, получим номер машины


                                    в2 - ой холмс, у вас буква отклеилась!
                                    D I . S T A . N C E
                                     x    + + +     X
                                    I D . T U B . E C N
                                    
                                    D O . C U M . E N T
                                     x    + + +     X
                                    O D . D V N . T N E
                                    
                                    H T . T Q . Y A D
                                     x    - -     X
                                    T H . S P . D A Y

                                    хз как расшифровывать 7-буквенные слова. Но допустим, что в конце DAY. А в начале может быть всё что угодно и как попало.

                                      0

                                      задача 1. как-то очень криво сформулирована.
                                      Приходится домысливать за топикстартера! Всё по-взрослому, вот тебе хотелки, сам себе сделай ТЗ!
                                      Поэтому под кат не прячу. Пусть будет спойлер, а авторам пусть будет стыдно.


                                      Допустим, так. Локации пронумерованы. Дана матрица смежности. Если локации смежные, то расстояние между ними 1. В некоторых локациях есть источники (потому что локаций — до 20 — по размеру матрицы, а источников — до 5).


                                      Тупое решение, благо, размер матрицы позволяет.


                                      1. Получаем матрицу расстояний из матрицы смежности. Это — тупо, возвести матрицу смежности в 20 степень, где (умножение) — это сложение, а (сложение) — это минимум. А единичка смежности считается 1 расстояния, нолик смежности считается бесконечностью, а на диагонали стоят 0. (расстояние до самих себя, естественно, нулевое).


                                      2. Для каждой локации посчитать сумму расстояний до всех источников.


                                      3. Найти минимум.
                                        0
                                        Задача 2 про стек

                                        элементарно ватсон!


                                        ptrdiff_t delta(char* caller) {
                                          char inside;
                                          return &inside - caller;
                                        }
                                        
                                        bool stack_grows_up() {
                                            char caller;
                                            return delta(caller) > 0;
                                        }
                                          0
                                          Задача 3 про NGE, наивное решение за квадратное время
                                          def NGEs(xs):
                                            return [
                                              next(  # первая итерация
                                                (y for y in xs[i+1:] if y > x),  # итератор по следующим бОльшим элементам
                                                -1)  # дефолт первой итерации
                                              for n in (len(xs),)  # трюк с переменной внутри генератора
                                              for i in range(n)
                                              for x in (xs[i],)  # трюк с переменной внутри генератора
                                            ]
                                            0
                                            Бракованные винты
                                            Взять количество винтов соответствующее порядковому номеру машины от каждой машины, сумму взвешать, определить десятичную дробную часть и отнимаем от 10.
                                            Например из xx.4 берем 4, затем от 10 отнимает 4 и получаем 6, т.е. 6 машина производит бракованные винты.
                                            Шифр Шерлока
                                            Паттерн прослеживается, но там ошибка. Ответ должен был быть THURSDAY. placementstudy.com/discuss/puzzles/interview-puzzle-2/477025101

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

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