Пока мозг еще не полностью превратился в Оливье, пора заставить его немного поработать.
Новая подборка логических и алгоритмических задач, предлагаемых на собеседованиях в известных IT-компаниях.
В нашу первую новогоднюю подборку вошли вопросы и задания, заданные в Alcatel-Lucent (Nokia).
Мы постарались подобрать задания разного уровня сложности.
На некоторые (а может, и на все) вопросы можно ответить в Интернете, но это не наш путь, верно? Мы приглашаем вас интеллектуально напрячься и попытаться решить данные проблемы самостоятельно.
Вопросы
- Бактерии в пробирке
Логическая задача о размножении бактерий в реторте.
Перевод Логическая задача — 1 бактерия, делясь, заполняет пробирку за минуту.1 бактерия заполнит ее за минуту.
Сколько времени потребуется, чтобы заполнить реторту, если вначале в ней присутствовало 4 бактерии? Каждая бактерия каждую секунду делится на 2 бактерии одинакового размера.
За сколько времени наполнится пробирка, если вначале в ней было 4 бактерии? Каждая бактерия каждую секунду делится на 2 бактерии одинакового размера.
- 25 лошадей
У вас 25 лошадей, за какое минимальное количество забегов вы сможете найти 3 лучших.
Перевод Необходимо определить минимальное количество скачек, при котором среди 25 лошадей можно выявить трех победителей.В одном забеге вы можете загнать 5 лошадей, и у вас нет таймера.
В одном забеге может быть заявлено максимум 5 лошадей; секундомер не предусмотрен.
Задания
- Создайте строку с подмножествами
Даны две строки s1 и s2. Вы создали новую строку s3 так, чтобы она содержала как s1, так и s2 в качестве одной из своих подпоследовательностей, а длина s3 была минимальной.
Перевод Из двух строк s1 и s2 создайте новую строку s3, содержащую s1 и s2 в качестве подмножеств.Пример: яблоко-груша => яблоко.
s3 должен иметь минимальную длину.
Пример: яблоко-груша => яблоко.
- Словарная сортировка чисел
Как вы будете сортировать целые числа по словарю, не преобразовывая их в строки? Например: 1 2 10 20 100 110 => 1 10 100 110 2 20.
Перевод Как бы вы сортировали целые числа в словарном порядке, не приводя их к строке? Пример: 1 2 10 20 100 110 => 1 10 100 110 2 20. - Найти дополнительные элементы в массиве
Даны два целочисленных массива A и B. B содержит те же числа, что и A, за исключением двух дополнительных чисел.
Перевод Даны массивы чисел A и B. Массив B содержит все числа из A + еще 2 числа.Найдите два элемента с минимальной временной и пространственной сложностью.
например: A = {1, 4, 2, 6, 3} Б = {4, 0,7, 6, 3, 2, 1} ответ: 0 7
Предложите алгоритм нахождения этих 2 чисел, оптимальный по быстродействию и объему памяти.
Пример: А = {1, 4, 2, 6, 3} Б = {4, 0,7, 6, 3, 2, 1} Результат: 0 7
Удачи!
Решения
- Вопрос 1 Многие комментаторы ответили правильно – 58 секунд. Можно было прийти к ответу логически, но кто-то решил его логарифмически :)
- вопрос 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 Я рассматривал случай, когда все сильные лошади находятся в одной группе, но их перестановка не меняет общей картины.
- Проблема 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 {
-
Аварийный Запуск Long March 5
19 Oct, 24 -
Украсть-Убить, Записать-Загрузить
19 Oct, 24 -
Lipstick.com — «Желтый» Аналог Digg
19 Oct, 24 -
Рекомендательные Системы: Перепросмотр
19 Oct, 24
