Pull to refresh
0
Spice IT Recruitment
ИТ-специализированное кадровое агентство

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

Reading time 5 min
Views 14K
Пока мозг ещё не окончательно превратился в оливье, самое время немного заставить его поработать. Новая подборка логических и алгоритмических задач, предлагаемых на собеседованиях в известные IT-компании.

КДПВ

В нашу первую в новом году подборку попали вопросы и задачи, задаваемые в Alcatel-Lucent (Nokia).
Задачи мы постарись подобрать с различным уровнем сложности. На некоторые (а, может быть, и на все) вопросы можно найти ответ на просторах интернета, но это ведь не наш путь, верно?
Предлагаем интеллектуально размяться и попробовать самостоятельно решить приведённые задачи.


Вопросы


  1. Бактерия в пробирке
    Logical task about bacteria increasing in a retort. 1 bacteria will fill it in a minute, how long it takes to fill a retort if 4 bacteria present at start? Each bacteria divides into 2 same size bacteria each second.

    Перевод
    Логическая задача — 1 бактерия путем деления заполняет пробирку за минуту. Сколько времени займёт заполнение пробирки, если на старте 4 бактерии? Каждая бактерия делится на 2 бактерии такого же размера ежесекундно.
  2. 25 лошадей
    You have 25 horses, what is the minimum number of races you can find the top 3. In one race you can race 5 horses, and you don't have a timer.

    Перевод
    Нужно определить минимальное количество забегов, за которое можно выявить тройку победителей среди 25 лошадей. В один забег можно пускать максимум 5 лошадей, секундомер не предусмотрен.

Задачи


  1. Построить строку с подмножествами
    Two strings s1 and s2 are given. You have make a new string s3 such that it has both s1 and s2 as one of its subsequences and length of s3 is minimum.

    Example: apple pear => applear

    Перевод
    Из двух строк s1 и s2 собрать новую строку s3, содержащую s1 и s2 в качестве подможножеств. s3 должна быть минимальной длины.
    Пример: apple pear => applear
  2. Словарная сортировка чисел
    How will you dictionary sort integers without converting them to strings?
    For ex: 1 2 10 20 100 110 => 1 10 100 110 2 20.

    Перевод
    Как бы Вы отсортировали целые числа в словарном порядке без приведения их к строке?
    Пример: 1 2 10 20 100 110 => 1 10 100 110 2 20.
  3. Найти добавочные элементы в массиве
    Given two integer arrays A and B.
    B contains exactly same numbers as A except two additional numbers. Find the two elements with minimum time and space complexity.
    for ex: A ={1, 4, 2, 6, 3}
    B = {4, 0,7, 6, 3, 2, 1}
    ans: 0 7

    Перевод
    Даны массивы чисел A и B. Массив B содержит все числа из A + ещё 2 числа. Предложить алгоритм нахождения этих 2 чисел, оптимальный по скорости и объёму памяти.
    Пример:
    A ={1, 4, 2, 6, 3}
    B = {4, 0,7, 6, 3, 2, 1}
    Результат: 0 7

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

Решения


  1. Вопрос 1
    Многие комментаторы ответили правильно — 58 секунд. Можно было прийти к ответу логическим путём, а кто-то решил логарифмически :)

  2. Вопрос 2
    Многие тоже нашли верное решение. Ответ — 7 забегов.

    Пронумеруем лошадей. Первые пять забегов:
    1. 1 2 3 4 5
    2. 6 7 8 9 10
    3. 11 12 13 14 15
    4. 16 17 18 19 20
    5. 21 22 23 24 25
    Выбыли 10 лошадей, поскольку они не могут претендовать на место в тройке лидеров.

    В шестом забеге выявим абсолютного лидера:
    6. 1 6 11 16 21

    Теперь картина следующая:
    1 2 3 4 5
    6 7 8 9 10
    11 12 13 14 15
    16 17 18 19 20
    21 22 23 24 25

    Выбыло ещё 10 лошадей — все лошади забегов, чьи лидеры пришли 4 и 5, поскольку они не могут претендовать на призовые места, лошади третьей группы (поскольку их лидер занял третье место и они могут расчитывать на 4+), и третья лошадь второй группы, потому что тоже может расчитывать только на 4+ место, а также лошадь занявшая 1-ое место как абсолютный лидер.

    В седьмом забеге выявляем первую пару сильнейших — они из займут почётные места в тройке лидеров:

    7. 2 3 6 7 11

    Я рассмотрел случай, когда все сильные лошади в одной группе, но перестановка их общей картины не меняет.

  3. Задача 1
    Оригинальное решение для подпоследовательностей на Java:
    public class GFG_1 {
         
        String a , b;
         
        // Prints super sequence of a[0..m-1] and b[0..n-1] 
        static void printSuperSeq(String a, String b)
        {
            int m = a.length(), n = b.length();
            int[][] dp = new int[m+1][n+1];
          
            // Fill table in bottom up manner
            for (int i = 0; i <= m; i++)
            {
                for (int j = 0; j <= n; j++)
                {
                   // Below steps follow above recurrence
                   if (i == 0)
                       dp[i][j] = j;
                   else if (j == 0 )
                       dp[i][j] = i;
                   else if (a.charAt(i-1) == b.charAt(j-1))
                        dp[i][j] = 1 + dp[i-1][j-1];
                   else
                        dp[i][j] = 1 + Math.min(dp[i-1][j], dp[i][j-1]);
                }
            }
          
           // Create a string of size index+1 to store the result
           String res = "";
          
           // Start from the right-most-bottom-most corner and
           // one by one store characters in res[]
           int i = m, j = n;
           while (i > 0 && j > 0)
           {
              // If current character in a[] and b are same,
              // then current character is part of LCS
              if (a.charAt(i-1) == b.charAt(j-1))
              {
                  // Put current character in result
                  res = a.charAt(i-1) + res;
          
                  // reduce values of i, j and indexs
                  i--;
                  j--;
              }
          
              // If not same, then find the larger of two and
              // go in the direction of larger value
              else if (dp[i-1][j] < dp[i][j-1])
              { 
                  res = a.charAt(i-1) + res;
                  i--;  
              }
              else
              {
                  res = b.charAt(j-1) + res; 
                  j--; 
              }
           }
          
           // Copy remaining characters of string 'a'
           while (i > 0)
           {
               res = a.charAt(i-1) + res;
               i--;
           }
          
           // Copy remaining characters of string 'b'
           while (j > 0)
           {
               res = b.charAt(j-1) + res;   
               j--; 
           }
          
           // Print the result
           System.out.println(res);
        }
          
        /* Driver program to test above function */
        public static void main(String args[])
        {
          String a = "apple";
          String b = "pear";
          printSuperSeq(a, b);
           
        }
    }


  4. Задача 2
    Исходное решение заключалось в написании компаратора и сравнении чисел по частному и остатку от деления:
    Algorithm: Compare quotients and reminders
    
    import java.util.Arrays;
    import java.util.Comparator;
    
    public class DictionarySort {
    	public static void main(String[] args) {
    		Integer[] array = new Integer[] { 1, 2, 10, 20, 100, 110 };
    		Arrays.sort(array, new Comparator<Integer>() {
    			@Override
    			public int compare(Integer o1, Integer o2) {
    				// TODO Auto-generated method stub
    				int quotient1 = o1 / 10;
    				int reminder1 = o1 % 10;
    				int quotient2 = o2 / 10;
    				int reminder2 = o2 % 10;
    				if (quotient1 != 0 && quotient2 != 0) {
    					if (quotient1 == quotient2)
    						return 0;
    					int msd1 = 0;
    					int msd2 = 0;
    					if (quotient1 >= 10)
    						msd1 = quotient1 / 10;
    					else
    						msd1 = quotient1;
    					if (quotient2 >= 10)
    						msd2 = quotient2 / 10;
    					else
    						msd2 = quotient2;
    					if (msd1 == msd2)
    						return quotient1 - quotient2;
    					if (msd1 != msd2)
    						return msd1 - msd2;
    
    				}
    
    				if (quotient1 == 0 && quotient2 == 0)
    					return reminder1 - reminder2;
    				if (quotient2 != 0 && quotient1 == 0) {
    					while (quotient2 >= 10)
    						quotient2 /= 10;
    					return reminder1 - quotient2;
    				}
    				if (quotient1 != 0 && quotient2 == 0) {
    					while (quotient1 >= 10)
    						quotient1 /= 10;
    					return quotient1 - reminder2;
    				}
    
    				return 1;
    			}
    
    		});
    		System.out.println(Arrays.toString(array));
    	}
    }
    


  5. Задача 3
    Исходное решение:

    public int[] findTwo(int[] a, int[] b) {
    		int sumA = 0, squareSumA = 0;
    		for (int i = 0; i < a.length; i++) {
    			sumA += a[i];
    			squareSumA += a[i] * a[i];
    		}
    		int sumB = 0, squareSumB = 0;
    		for (int i = 0; i < b.length; i++) {
    			sumB += b[i];
    			squareSumB += b[i] * b[i];
    		}
    		int twosum = sumB - sumA;
    		int squareSum = squareSumB - squareSumA;
    		int param1 = 2;
    		int param2 = 2 * twosum;
    		int param3 = twosum * twosum - squareSum;
    		int[] res = new int[2];
    		int sqrtdiff = (int) Math.sqrt(param2 * param2 - 4 * param1 * param3);
    		res[0] = (param2 - sqrtdiff) / (2 * param1);
    		res[1] = (param2 + sqrtdiff) / (2 * param1);
    		return res;
    	}
    


Tags:
Hubs:
+6
Comments 72
Comments Comments 72

Articles

Information

Website
www.spiceit.ru
Registered
Founded
2009
Employees
31–50 employees
Location
Россия