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

    Мы подготовили для Вас новый выпуск ITренировки — с задачами от Amazon.

    КДПВ

    Ниже приведены вопросы и задачи для соискателей на должность инженера-разработчика в Amazon, сложность традиционно варьируется от низкой до высокой. А некоторые вопросы под силу решить только самым пытливым умам :) Предлагаем решить их и тем, кто готовится к собеседованию в компанию подобного уровня и просто для проверки собственных сил.

    Вопросы


    1. Find missing int
      We are given an Excel sheet which contains integers from 1 to 50, including both. However, the numbers are in a jumbled form and there is 1 integer missing. You have to identify the missing integer. Only the logic is required.

      Перевод
      Дана таблица Excel, содержащая числа от 1 до 50 включительно. Числа неупорядочены, а одно число — пропущено. Необходимо найти это число. Для решения задачи достаточно логики.

    2. Robots and parachutes
      Two robots land with their parachutes on an infinite one-dimensional number line. They both release their parachutes as soon as they land and start moving. They are allowed only to make use of the following functions.

      I. moveLeft() // robot moves to left by 1 unit in 1 unit time

      II. moveRight() // robot moves to right by 1 unit in 1 unit time

      III. noOperation() // robot does not move and takes 1 unit time

      IV. onTopOfParachute() // returns true if the robot is standing on top of either of the parachute, else false

      V. didWeMeet() // returns true if the robot meets to the other robot, else false

      Write a function in order to make the robots meet each other. Robots will be executing the same copy of this function. Pseudocode is accepted.

      Перевод
      Два робота с парашютами приземляются на бесконечную плоскую ленту. Оба отстёгивают парашюты и начинают двигаться. Роботы могут выполнять следующие инструкции:

      I. moveLeft() // робот двигается влево на 1 единицу за 1 единицу времени

      II. moveRight() // робот двигается вправо на 1 единицу за 1 единицу времени

      III. noOperation() // робот выжидает на месте 1 единицу времени

      IV. onTopOfParachute() // возвращает true если робот стоит на парашюте, иначе — возвращает false

      V. didWeMeet() // возвращает true, если робот встретил другого робота, иначе — false.

      Напишите функцию, обеспечивающую встречу роботов. Роботы выполняют одинаковые копии этой функции. Псевдокод приемлем.

    Задачи


    1. Run length encoding
      Given an input string, write a function that returns the Run Length Encoded string for the input string.

      For example, if the input string is “wwwwaaadexxxxxx”, then the function should return “w4a3d1e1x6”.
      Перевод
      Дана входная строка, напишите функцию, которая возвращает кодирование длин серий входной строки.

      Например, входная строка “wwwwaaadexxxxxx” должна быть преобразована к “w4a3d1e1x6”.

    2. Students and chocolates
      Given n boxes containing some chocolates arranged in a row. There are k number of students. The problem is to distribute maximum number of chocolates equally among k students by selecting a consecutive sequence of boxes from the given lot. Consider the boxes are arranged in a row with numbers from 1 to n from left to right. We have to select a group of boxes which are in consecutive order that could provide maximum number of chocolates equally to all the k students. An array arr[] is given representing the row arrangement of the boxes and arr[i] represents number of chocolates in that box at position ‘i’.

      Examples:

      Input: arr[] = {2, 7, 6, 1, 4, 5}, k = 3
      Output: 6
      The subarray is {7, 6, 1, 4} with sum 18.
      Equal distribution of 18 chocolates among
      3 students is 6.
      Note that the selected boxes are in consecutive order
      with indexes {1, 2, 3, 4}.
      Перевод
      Дано n ящиков с шоколадом, уложенных в ряд. Также присутствует k студентов. Задача — разделить максимально возможное количество шоколада поровну между студентами, выбрав подпоследовательность ящиков в ряду. Предположим, ящики пронумерованы от 1 до n слева направо. Мы должны последовательно выбрать группу ящиков, расположенных рядом, которые содержат максимальное количество шоколада, делимого поровну между студентами. Массив arr[] представляет собой ящики, расположенные в ряд, а значение arr[i] представляет количество шоколада в ящике 'i'.

      Например:

      Вход: arr[] = {2, 7, 6, 1, 4, 5}, k = 3
      Выход: 6 (количество шоколада, которое достанется одному студенту)
      Подмассив {7, 6, 1, 4} с суммой 18. Распределение 18 шоколадок между студентами даст 6 шок/чел. Выбранные индексы ящиков — {1, 2, 3, 4}.

    3. Print all anagrams together
      Given an array of words, print all anagrams together. For example, if the given array is {“cat”, “dog”, “tac”, “god”, “act”}, then output may be “cat tac act dog god”.
      Перевод
      Дан массив слов, напечатайте все анаграммы вместе. Например, в массиве {“cat”, “dog”, “tac”, “god”, “act”} вывод может быть «cat tac act dog god».


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

    Решения


    1. Вопрос 1
      Верный ответ дан в первом же комментарии. Также верное, при некоторых условиях, решение предложено тут

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

    3. Задача 1
      Было предложено несколько правильных вариантов. Исходный:
      #include<stdio.h>
      #include<string.h>
      #include<stdlib.h>
      #define MAX_RLEN 50
       
      /* Returns the Run Length Encoded string for the 
         source string src */
      char *encode(char *src)
      {     
        int rLen;
        char count[MAX_RLEN];
        int len = strlen(src);
         
        /* If all characters in the source string are different, 
          then size of destination string would be twice of input string.
          For example if the src is "abcd", then dest would be "a1b1c1d1"
          For other inputs, size would be less than twice.  */
        char *dest = (char *)malloc(sizeof(char)*(len*2 + 1));
        
        int i, j = 0, k;
       
        /* traverse the input string one by one */
        for(i = 0; i < len; i++)
        {
       
          /* Copy the first occurrence of the new character */
          dest[j++] = src[i];
           
          /* Count the number of occurrences of the new character */
          rLen = 1;     
          while(i + 1 < len && src[i] == src[i+1])
          {
            rLen++;
            i++;
          }   
           
          /* Store rLen in a character array count[] */
          sprintf(count, "%d", rLen);
       
          /* Copy the count[] to destination */
          for(k = 0; *(count+k); k++, j++)
          { 
            dest[j] = count[k]; 
          } 
        }  
       
        /*terminate the destination string */
        dest[j] = '\0';
        return dest;
      }     
       
      /*driver program to test above function */
      int main()
      {
        char str[] = "geeksforgeeks";    
        char *res = encode(str);
        printf("%s", res);
        getchar();
      }
      


    4. Задача 2
      Исходный вариант решения:
      // Java implementation to find the maximum number
      // of chocolates to be distributed equally among
      // k students
      import java.io.*;
      import java.util.*;
      class GFG {
      // Function to find the maximum number of chocolates
      // to be distributed equally among k students
      static int maxNumOfChocolates(int arr[], int n, int k)
      {
          // Hash table
          HashMap <Integer,Integer> um = new HashMap<Integer,Integer>();
       
          // 'sum[]' to store cumulative sum, where
          // sum[i] = sum(arr[0]+..arr[i])
          int[] sum=new int[n];
          int curr_rem;
       
          // To store sum of sub-array having maximum sum
          int maxSum = 0;
       
          // Building up 'sum[]'
          sum[0] = arr[0];
          for (int i = 1; i < n; i++)
              sum[i] = sum[i - 1] + arr[i];
       
          // Traversing 'sum[]'
          for (int i = 0; i < n; i++) {
       
              // Finding current remainder
              curr_rem = sum[i] % k;
       
              // If true then sum(0..i) is divisible
              // by k
              if (curr_rem == 0) {
                  // update 'maxSum'
                  if (maxSum < sum[i])
                      maxSum = sum[i];
              }
       
              // If value 'curr_rem' not present in 'um'
              // then store it in 'um' with index of its
              // first occurrence
              else if (!um.containsKey(curr_rem) )
                  um.put(curr_rem , i);
       
              else
                  // If true, then update 'max'
                  if (maxSum < (sum[i] - sum[um.get(curr_rem)]))
                  maxSum = sum[i] - sum[um.get(curr_rem)];
          }
       
          // Required maximum number of chocolates to be
          // distributed equally among 'k' students
          return (maxSum / k);
      }
       
      // Driver Code
      public static void main(String[] args)
      {
      int arr[] = { 2, 7, 6, 1, 4, 5 };
      int n = arr.length;
      int k = 3;
      System.out.println("Maximum number of chocolates: "
                          + maxNumOfChocolates(arr, n, k));
      }
          }
      


    5. Задача 3
      Вариант решения на python:
      # structure for each word of duplicate array
      class Word(object):
          def __init__(self, string, index):
              self.string = string
              self.index = index
       
      # Create a DupArray object that contains an array
      # of Words
      def createDupArray(string, size):
          dupArray = []
       
          # One by one copy words from the given wordArray
          # to dupArray
          for i in xrange(size):
              dupArray.append(Word(string[i], i))
       
          return dupArray
       
      # Given a list of words in wordArr[]
      def printAnagramsTogether(wordArr, size):
          # Step 1: Create a copy of all words present in
          # given wordArr.
          # The copy will also have orignal indexes of words
          dupArray = createDupArray(wordArr, size)
       
          # Step 2: Iterate through all words in dupArray and sort
          # individual words.
          for i in xrange(size):
              dupArray[i].string = ''.join(sorted(dupArray[i].string))
       
          # Step 3: Now sort the array of words in dupArray
          dupArray = sorted(dupArray, key=lambda k: k.string)
       
          # Step 4: Now all words in dupArray are together, but
          # these words are changed. Use the index member of word
          # struct to get the corresponding original word
          for word in dupArray:
              print wordArr[word.index],
       
      # Driver program
      wordArr = ["cat", "dog", "tac", "god", "act"]
      size = len(wordArr)
      printAnagramsTogether(wordArr, size)
      


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

    More
    Ads

    Comments 38

      +1
      Вопрос 1
      Пропущенное_число = (1 + 50) / 2 * 50 — Сумма_чисел_в_таблице

      Вопрос 2
      function meet() {
        moveLeft();
        while (!didWeMeet() && !onTopOfParachute()) {
          moveLeft();
          noOperation();
        }
        while (!didWeMeet()) {
          moveLeft();
        }
        say('Hurrah!')
      }
      
        0
        И встретятся они через 4*s единиц времени, где s — расстояние между парашютистами сразу после приземления.
          –1
          Оба будут двигаться влево бесконечно.
            0
            Хотя, если парашюты остаются на месте приземления (а они остаются по условию задачи), то — все ок.
          +2
          а так не проще?
          #1
          Сумма_чисел_от_1_до_50 — Сумма_чисел_в_таблице
            +1
            ну так выше же и дана формула суммы ряда.
            0

            1 вопрос — Гаусс, Карл! (С). Который решал ее в детстве безо всяких экселей.


            1 задача
            f = (=<<) (\s -> head s : show (length s)) . group

            3 задача
            h = map snd . sort . map (\s -> (sort s, s))

            ЗЫ детство Карла какое-то. Прошлая серия и то была интереснее.

              +1
              1 вопр. В екселе это номер строки, начиная с которой номер строки не равен числу.
                0
                Это только если числа отсортированы, находятся в одной колонке и записаны начиная с первой строки. В задаче же, как минимум, явно указано, что числа неупорядочены.
                  0
                  Разьве в екселе нет сортировки?
                    0
                    Попробуйте отсортировать числа, находящиеся в разных колонках на разных страницах.
                      0
                      Но ведь при вычислении через разность сумм их ведь тоже не ручками предлагается переносить?
                        0
                        Для суммирования можно просто выделять диапазоны ячеек, в том числе и на разных страницах.
                          0
                          Почему в одном случае можно, а в другом нельзя?
                            0
                            Попробуйте сами. Выделите в Excel несколько колонок на разных страницах и попробуйте их отсортировать для сравнения с номерами строк.
                              0
                              Почему в моём случае это сложно, а в вашем — посто?
                                0
                                Вы не спрашивайте, вы откройте Excel и попробуйте. Запишите в колонку A все нечётные от 1 до 49, в колонку B — все чётные от 2 до 50. А теперь отсортируйте эти значения так, чтобы они были в строках с соответствующими номерами.
                                  +1
                                  Ещё раз. Почему в поём случае это проблема, а в вашем — нет? Вы как будете вычислят пропущенное число? Макрос напишете или на калькуляторе? Эти числа ведь не сами найдутся и впрыгнут в калькулятр. В любом случае вам точно так же придётся эти числа найти, выделить, скопировать, куда-то вставить. Подозреваю, что у меня-то как раз ручных действий требуется меньше.
                                    0
                                    Ставите курсор в свободную ячейку. Набираете '=(1+50)/2*50-СУММ('. Зажав Ctrl, мышкой выбираете все нужные ячейки и/или диапазоны ячеек. Набираете ')'. Нажимаете Enter. Всё, пропущенное число найдено. Ничего копировать, вставлять и т.п. не надо.
                                      0
                                      То есть все те же действия ручками совершить надо.

                                      Ну ладно, что-то трёп затянулся. Я же не опровергаю вычислительное решение.

                                      Ну и на закуску. "… одно число — пропущено. Необходимо найти это число.". Найти, а не вычислить! Но как можно найти то, чего нет? Оно же пропущено!

                                      Вот. Вы как хотите, а я на этом закончил.
                                        0
                                        На мой взгляд не совсем корректно поставлена задача. Непонятно зачем приплели Excel. В Excel можно решить эту задачу большим количеством способов, вплоть до того что можно написать макрос. Я бы переформулировал бы задачу так. Дан массив размерностью 49, в котором находятся в неупорядоченном виде числа от 1 до 50, за исключением одного. Как за один проход найти пропущенное число? Ограничение по памяти О(1). И тогда решение от Rsa97 станет очевидным и самым простым.
                                          0
                                          Или даже так: вообще не использовать дополнительно память))
                              0
                              Я думаю, что Rsa97 имеет в виду, что-то вроде
                              SUM(Sheet1!A1:C10,Sheet2!A1:C10)
                                0
                                А Sheet1!A1:C10 и Sheet2!A1:C10 точно в одной таблице находятся?
                                  0
                                  По условию задачи — в одной.
                                    0
                                    Я читал условия задачи.
                                    В екселе разные листы — это точно одна и та же таблица?
                  0
                  Мой вариант #2
                  steps = 1;
                  do {
                  for (i=0;i < steps; i++) { moveLeft(); }
                  if (onTopOfParachute()) { noOperation(); }
                  else {
                  for (i=0;i < steps; i++) { moveRight();}
                  steps++;
                  }
                  } while(!didWeMeet())

                    0
                    Встретятся через s2 единиц времени, где s — расстояние между парашютистами сразу после приземления.
                      0
                      Поправка. Роботы не встретятся. После того, как один из роботов дойдёт до чужого парашюта, он пойдёт влево на s шагов, в то время, как второй робот будет двигаться мимо него вправо.
                        –1
                        image
                          0
                          Да, облажался.
                            0
                            А если одним роботом стоять на месте, а вторым шагать влево-вправо, каждый раз добавляя по +1 шагу (расшатывать) до тех пор пока они не встретятся.
                              0
                              Роботы должны выполнять одну и ту же программу. Кто из них слева, а кто справа — самим роботам неизвестно.
                                0
                                Так нельзя, потому что у них должна выполняться идентичная программа. Невозможно определить, кто первый, а кто второй.
                        +1
                        Моё решение для вопроса 2
                        bool checkParachute = false;
                        do {
                            moveLeft();
                            if (checkParachute)
                        	moveLeft();
                            else
                        	noOperation();
                            if (onTopOfParachute())
                        	checkParachute = true;		
                        } while (!didWeMeet());
                        

                          0
                          Такой вариант задачи:
                          Задача 1
                          public static string ConvertIntoSeriesLengths(string str)
                                  {
                                      if (str == string.Empty)
                                          return "Empty string passed";
                          
                                      int len = 1;
                                      char symb = str.ToCharArray()[0];
                                      string res = String.Empty;
                          
                                      for (int i = 1; i < str.ToCharArray().Length; i++)
                                      {
                                          if (str.ToCharArray()[i] == symb)
                                          {
                                              len++;
                                          }
                                          else
                                          {
                                              res += symb.ToString() + len.ToString();
                                              len = 1;
                                              symb = str.ToCharArray()[i];
                                          }
                                      }
                                      
                                      return res += symb.ToString() + len.ToString();
                                  }
                          


                            0
                            Задача 1
                            public static string ConvertIntoSeriesLengths(string str) {
                              var chars = str.ToCharArray();
                              if  (0 == chars.Length) {
                                return String.Empty;
                              }
                              int len, pos = 0;
                              char ch;
                              string res = String.Empty;
                              while (pos < chars.Length) {
                                len = 1;
                                ch = chars[pos++];
                                while (pos < chars.Length && ch == chars[pos]) {
                                  pos++;
                                  len++;
                                }
                                res += ch.toString() + len.toString();
                              }
                              return res;
                            }

                              0
                              Задача 1
                              'wwwwaaadexxxxxx'
                                .split('')
                                .reduce((acc, char) => {
                                  const last = acc[acc.length - 1]
                                  if (last && last.char === char) {
                                    last.count += 1
                                  } else {
                                    acc.push({ char, count: 1 })
                                  }
                                  return acc
                                }, [])
                                .reduce((acc, { char, count }) => `${acc}${char}${count}`, '')
                              

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