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

    Подоспел очередной выпуск ITренировки, и сегодня в номере — задачи от интервьюеров Microsoft.

    КДПВ

    В подборку вошли задачи с собеседований Microsoft. Сложность, традиционно, варьируется от простых до таких, над которыми нужно немного поразмыслить. Мы предпочитаем делать это в спокойной обстановке, нежели в цейтноте на собеседовании, и желаем, чтобы Ваши собеседования проходили так же спокойно, расслабленно и конструктивно :)

    Вопросы


    1. Dominos on the chessboard
      There is an 8 by 8 chessboard in which two diagonally opposite corners have been cut off. You are given 31 dominos, and a single domino can cover exactly two squares. Can you use the 31 dominos to cover the entire board?

      Перевод
      У обычной шахматной доски отрезаны две противоположных по диагонали клетки. Вам дана 31 косточка домино. Одна кость покрывает ровно 2 шахматных клетки. Сможете ли Вы покрыть все поле этими косточками?

    2. Gold for work
      You’ve got someone working for you for seven days and a gold bar to pay them. You must pay the worker for their work at the end of every day. If you are only allowed to make two breaks in the gold bar, how do you pay your worker? (Assuming equal amount of work is done during each day thus requiring equal amount of pay for each day)

      Перевод
      На Вас работает некто в течение семи дней с оплатой за работу в слиток золота. Вы должны расплачиваться с работником ежедневно в конце дня. Как вы будете рассчитываться с работником, если Вам разрешено разломить слиток лишь дважды? (Предполагается, что ежедневно выполняется одинаковый объём работы, требующий одинаковой оплаты)


    Задачи


    1. Reverse a linked list
      Given pointer to the head node of a linked list, the task is to reverse the linked list. We need to reverse the list by changing links between nodes.

      Examples:

      Input: Head of following linked list
      1->2->3->4->NULL
      Output: Linked list should be changed to,
      4->3->2->1->NULL

      Input: Head of following linked list
      1->2->3->4->5->NULL
      Output: Linked list should be changed to,
      5->4->3->2->1->NULL

      Input: NULL
      Output: NULL

      Input: 1->NULL
      Output: 1->NULL


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

      Примеры:
      Вход: Указатель на головную ноду, и сам список — 1->2->3->4->NULL
      Выход: 4->3->2->1->NULL

      Вход: 1->2->3->4->5->NULL
      Выход: 5->4->3->2->1->NULL

      Вход: NULL
      Выход: NULL

      Вход: 1->NULL
      Выход: 1->NULL

    2. Longest Bitonic Subsequence
      Given an array arr[0 … n-1] containing n positive integers, a subsequence of arr[] is called Bitonic if it is first increasing, then decreasing. Write a function that takes an array as argument and returns the length of the longest bitonic subsequence.
      A sequence, sorted in increasing order is considered Bitonic with the decreasing part as empty. Similarly, decreasing order sequence is considered Bitonic with the increasing part as empty.

      Examples:

      Input arr[] = {1, 11, 2, 10, 4, 5, 2, 1};
      Output: 6 (A Longest Bitonic Subsequence of length 6 is 1, 2, 10, 4, 2, 1)

      Input arr[] = {12, 11, 40, 5, 3, 1}
      Output: 5 (A Longest Bitonic Subsequence of length 5 is 12, 11, 5, 3, 1)

      Input arr[] = {80, 60, 30, 40, 20, 10}
      Output: 5 (A Longest Bitonic Subsequence of length 5 is 80, 60, 30, 20, 10)

      Перевод
      Дам массив arr[0… n-1] содержащий в себе n положительных целых чисел. Назовём подпоследовательность arr[] «Битонной», если элементы в ней сначала увеличиваются, затем уменьшаются. Напишите функцию, принимающую в качестве аргумента массив и возвращающую длину самой длинной битонной подпоследовательности.
      Последовательность, отсортированная по возрастанию, считается битонной с отсутствующей убывающей частью.
      Аналогично, последовательность, отсортированная по убыванию, считается битонной, с отсутствующей возрастающей частью.

      Пример:

      Вход: arr[] = {1, 11, 2, 10, 4, 5, 2, 1};
      Выход: 6 (Длина наибольшей битонной подпоследовательности — 6 { 1, 2, 10, 4, 2, 1})

      Вход: arr[] = {12, 11, 40, 5, 3, 1}
      Выход: 5 (12, 11, 5, 3, 1)

      Вход: arr[] = {80, 60, 30, 40, 20, 10}
      Выход: 5 (80, 60, 30, 20, 10)

    3. Inplace transformation
      Given a string, move all even positioned elements to end of string. While moving elements, keep the relative order of all even positioned and odd positioned elements same with O(1) space and O(n) time.
      In other words given a string with alternating elements (numbers and letters) like this [a1b2c3d4] should be converted to [abcd1234].

      Перевод
      Дана строка, необходимо сместить все элементы, находящиеся на чётной позиции в конец строки. При перемещении элементов необходимо сохранять относительный порядок элементов, чётных и нечётных. Ограничения — O(1) памяти и O(n) времени выполнения.
      Другими словами, строка с чередующимися элементами (цифрами и буквами), например [a1b2c3d4] должна быть преобразована в [abcd1234].



    Решения


    1. Вопрос 1
      Нет, kardan2 ответил почему.

    2. Вопрос 2
      Было предложено верное решение

    3. Задача 1
      В комментариях было предложено корректное решение. Исходный вариант:

      void ReverseRecursive(struct Node** head_ref)
      {
          struct Node* first;
          struct Node* rest;
           
          /* empty list */
          if (*head_ref == NULL)
             return;   
      
          /* suppose first = {1, 2, 3}, rest = {2, 3} */
          first = *head_ref;  
          rest  = first->next;
      
          /* List has only one node */
          if (rest == NULL)
             return;   
      
          /* reverse the rest list and put the first element at the end */
          recursiveReverse(&rest);
          first->next->next  = first;  
          
          /* tricky step -- see the diagram */
          first->next  = NULL;          
      
          /* fix the head pointer */
          *head_ref = rest;              
      }
      


    4. Задача 2
      Вариант решения:
      using System;
      
      class LBS {
          
          /* lbs() returns the length of the Longest Bitonic Subsequence in
          arr[] of size n. The function mainly creates two temporary arrays
          lis[] and lds[] and returns the maximum lis[i] + lds[i] - 1.
      
          lis[i] ==> Longest Increasing subsequence ending with arr[i]
          lds[i] ==> Longest decreasing subsequence starting with arr[i]
          */
          static int lbs(int[] arr, int n)
          {
              int i, j;
      
              /* Allocate memory for LIS[] and initialize 
                 LIS values as 1 for all indexes */
              int[] lis = new int[n];
              for (i = 0; i < n; i++)
                  lis[i] = 1;
      
              /* Compute LIS values from left to right */
              for (i = 1; i < n; i++)
                  for (j = 0; j < i; j++)
                      if (arr[i] > arr[j] && lis[i] < lis[j] + 1)
                          lis[i] = lis[j] + 1;
      
              /* Allocate memory for lds and initialize LDS values for
                  all indexes */
              int[] lds = new int[n];
              for (i = 0; i < n; i++)
                  lds[i] = 1;
      
              /* Compute LDS values from right to left */
              for (i = n - 2; i >= 0; i--)
                  for (j = n - 1; j > i; j--)
                      if (arr[i] > arr[j] && lds[i] < lds[j] + 1)
                          lds[i] = lds[j] + 1;
      
              /* Return the maximum value of lis[i] + lds[i] - 1*/
              int max = lis[0] + lds[0] - 1;
              for (i = 1; i < n; i++)
                  if (lis[i] + lds[i] - 1 > max)
                      max = lis[i] + lds[i] - 1;
      
              return max;
          }
          
          // Driver code
          public static void Main()
          {
              int[] arr = { 0, 8, 4, 12, 2, 10, 6, 14, 1, 9, 5,
                                            13, 3, 11, 7, 15 };
              int n = arr.Length;
              Console.WriteLine("Length of LBS is " + lbs(arr, n));
          }
      }
      


    5. Задача 3
      Вариант решения:
      #include <stdio.h>
      #include <string.h>
      #include <math.h>
      
      // A utility function to swap characters
      void swap ( char* a, char* b )
      {
          char t = *a;
          *a = *b;
          *b = t;
      }
      
      // A utility function to reverse string str[low..high]
      void reverse ( char* str, int low, int high )
      {
          while ( low < high )
          {
              swap( &str[low], &str[high] );
              ++low;
              --high;
          }
      }
      
      // Cycle leader algorithm to move all even positioned elements
      // at the end.
      void cycleLeader ( char* str, int shift, int len )
      {
          int j;
          char item;
      
          for (int i = 1; i < len; i *= 3 )
          {
              j = i;
      
              item = str[j + shift];
              do
              {
                  // odd index
                  if ( j & 1 )
                      j = len / 2 + j / 2;
                  // even index
                  else
                      j /= 2;
      
                  // keep the back-up of element at new position
                  swap (&str[j + shift], &item);
              }
              while ( j != i );
          }
      }
      
      // The main function to transform a string. This function mainly uses
      // cycleLeader() to transform
      void moveNumberToSecondHalf( char* str )
      {
          int k, lenFirst;
      
          int lenRemaining = strlen( str );
          int shift = 0;
      
          while ( lenRemaining )
          {
              k = 0;
      
              // Step 1: Find the largest prefix subarray of the form 3^k + 1
              while ( pow( 3, k ) + 1 <= lenRemaining )
                  k++;
              lenFirst = pow( 3, k - 1 ) + 1;
              lenRemaining -= lenFirst;
      
              // Step 2: Apply cycle leader algorithm for the largest subarrau
              cycleLeader ( str, shift, lenFirst );
      
              // Step 4.1: Reverse the second half of first subarray
              reverse ( str, shift / 2, shift - 1 );
      
              // Step 4.2: Reverse the first half of second sub-string.
              reverse ( str, shift, shift + lenFirst / 2 - 1 );
      
              // Step 4.3 Reverse the second half of first sub-string and first
              // half of second sub-string together
              reverse ( str, shift / 2, shift + lenFirst / 2 - 1 );
      
              // Increase the length of first subarray
              shift += lenFirst;
          }
      }
      
      // Driver program to test above function
      int main()
      {
          char str[] = "a1b2c3d4e5f6g7";
          moveNumberToSecondHalf( str );
          printf( "%s", str );
          return 0;
      }
      


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

    More
    Ads

    Comments 9

      +2
      Задача 2. Gold for work
      Спойлер
      Разламываем слиток:
      Первый раз разламываем слиток на две части: 3/7 и 4/7
      Второй раз разламываем 3/7 слитка на две части: 1/7 и 2/7
      Оплата:
      Первый день: отдаем 1/7
      Второй день: отдаем 2/7, работник дает сдачу 1/7
      Третий день: отдаем 1/7
      Четвертый день: отдаем 4/7, работник дает сдачу 1/7 + 2/7
      Пятый день: отдаем 1/7
      Шестой день: отдаем 2/7, работник дает сдачу 1/7
      Седьмой день: отдаем 1/7
        0
        Эта задача (точнее, ее решение) всегда вызывала у меня негодование: получается, что мы должны запретить работнику тратить его зарплату. Плохая задача, я считаю
          0
          А часто она Вам встречается?
            0
            До сегодняшнего дня — не меньше одного раза.
            0
            Во-первых получая предоплату, вы в случае неудачи должны её вернуть, т.е. иметь на балансе.
            Во-вторых, данный дискомфорт обоюден, т.к. заказчик тоже не может свободно распоряжаться своей долей во времени. И это надо понимать, и находить компромисс…
              0
              Вы, безусловно, правы, но речь идет не о предоплате. Первый кусок слитка — полноценная зарплата за один рабочий день.
          +2
          Мои решения.
          Вопрос 1
          Нет.
          Каждая доминошка покрывает 1 белую клетку и 1 черную. Если убрать симметричные клетки (а они одного цвета), то баланс цветов нарушится.

          Вопрос 2
          Нужно разделить слиток на 3 части в пропорции 1-2-4.
          В первый день отдает 1.
          Во второй день забираем 1 обратно и отдаем 2.
          в среду отдает 1 и ничего не берем в замен.
          в четверг отдает 4 и забираем обратно 1 и 2
          и т.д.

          Задача 3
          Пока без кода. Если воспринимать условия, как «в любой момент должна сохраняться последовательность четных и нечетных», то задача может решится только за O(n^2).
          В этом случае, замену местами можно сделать только если 2 элемента стоят рядом. А это квадратичная зависимость.
          Если же последовательность не обязана сохраняться, а должна быть только восстановлена в конце, то я предлагаю такой ход мыслей.
          У нас есть фиксированный набор переменных, можно ограничится всего 1. Это значит, что элементы в массиве можно ТОЛЬКО менять местами.
          Нам нужна линейная зависимость. Вспоминаем, что сумма убывающей геометрической прогрессии линейна. n+1/2n+1/4n+1/8n+...<2n.
          Делим наш массив на 3 зоны, в пропорции 1-2-1. Добиваемся, что все числа из первой и третей зоны стали на место, а вторая часть опять заполнена в перемешку. Таким образом мы за 1 итерацию свели задачу с ней самой же, но сократили длину в 2 раза.
          Т.е. если у нас есть 1a2b3c4d5e6f, то после первой итерации получим 123-4a5b6c-def.
          Здесь есть вопросы нечетной длины, и теоретического обоснования, но суть концепции представлена. Постараюсь оформить в виде кода.
            +1
            Задача 1. Легкотня
            public class Node {
                public String value = null;
                public Node next = null;
            
                public Node(String _value, Node _next) {
                    value = _value;
                    next = _next;
                }
                
                public static Node reverse(Node _node){
                    Node base = _node;
                    Node result = null;     
                    while(base!=null){
                        Node temp = base;
                        base = temp.next;
                        temp.next = result;
                        result = temp;
                        
                    }
                    return result;
                }
            }


            Задача 2. Без кода.
            По сути сводится к нахождению для каждого элемента убывающей последовательности слева и справа, и суммированию длин этих последовательностей. Правда решается за квадратичные затраты от n. ХМ, э нет, я пожалуй поищу решение получше.

            А вообще мне понравились задачи от Майкрософт, и пусть к самому продукту отношение негативное, задачи что здесь, что раньше, очень адекватные для тестирования. Ни через чур сложные, ни слишком легкие.
              0
              Оптимизация жеж
              Наибольшая возрастающая подпоследовательность(ну его просто так по дефолту кличут), имеет оптимизацию до O(n*log n) за счет динамики

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