забавные (на мой взгляд) алгоритмические задачи, встречавшиеся на интервью при устройстве на работу, рассказанные друзьями/коллегами... и т.д.
разные по сложности... на скорость... реакцию... и т.д.
Парочка примеров для начала: 😉
Пример: найти среднее значение
Задача
Есть набор R из N разных чисел. Как найти среднее арифметическое всех чисел в наборе? Сколько действий для этого потребуется?
Решение
1. присвоить значение A= 0
2. для всех чисел из набора (i < N) сделать следующее: А = А + Ri
A/N равно среднебму арифметическому чисел из набора R
Количество требуемых действий ~N
Пример: найти минимальное значение
Задача:
Есть набор R из N разных чисел. Как найти минимальное число в наборе? Сколько действий для этого потребуется?
Решение
1. запомнить первое число из набора A= Rо
2. для всех остальных чисел из набора
(0 < i < N) сделать следующее:
если Ri < A ? то A = Ri
A равно минимальному числу из набора R Количество требуемых действий ~N
Теперь начинаем...
Как (быстро) определить является-ли заданное целое число степенью двойки?
Найти повторяющееся число
Набор целых чисел от 1 до 100, распределённых в случайном порядке, содержит 101 элемент. Одно число присутствует дважды.
Как найти это - повторяющееся - число?
Сколько действий для этого потребуется?
Подсказка
Сумма первых 100 чисел от 1 до 100 равна 5050. Таким образом, сложив 101 число из набора, легко найти повторяющееся
Найти медианное значение
Есть набор R из N разных чисел.
Как найти медианное число в наборе?
Сколько действий для этого потребуется?
медиана — это такое число, что половина из элементов набора больше него, а другая половина меньше. Например, для набора чисел 1, 3, 2, 59, 68 медианой будет 3, так как два числа из набора (1 и 2) меньше 3, и два числа из набора (59 и 68) больше 3.
Ханойская башня
Детская игрушка: пирамидка из дисков разного диамета на одной вертикальной оси (стержне).
Даны три стержня. На одном стержне нанизаны диски так, что меньший лежит на большем.
Как перенести пирамиду из дисков на другой стержень?
Условия:
за один ход можно перенести один диск со стержня на стержень
нельзя класть большее кольцо на меньшее.
Сколько действий потребуется если количество дисков 3, 4, 5, N ?
Силуэт города / Skyline
На горизонтальную прямую (ось Х) накидали прямоугольники разной длины и высоты. Нижнее основание прямоугольников лежит на прямой (ось 0х). Прямоугольники могут пересекаться (перекрывать друг друга). Сочините алгоритм "рисования" / формирования силуэта (skyline), образованого прямоугольнками (набор вершин (X, Y) ломаной линии)
City Silhouette / Skyline
Все картинки - на экран!
Набор разных прямоугольников (ориентированых вдоль осей 0X, 0Y) требуется разместить на плосклсти так, чтобы
прямоугольники не пересекали друг друга
отношение длины к ширине общей покрытой прямоугольниками области было бы в заданых пределах (Rmin < L/W < Rmax)
часть общей площади, не покрытая прямоугольниками, была бы минтимальной.
О деревьях
Здесь деревом будем называть (иерархическую) структуру, в которой у каждого узла ("родитель") может быть несколько под-узлов ("детей").
Отдельно стоит упомянуть структуру двоичное (бинарное) дерево. В двоичном дереве каждый узел имеет не более двух "детей".
Общий предок
Даны два узла одного дерева.
Найти их ближайшего общего предка. Оценить сложность (сколько действий потребуется?)
Пример. Для двух синих узлов ближайшим общим предком будет красный узел. Для двух зелёных узлов ближайшим общим предком будет оранжевый узел.
Наследники Чингиз-Хана
Распечатать информацию о всех узлах дерева, соблюдая иерархию. (Пример: дано генеалогическое дерево наследников Чингиз-Хана. Требуется распечатать имена и порядок/уровень наследников)
Решение 1 (рекурсия):
1. напишем вспомогательную функцию для печати информации о "под-узлах/детях" заданного "узла/родителя" с рекурсивным вызовом самой себя:
print_children (parent , level)
{
for each child of a given parent {
print: child-name , level
call print_children(child, level + 1)
}
}
2. для распечатки дерева наследников Чингиз-Хана:
напечатать: Чингиз-Хан, 0
вызвать вспомогательную функцию:
print_children ( Genghis Khan , 1)
Решение 1 изящно, но не всегда хорошо: для очень "глубоких/высоких" деревьев рекурсия может "захлебнуться" (специфика компьютера). Поэтому хорошо-бы найти решение без рекурсии (обойтись циклом).
Попробуйте найти решение 2... 😉
и снова Чингиз-Хан
А теперь вопрос о структуре.
Можно-ли (как?) представить иерархию наследников Чингиз-Хана (произвольное дерево) в виде двоичного дерева?
Напомним: в двоичном дереве каждый узел имеет не более двух под-узлов.
Не просто куча
Часто эффективность алгоритма/решения определяет выбор подходящей структуры данных.
Один из ярких примеров - использование структур MinHeap / MaxHeap.
(англ. heap - куча)
MinHeap / MaxHeap - структура данных типа двоичного дерева, где каждый узел имеет меньший (или больший) приоритет("вес"), чем его (два) под-узла. При этом соотношение приоритетов узлов одного уровня не имеет значения.
В некоторых задачах такие структуры гораздо эффективнее сортированных данных. Heap-структуры незаменимы в задачах с динамически меняющимися наборами данных, где элемент с наименьшим (или наибольшим) приоритетом периодически удаляется. В таких задачах Heap делает только то, что необходимо (исключаются ненужные действия полной сортировки).
Важное свойтво "кучи": её можно хранить как массив (вектор). При этом для каждого узла "кучи" его порядковый номер (id) в массиве и порядковые номера "детей" (под-узлов) связаны просто:
если номер (id) узла в массиве: n,
то номера (id) его под-узлов:
i1 = 2n+1 и i2 = 2n+2
Пример: вариант MinHeap из целых чисел (1..9)
Ниже: MinHeap как массив. Номера узлов в массиве написаны синим цветом.
Восстатовлениe структуры MinHeap / MaxHeap при добавлении нового элемента и/или при удалении корневого элемента (номер 0 в массиве) требует не больше log(N) операций. Здесь N - число элементов в "куче".
Реализация "кучи" и все подробности описаны во многих статьях. (см. Википедия, ищите в Google)
Примеры использования
1. "Уважение к старшим"
Люди приходят в некую организацию (магазин, поликлиника, муниципалитет), где обслуживаются не по порядку прибытия, а по возрасту. Как организовать приём посетителей? - MaxHeap!
2. "Динамическая медиана"
Набор чисел пополняется новыми данными, требуется отслеживать медианное значение "на лету".
Поможет парочка: MinHeap (для чисел больших медианы) и MaxHeap (для чисел меньших медианы). Следите, чтобы число элементов в кучах не отличалось больше, чем на 1. Медиана всегда будет либо вершиной одной из "куч" (большего размера), либо средним обоих вершин (если число элементов в "кучах" одно и то же).
3. "Растворение полимера"
Дана плёнка полимера, в которой макромолекулы разного размера (показатель растворимости) распределены по объему неравномерно. Где-то растворимость высокая, где-то - низкая. На поверхность полимера налили растворитель... Требуется определить распространение фронта растворителя в полимере (развити поверхности).
Разобьём объём полимера на маленькие ячейки так, что в пределах каждой ячейки скорость растворения постоянна. Ячейки при фронте растворителя будем собирать/хранить в MinHeap. "Приоритетом" будет время растворения ячейки. Ячейка на вершине MinHeap считается растворённой. После этого в MinHeap добавляются её нерастворённые "соседи" (оценка времени растворения соседей обновляется). И новая ячейка на вершине (минимальное время растворения) становится растворённой...
Разумеется, время постоянно увеличивается