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