Пока мозг ещё не окончательно превратился в оливье, самое время немного заставить его поработать. Новая подборка логических и алгоритмических задач, предлагаемых на собеседованиях в известные 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
Ответы будут даны в течение следующей недели — успейте решить. Удачи!
Nick_mentat
понравились задачки)
7
найти самую длинную совпдающую подпоследовательность второго слова в первом и
приписать недостающие буквы с обоих сторон от крайних символов подпоследовавтельности
домножить все числа до самого старшего разряда в наборе. Запомнить кого на сколько помножили. Отсортировать по значению. Делить на запомненные ранее множители
вычесть B\A — по одному выкидывая элементы. Искать совпадения перебором от последнего выкинутого элемента, к примеру. Даст максимально быстрый результат если оба входных массива отсортированы (ну мало ли)
kardan2
Ваше решение 1-задачи вызывает больше вопросов, чем дает ответы. Во-первых, поиск максимальной подпоследовательности — это не тривиальная задача. Даже найдя её, нужно ещё правильно расставить значения по бокам. В -третьих, что будет, если одна и та же максимальная подпоследовательность будет встречаться во втором слове несколько раз?
По описанному вами невозможно определить даже алгоритмическую сложность.
Ваше решение как минимум неполное, как максимум неверное. Неполнота не дают мне возможность построить контрпример.
shadson
Чего-то я как не кручу, не получается 7 (если брать худший случай, когда топ5 лошадей набивается в одну пятёрку), выходит 8 по любому.
(6) — первая из каждой пятерки.
Получаем самую быструю + 2 кандидата (6.1 + 6.2) + выпадают все лошади из пятёрок тех, кто на 3, 4 и 5 местах.
Итого остаётся получить 2х самых быстрых из 6 лошадей (2 кандидата + места 2/3 из пятерок победителя и второго места), из которых нам только известно только про двух лошадей что одна быстрее другой (безотносительно остальных 4х). Еще 2 забега потому, имхо…
kardan2
На последний (7-й) забег неопределенность остается только у 5-ти лошадей. Из первой пятёрки лидер = 100% лучший среди всех, его в расчет не берем. Остается 2 и 3 место из первой пятёрки, 1 и 2 место из второй пятерки, и только первое место из 3-й пятёрки. И это ровно на 1 забег.
shadson
Таки да, 7. Пятница, мозги сплавились уже.
abpraller
Вопрос 1 — 58 сек?
LonelyCruiser
Во второй задаче перевод неправильный, там нужно определить минимальное кол-во забегов.
reci Автор
Верно, спасибо
vshmidt
apple pear => applear
мне одному кажется что в applear нет подстроки pear?
reci Автор
applear
Подмножеством не обязательно является цельная подстрока.
qw1
И опять неточный перевод.
{a,p,l,e} — подмножество {a,e,l,p}? Да, ведь множество — набор без какого-либо порядка.
Тогда, задача тривиальна — выбираем все различные буквы из первого слова и из второго, объединяем эти множества, вот и ответ.
В оригинале речь шла о подпоследовательности.
reci Автор
Верно, subsequences = подпоследовательности. Но тогда пример должен быть вроде: apple, pear => applepear, что тоже тривиально.
Я счёл, что пример, взятый из оригинала, более корректно иллюстрирует условие, поэтому перевёл соответствующе.
qw1
Нетривиально, если учесть, что требуется не любая строка, а минимальной длины.
reci Автор
Можете предложить решение для подпоследовательностей?
qw1
Это очень похоже на задачу поиска наибольшей общей подпоследовательности из двух строк, которая решается динамическим программированием за
O(NM), N=length(s1), M=length(s2)Нужно рассмотреть ф-цию F(a,b), которая решает задачу на урезанных входных строках длины a и b, а затем вычислять F(a,b) для всех a=1..N, b=1..M, опираясь на предыдущие вычисленные F
Обычно в таких задачах даже можно уложиться по памяти не в O(N*M), а в O(max(N,M)), т.к. рекуррентная формула обращается только к предыдущей строке матрицы.
На собеседовании, наверное, я бы записал рекуррентное соотношение минут за 15-30, но сейчас думать лень )))
Beyka
вопрос 1) 58 сек
вопрос 2) 6 забегов
reci Автор
Есть ошибки :)
Beyka
В 1 вопросе бактерия делением звонит пробирку за 60 секунд на 2^60. 4 бактерии заполнят: 2^60/4 и от этого числа взять логарифм по основанию 2
Задача 2) 25 лошадей делим на 5 лошадей в забеге и получаем 5 победителей, потом ещё 1 забег. Правда в этом случае не сработает если все хорошие лошади в одной пятерке.
Задача 2 вариант 2) из каждого забега брать по 3 лошади и формировать пятерки из них итого 12 забегов.
Nick_mentat
По 3 из всех не обязательно брать. Достаточно отсортировать забеги по забегу лидеров первых пяти гонок, а затем сравнить в одном забеге 1.2, 1.3, 2.1, 2.2 и 3.1 (место_лидера_пятёрки_в_6_забеге.место_лошади_в_забеге_с_этим_лидером_из_первых_5_забегов).
Ksoo
Таймера нет, сортировать не получится.
Nick_mentat
Получится. Есть места в забеге. С таймером, пончтное дело, и пяти было бы достаточно…
Ksoo
Не понятно написали, после комментария уже понял, что надо устроить отдельный забег лидеров, и на основании него, произвести сортировку.
shadson
степени, логарифмы — как сложно-то…
Состояния «в пробирке уже 4 бактерии» исходная особь достигает за 2 секунды (1->2->4), итого 60-2=58.
Bunny_74
12 забегов, кмк
3 забега по 5 — выбираем по 3 лучших из каждого — осталось 9 лошадок
2 забега 5+4 — выбираем по 3 лучших — осталось 6
1 забег из 5 лошадей — 3 лучших идут в следующий забег
1 забег из 4х лошадей (3 из предыдущего и +1 отдыхающая лошадь) — по результатам определяем 3 быстрейших лошади
лошадки, конечно, должны бегать стабильно по своему максимальному результату и не уставать :)
Gromo
Теоретический минимум — 5 забегов, даже если бы был таймер, чтобы протестировать всех лошадей. Максимум при последовательном переборе — 11, если из каждого забега оставлять тройку лидеров и заменять последних двух лошадей свежими: 5-2-2-2-2-2-2-2-2-2-2. У меня получилось минимум 9 забегов.
Gromo
Всё же можно уложиться в 7 забегов — 5 основных, 6й — между лидерами, 7-й между 5ю оставшимися лошадьми, как описано в комменте Nick_mentat
kardan2
Мои решения.
1) Подобная задача у нас была ещё в школе, классе примерно 8-м. И даже тогда она легко решалась.
2) Первое решение — это разбить всех на 5-ки. Пустить 5 забегов (узнать места внутри пятерки). Выбираем 5 лидеров. Затем пока не наберем нужное количество поступаем так: устраиваем забег, выбираем первую лошадь, и на её место ставим следующую лошадь из её пятерки. Всего 8 забегов. Причем это общий подход, на любое количество лошадей.
А второе решение (7 забегов) пришло, когда а нарисовал на листке положение лошадей после 6-го забега и вычеркнул тех, кто не может претендовать на тройку.
3) Вот это уже сложная задача, решение приличное я не нашел. Она одна стоит больше всех остальных вместе взятых. Даже не утерпел и посмотрел решение Nick_mentat, но к нему у меня много вопросов.
4) Тут 2 варианта. Если разрешено использовать дополнительные ячейки, тогда нужно приводить путем умножение на 10^n к "одной весовой категории", сохранить для каждого числа получившиеся значение, которые уже и сравниваются. При этом, в случае равенства, нужно сравнивать исходные числа (чтобы упорядочить 10 и 100). Этот вариант более быстрый, за счет того, что операция приведение (а она не дешевая) выполняется 1 раз.
Второй вариант — это написание КОМПОРАТОРА, который принимает на вход 2 числа, и сравнивает их. А дальше можно вызывать стандартную функцию сортировки. Это не требует лишней памяти, но требует приведения чисел каждый раз при сравнении.
5) Самый простой способ — это вычислить сумму чисел обоих массивов и произведение чисел (на 0 не умножаем) обоих массивов. Тогда мы получим произведение и сумму искомых чисел. Эти 2 уравнения приводятся к полиному второй степени, и элементарно находятся. Но тут несколько моментов. Первоначально нужно посчитать количество нулей в обоих массивах, если оно разное, то находить произведение смысла нет. С суммой тоже вопросов нет, достаточно взять тип целого, который больше используемых чисел. Например если массивы заполнены 32-битными значениями, то использовать надо 64-битное. С умножением сложнее, умножение пару сотен чисел переполняет даже самые большие типы целого. Значит для умножения нужно использовать числа с плавающей точкой. Да, там будет потеря точности, но старшие биты должны вытянуть (обеспечить) правильное значение.
Насчет задачи 3). Лучшее, что я придумал — это полный перебор, когда первое слово перемешивается со вторым (с сохранением последовательности внутри), для каждого варианта ищем букву из первого слова, которая оказалась равна рядом стоящей букве из второго слова (т.е. эту букву можно выкинуть). Считаем количество таких букв, запоминаем комбинацию, когда их число максимально. Такой алгоритм дает гарантированный результат, но имеет очень плохую алгоритмическую сложность, что-то вроде O(n^m).
kardan2
Прошу прощения. Нумеровал задания по порядку. 1) и 2) — это вопросы. 3), 4), 5) — это задачи 1, 2 и 3.
kardan2
Уточнение к решениям
Задача с подмножествами. Здесь очевидно, нужно работать с укороченными строками, выбросив те буквы из первого слова, которые не входят во второе, и буквы из второго слова, которых нет в первом. Остатки от 2-х слов уже пытаемся перебором «перемешать» в строку минимальной длины. А уже потом (и это тривиально) добавить выкинутые буквы. В худшем варианте (когда буквы нельзя выкинуть) сложность остается той же, но зато существенно сокращает сложность, когда у обоих слов всего 1 буква общая.
kardan2
Задача с подпоследовательностями. Решение.
1) Первым делом находим общие буквы в обоих словах. Как это сделать (через хэш, массив или полным поиском) — не принципиально. Общие буквы у них — ACD.
2) Для обоих слов создаем урезанные варианты (оставляем только общие буквы), и при этом запоминаем соответствие. Получаются слова ACAD и ADDCA, и соответствие [3,4,6,7] и [2,5,7,8,10].
3) Создаем массив размером произведения длин сокращенных слов, в нашем случае 4 * 5.
Выбираем слово ACAD проходим по нему с конца (начиная с буквы D). Для каждой такой буквы из первого слова проходим по второму в обратном порядке, и ищем совпадающие буквы. Когда буквы совпали, делаем проход по первому слову в правильном порядке, начиная с буквы справа от текущей (слева от D в нашем примере ничего нет, поэтому ничего не делаем) и смотрим что стоит в массиве для этой буквы и её положения. Находим максимальное значение, прибавляем к нем 1 и сохраняем в массиве в текущем положении и для всех леволежащих, пока не найдем число большее. И того у нас получается тройной цикл (по первому слову-по второму слову-по первому слову).
В чем смысл массива — значение в ячейке x,y говорит нам о максимальной подпоследовательности которая бы начиналась с x-места первом слове, y-места второго слова.
Чтобы было понятно приведу результаты обработки ACAD и ADDCA.
A [3 1 1 1 1]
C [2 2 2 2 0]
A [2 2 1 1 1]
D [1 1 1 0 0]
максимальное значение — 3. Теперь мы имеем в наличии длину искомой последовательности, и букву (положение) в первом слове, с которой она начинается.
4) Используя всё это и массив находим узлы (положение букв в обоих словах) за 1 проход.
В нашем случае A(1,1) C(2,4) A(3,5).
5) Возвращаемся к исходным словам, переводим по таблице соответствия наши узлы.
OPACKADOS и MABUDYDCMAB => A(3,2) C(4,8) A(6,10). После чего разбиваем наши слова на участки (между узлов, узлы не входят ). Берем первый участок первого слова, прибавляем первый участов второго слова и прибавляем сам узел, и так далее…
OP — M — A…
Вычислительная сложность что-то типа между O(n*n+m*n) в случае, если каждая буква встречается не чаще 1 раза и O(n*n*m) в случае, если все буквы одинаковы. Т.е. сложность между квадратичной и кубической.
Ура товарищи!!!
roces
В английской версии вопросов похоже много ошибок. Вы сами составляли?
reci Автор
Нет, оригинальные задачи приведены без изменений, если это не влияет на смысл.
yizraor
Спасибо за задачки :)
Почти все не так просты, как кажутся на первый взгляд.
Нетрудно понять, что если бактерий на старте 1, то через две секунды будет их 4.
Значит, для заполнения пробирки от 4-х бактерий надо на 2 секунды меньше, т.е. 60 — 2 = 58.
Впрочем, можно показать это и математически.
Количество бактерий в момент времени “t”, если начинать с 1-й штуки, 0?t:
1; 2; 4; 8; 16; … 2^t; …
Если взять объем пробирки (кол-во умещающихся бактерий) за "V", и время заполнения в секундах за "t", то имеем:
V = 2^t
Количество бактерий в момент времени “x”, если начинать с 4-х штук, 0?x:
4; 8; 16; 32; 64; … 2^(x + 2); …
V = 2^(x + 2)
Поскольку объём пробирки один и тот же, то:
2^t = 2^(x + 2)
t = x + 2
Зная, что t = 60 (пробирка от 1-й бактерии заполняется за минуту), имеем:
60 = x + 2
x = 58
Ответ: пробирка с 4-мя бактериями заполнится за 58 секунд.
kardan2
Давайте уточним, что обработка слов ABCE и ACDE должна на выходе дать единственно возможный вариант ABCDE. Во всяком случае я понимаю условие задачи именно так.
alexeykuzmin0
Наконец-то интересные, не очень баянистые задачи, спасибо!
LlessSpb
Попробую и я свои силы.
sparrowhome
Задача 1 не особо интересна, т.к. решение тревиально.
Задача 2 решения, которые предлагаются мне не до конца ясны, почему то все считают, что устроив 5 забегов для разных наборов лошадей мы каким то образом сможем получить корреляцию между лошадьми из разных забегов, но никто не гарантирует что первая пятерка лошадей, например, не была лучше всех остальных, таким образом на мой взгляд правильное решение такое:
Всего 11 забегов.
Задача 3 не понимаю что требуется, пример ужасно путает.
Задача 4 думаю нужно привести все числа к одному разряду и дальше отсортировать их, затем сравнить для одинаковых исходные и отсрортивать их.
Задача 5 не хочется повторять решения предложенные выше, поэтому массив B делим пополам и начинаем для каждого элемента из выбранной части массива B выполнят проверку на наличие его в массиве А, как только нашли то удаляем его из массива А и В, если нет печатаем его. Если проверили первую половину полностью то повторяем алгоритм рекурсивно для второй части массива В.
kardan2
В последней задачи деление второго массива на части ничего не дает по сравнению с последовательным проходов, вам все равно в худшем случае надо будет проверить все элементы. Вероятность досрочного нахождения элементы такая же. Кроме того, вы меняете данные в массивах (портите их), а не факт что это разрешено. Для правильной работы вам придется сделать копии массивов, а это ДОПОЛНИТЕЛЬНАЯ ПАМЯТЬ.
Задача с конями решается быстрее.
sparrowhome
Я не согласен с предлагаемыми выше решениями задачи про коней, по уже описанной причине (нет гарантии что все самые быстрые лошади не в первой пятерке, например).
Все варианты решения тут уверяют ю что мы можем сказать лошадь 3 из забега 1 точно хуже лошади 1 из забега 2 или 3, потому что нет секундомера, поэтому мы не можем сравнивать лидеров независимы забегов, или я не прав?
kardan2
Варианта с «все самые быстрые лошади не в первой пятерке» отрабатывается корректно. Лидер первой пятерки попадает автоматом в топ после 6-го забега. А далее в 7 забеге участвуют 2 другие лошади из первой пятерки. Они в этом забеге соревнуются с лидерами второй и третей пятерки + второй лошади второй пятерки. Если они выигрывают (приходят первой и второй) 7 забег, то они и попадают в топ.
Не можем, однозначно не можем, но мы можем их прогнать вместе в 7-м забеге и узнать точно нужные места. Заметьте, что мы оставляем 3 лошади из первой пятерки, 2 лошади из второй, и 1 лошадь из третьей. Всего 6 штук, но одна из них гарантированно лидер.
braingeek
Я не совсем понимаю, с чего вы взяли по 7 забегов в задаче о конячках. Я полностью согласен о первых 6 забегах, о нахождении самой быстрой, однако у меня возникает вопрос: почему вы с каждой пятёрки выкидываете аж по 3 лошади (что уже в корне не верно, так как в любой из пятёрок может находится та самая троица). А ещё утверждение рода «лошадь №3 из первого забега 100% медленне лошади №2 из четвёртого забега».
Прошу ответить, почему некоторые нашли 10/11 забегов минимум, может я чего упустил.
Далее мы выбираем из каждой пятёрки по 1 месту и прогоняем шестым забегом, определяя топ-1. Теперь у нас 14 лошадок и 6 забегов, хорошо (Прошу заметить, господа, 14!).
Каков у нас выбор? Делить группы на 3 и 4 смысла нет, это увеличение кол-ва забегов, поэтому делим по максимуму. 5,5 и 4 лошади на забег, соответственно.
Делаем 7,8 и 9 забеги, определяя (внимание) по 2 самых быстрых лошади на каждую группу (так как мест осталось 2, а остальные снова не помещаются). Итого имеем на 9 забегов группы: 2-2-2 (выкинули 3-3-0, соответственно).
У нас 6 лошадей. Теперь делим на группы по 3 особи. 10 и 11 забеги: находим по самой быстрой лошадке на каждую группу.
12 забегом забираем этих двух лошадок и сравниваем, получая топ-2 и топ-3 места.
kardan2
Итого остается при беглом рассмотрении всего 9 лошадок (по 3 лошади из 3-х пятёрок). При более подробном рассмотрении, оказывается, что лошадь, которая пришла в прошлый раз первой — лучшая среди всех. И её можно исключать сразу, а далее нужно просто понять кто займет 2 и 3 место. Из оставшихся 8-ми лошадок можно выкинуть ещё 3. Остается как раз 5 для выявления серебра и бронзы.
braingeek
Можно ли уточнить, почему осталось 9 лошадок (а точнее, почему вы взяли всего 3 пятёрки)? В каждой пятёрки есть по 3 лидера и по 2 проигравших лошади (после 5 первых забегов). Мы сразу получаем 15 лошадей. Отбирая топ-1 с каждой группы и устраивая забег, мы получаем победителя, а тех лошадей возвращаем обратно, потому что мы не уверены, что, например, вторая лошадь с пятой группы (которую вы, как я понял, уже откинули) медленнее первой лошади с любой иной группы. По такой же аналогии мы не можем быть уверены, что третья лошадь с какой-то группы обязательно медленнее любой другой лошади с 1/2 места но с другой группы. Поэтому я не вижу вообще варианта с 9 лошадками.
Заодно, пользуясь случаем, исправлю себя
s_suhanov
Шестой забег — это забег лидеров предыдущих пяти пятерок. И те лидеры, которые в шестом забеге прибежали на 4 и 5 месте — уже не попадают в общую лучшую тройку. А значит и лошади из их забегов тоже (они ведь еще хуже).
Объясню на примере: допустим в шестом забеге лошади прибежали в таком порядке:
Таким образом ВСЕ лошади из забегов №1 и №4 точно не могут входить в общую лучшую тройку. Ведь лидеры забегов №2, №3 и №5 — гарантированно быстрее.
braingeek
Всё верно, теперь до меня дошло, спасибо)
Как-то упустил момент, что можно откинуть сразу 2 группы, хоть и нарисовал перед глазами задачу.