Пока мозг ещё не окончательно превратился в оливье, самое время немного заставить его поработать. Новая подборка логических и алгоритмических задач, предлагаемых на собеседованиях в известные IT-компании.
В нашу первую в новом году подборку попали вопросы и задачи, задаваемые в Alcatel-Lucent (Nokia).
Задачи мы постарись подобрать с различным уровнем сложности. На некоторые (а, может быть, и на все) вопросы можно найти ответ на просторах интернета, но это ведь не наш путь, верно?
Предлагаем интеллектуально размяться и попробовать самостоятельно решить приведённые задачи.
Ответы будут даны в течение следующей недели — успейте решить. Удачи!
В нашу первую в новом году подборку попали вопросы и задачи, задаваемые в Alcatel-Lucent (Nokia).
Задачи мы постарись подобрать с различным уровнем сложности. На некоторые (а, может быть, и на все) вопросы можно найти ответ на просторах интернета, но это ведь не наш путь, верно?
Предлагаем интеллектуально размяться и попробовать самостоятельно решить приведённые задачи.
Вопросы
- Бактерия в пробирке
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 бактерии такого же размера ежесекундно.
- 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 лошадей, секундомер не предусмотрен.
Задачи
- Построить строку с подмножествами
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
- Словарная сортировка чисел
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.
- Найти добавочные элементы в массиве
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Многие комментаторы ответили правильно — 58 секунд. Можно было прийти к ответу логическим путём, а кто-то решил логарифмически :)
- Вопрос 2Многие тоже нашли верное решение. Ответ — 7 забегов.
Пронумеруем лошадей. Первые пять забегов:
1. 1 2 345
2. 6 7 8910
3. 11 12 131415
4. 16 17 181920
5. 21 22 232425
Выбыли 10 лошадей, поскольку они не могут претендовать на место в тройке лидеров.
В шестом забеге выявим абсолютного лидера:
6. 1 6 111621
Теперь картина следующая:
1 2 345
6 78910
1112131415
1617181920
2122232425
Выбыло ещё 10 лошадей — все лошади забегов, чьи лидеры пришли 4 и 5, поскольку они не могут претендовать на призовые места, лошади третьей группы (поскольку их лидер занял третье место и они могут расчитывать на 4+), и третья лошадь второй группы, потому что тоже может расчитывать только на 4+ место, а также лошадь занявшая 1-ое место как абсолютный лидер.
В седьмом забеге выявляем первую пару сильнейших — они из займут почётные места в тройке лидеров:
7. 2 36711
Я рассмотрел случай, когда все сильные лошади в одной группе, но перестановка их общей картины не меняет.
- Задача 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); } }
- Задача 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)); } }
- Задача 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; }