Главная » Хабрахабр » [Из песочницы] Обзор задач по алгоритмам для собеседований — генерация множеств

[Из песочницы] Обзор задач по алгоритмам для собеседований — генерация множеств

Привет, Хабр!

В первую очередь этот пост предназначается для тех, кто не имеет в своем арсенале опыта олимпиадного программирования, тяжеловесных курсов по типу ШАДа или ЛКШ, в которых тематика алгоритмов разобрана достаточно серьезно, но кто хочет начать подготовку к собеседованиям или же тем, кто хочет освежить свои знания в какой-то то определенной теме. Этим постом начинается обзор задачек по алгоритмам, которые крупные IT-компании (Яндекс, Гугл и тп) так любят давать кандидатам на собеседованиях (если плохо пройти собеседование по алгоритмам, то шансы устроиться на работу в компанию мечты, увы, стремятся к нулю).

При этом нельзя утверждать, что все задачи, которые здесь будут разбираться, обязательно встретятся на собеседовании, однако подходы, с помощью которых такие задачи решаются, в большинстве случаев похожи.

Повествование будет разбито на разные темы, и начнем мы с генерации множеств с определенной структурой.

1. Начнем с баян-баяныча — нужно сгенерировать все правильные скобочные последовательности со скобками одного вида(что такое правильная скобочная последовательность) с количеством скобок, равным k.

Начнем с рекурсивного.
В этом способе предполагается, что мы начинаем перебирать их с пустого списка, после того, как в список дозаписана скобка (открывающая или закрывающая), происходит новый вызов рекурсии и проверка условий. Эту задачу можно решить несколькими способами. Понятно, что необходимо следить за разницей между открывающими скобками и закрывающими (переменная cnt) — нельзя добавить закрывающую скобку в список, если это разница не является положительной, иначе скобочная последовательность перестанет быть правильной. Какие могут быть условия? Вот и все, осталось аккуратно реализовать это в коде.

k = 6 # количество скобок
init = list(np.zeros(k)) # пустой список, куда кладем скобки
cnt = 0 # разница между скобками
ind = 0 # индекс, по которому кладем скобку в список def f(cnt, ind, k, init): # кладем откр. скобку, только если хватает места if (cnt <= k-ind-2): init[ind] = '(' f(cnt+1, ind+1, k, init) # закр. скобку можно положить всегда, если cnt > 0 if cnt > 0: init[ind] = ')' f(cnt-1, ind+1, k, init) # выходим из цикла и печатаем if ind == k: if cnt == 0: print (init)

Сложность этого алгоритма — $inline$O((C_k^ - C_k^{k/2 -1})*k)$inline$, дополнительной памяти требуется $inline$O(k)$inline$.

При заданных параметрах вызов функции $inline$f(cnt, ind, k, init)$inline$ выведет следующее:

2. Теперь рассмотрим итеративный способ решения этой задачи.

В этом случае идея будет принципиально другой — нужно ввести понятие лексикографического порядка на скобочных последовательностях.

Например, для n=6 самой лексикографически младшей последовательностью будет $inline$((()))$inline$, а самой старшей $inline$()()()$inline$. Все правильные скобочные последовательности для одного типа скобок можно упорядочить, учитывая то, что $inline$'('<')'$inline$.

После их перестановки сделать суффикс, который просмотрен, самым лексикографическим младшим — для этого нужно разницу между количеством скобок на каждом шаге. Для того, чтобы получить следующую лексикографическую последовательность, нужно найти самую правую открывающуюся скобку, перед которой стоит закрывающаяся, такую, что при их перестановке друг с другом скобочная последовательность останется правильной.

Реализуем это в коде. На мой взгляд, этот подход чуть-чуть муторнее рекурсивного, однако его можно использовать для решения других задач на генерацию множеств.

# количество скобок, должно быть четное
n = 6
arr = ['(' for _ in range(n//2)] + [')' for _ in range(n//2)] def f(n, arr): # печатаем нулевую последовательность print (arr) while True: ind = n-1 cnt = 0 # находим откр. скобку, которую можно заменить while ind>=0: if arr[ind] == ')': cnt -= 1 if arr[ind] == '(': cnt += 1 if cnt < 0 and arr[ind] =='(': break ind -= 1 # если не нашли, то алгоритм заканчивает работу if ind < 0: break # заменяем на закр. скобку arr[ind] = ')' # заменяем на самую лексикографическую минимальную for i in range(ind+1,n): if i <= (n-ind+cnt)/2 +ind: arr[i] = '(' else: arr[i] = ')' print (arr)

Сложность этого алгоритма такая же, как и для прошлого способа.

Кстати, есть несложный способ, который покажет, что как минимум количество сгенерированных скобочных последовательностей точно такое, какое нужно — их количество для данного n/2 должно совпадать с числами Каталана.

Работает!

Отлично, со скобками пока все, теперь перейдем к генерации подмножеств, начнем с простой задачки.

3. Дан упорядоченный массив по возрастанию с числами от $inline$0$inline$ до $inline$n-1$inline$, требуется сгенерировать все его подмножества.

Если каждое подмножество представить в виде массива индексов, где $inline$0$inline$ означает, что элемент не входит в множество, а $inline$1 $inline$ — что входит, тогда генерация всех таких массивов будет являться генерацией всех подмножеств. Заметим, что количество подмножеств такого множества равно в точности $inline$2^n$inline$.

То есть для того, чтобы решить эту задачу, необходимо реализовать прибавление единицы к двоичному числу. Если рассмотреть побитовое представление чисел от 0 до $inline$2^n - 1$inline$, то они будут задавать искомые подмножества. Начинаем со всех нулей и заканчиваем массивом, в котором все единицы.

n = 3
B = np.zeros(n+1) # массив B берем на 1 длиннее (для удобства выхода из цикла)
a = np.array(list(range(n))) # изначальный массив def f(B, n, a): # начинаем цикл while B[0] == 0: ind = n # ищем самый правый ноль while B[ind] == 1: ind -= 1 # заменяем на 1 B[ind] = 1 # на все остальное пишем нули B[(ind+1):] = 0 print (a[B[1:].astype('bool')])

Сложность этого алгоритма — $inline$O(n*2^n)$inline$, по памяти — $inline$O(n)$inline$.
Посмотрим на вывод.

Теперь чуть-чуть усложним предыдущую задачу.

4. Дан упорядоченный массив по возрастанию с числами от $inline$0$inline$ до $inline$n-1$inline$, требуется сгенерировать все его $inline$k$inline$-элементные подмножества — решить итеративным способом.

Решим первым. Как следует из названия, эту задачу можно решать двумя способами — итеративно и рекурсивно. Заметим, что по формулировке эта задача похожа на предыдущую и решать ее можно с помощью примерно такой же методики — взять изначальный массив с $inline$k$inline$ единицами и $inline$n-k$inline$ нулями и последовательно перебрать все варианты таких последовательностей длины $inline$n.$inline$

Нам нужно перебрать все $inline$k$inline$-значные наборы чисел от $inline$0$inline$ до $inline$n-1$inline$. Однако требуются небольшие модификации. Необходимо понять, как именно нужно перебирать подмножества — в данном случае можно ввести понятие лексикографического порядка на таких множествах.

Например, для $inline$n=4, k=2$inline$ самой младшей и старшей будут последовательности $inline$[1,1,0,0],[0,0,1,1]$inline$. Также упорядочи такую последовательность по кодам символов: $inline$1 < 0$inline$ (это конечно странно, но так надо, и сейчас поймем почему).

Код следующий: Все, осталось понять, как именно необходимо описать переход от одной последовательности к другой — тут все просто, если меняем $inline$1$inline$ на $inline$0$inline$, то слева пишем лексикографически минимальное с учетом сохранения условия на $inline$k$inline$.

n = 5
k = 3
a = np.array(list(range(n))) # начальный список первого k - элементного подмножества
init = [1 for _ in range(k)] + [0 for _ in range(n-k)] def f(a, n, k, init): # печатаем нулевое k-элементное множество print (a[a[init].astype('bool')]) while True: unit_cnt = 0 cur_ind = 0 # находим нулевой индекс, который будем менять на 1 while (cur_ind < n) and (init[cur_ind]==1 or unit_cnt==0): if init[cur_ind] == 1: unit_cnt += 1 cur_ind += 1 # если не нашли и дошли до конца - то все сгенерировали if cur_ind == n: break # меняем init[cur_ind] = 1 # заполняем слева лекс. наим. способом for i in range(cur_ind): if i < unit_cnt-1: init[i] = 1 else: init[i] = 0 print (a[a[init].astype('bool')])

Пример работы:

Сложность этого алгоритма — $inline$O(C_n^k * n)$inline$, по памяти — $inline$O(n)$inline$.

5. Дан упорядоченный массив по возрастанию с числами от $inline$0$inline$ до $inline$n-1$inline$, требуется сгенерировать все его $inline$k$inline$-элементные подмножества- решить рекурсивно.

Идея простая — на этот раз обойдемся без описания, смотрите код. Теперь попробуем рекурсию.

n = 5
a = np.array(list(range(n)))
ind = 0 # число, в котором лежит количество элементов массива
num = 0 # индекс, с которого начинается новый вызов функции
k = 3
sub = list(-np.ones(k)) # подмножество def f(n, a, num, ind, k, sub): # если уже k единиц есть, то печатем и выходим if ind == k: print (sub) else: for i in range(n - num): # вызываем рекурсию, только если можем добрать до k единиц if (n - num - i >= k - ind): # кладем в этот индекс элемент sub[ind] = a[num + i] # обратите внимание на аргументы f(n, a, num+1+i, ind+1, k, sub)

Пример работы:

Сложность такая же, как и у прошлого способа.

6. Дан упорядоченный массив по возрастанию с числами от 0 до n-1, требуется сгенерировать все его перестановки.

Будем решать рекурсией. Вроде тоже баян, но тем не менее давайте решим. Изначально он нулевой, если на $inline$i$inline$-ом месте элемента стоит единица, то значит, что элемент $inline$i$inline$ уже есть в перестановке. Идея похожа на предыдущую задачу, где у нас есть вспомогательный список. Сказано — сделано:

a = np.array(range(3))
n = a.shape[0] ind_mark = np.zeros(n) # массив индексов
perm = -np.ones(n) # уже заполненная часть перестановки def f(ind_mark, perm, ind, n): if ind == n: print (perm) else: for i in range(n): if not ind_mark[i]: # кладем в перестановку элемент ind_mark[i] = 1 # заполняем индекс perm[ind] = i f(ind_mark, perm, ind+1, n) # важный момент - нужно занулить индекс ind_mark[i] = 0

Пример работы:

Сложность этого алгоритма — $inline$O(n^2 *n!)$inline$, по памяти — $inline$O(n).$inline$

Если в двух словах, то это набор последовательностей одной длины, где каждая последовательность отличается от своих соседей в одном разряде. Теперь рассмотрим две очень интересных задачки на коды Грея.

7. Сгенерировать все двумерные коды Грея длины n.

Заметим, что количество таких последовательностей равно $inline$2^n$inline$. Идея решения этой задачи классная, но имхо если не знать решения, то очень сложно додуматься.

Пусть мы сгенерировали какую-то часть таких последовательностей. Будем решать итеративно. Если мы продублируем такой список и запишем его в обратном порядке, то получится что последняя последовательность в первом списке совпадает с первой последовательностью во втором списке, предпоследняя совпадает со второй и т.д. Пусть они лежат в каком-то списке. Соединим эти списки в один.

Правильно, поставить в соответствующих местах одну единицу в элементы второго списка, чтобы получить коды Грея. Что необходимо сделать, чтобы все последовательности в нем отличались друг от друга в одном разряде?

Это сложно воспринять, изобразим итерации этого алгоритма.

Код следующий:

n = 3
init = [list(np.zeros(n))] def f(n, init): for i in range(n): for j in range(2**i): init.append(list(init[2**i - j - 1])) init[-1][i] = 1.0 return init

Сложность этой задачи — $inline$O(n*2^n)$inline$, по памяти такая же.

Теперь усложним задачу.

8. Сгенерировать все k-мерные коды Грея длины n.

Однако тем красивым способом, которым была решена прошлая задача, эту задачу решить не получится, здесь необходимо в правильном порядке научиться перебирать такие последовательности. Понятно, что прошлая задача является лишь частным случаем этой задачи. Изначально в последней строчке стоят единицы, а в остальных стоят нули. Заведем двумерный массив $inline$k*n$inline$. Здесь $inline$1$inline$ и $inline$-1$inline$ по сути отличаются друг от друга направлением: $inline$1$inline$ указывает вверх, $inline$-1$inline$ указывает вниз. При этом в матрице также могут встречаться и $inline$-1$inline$. Важно — в каждом столбике в любой момент времени может быть только одна $inline$1$inline$ или $inline$-1$inline$, а остальные числа будут нулями.

Начинаем с конца двигать элемент вверх. Теперь поймем, каким именно образом можно перебрать эти последовательности, чтобы получались коды Грея.

Записываем получившуюся последовательность. Следующим шагом мы упремся в потолок. Искать его нужна справа налево, и если мы нашли такой столбец, который можно двигать, то у всех столбцов, с которыми мы не могли работать, стрелочки поменяются в противоположном направлении, чтобы их опять можно было двигать. После того, как стрелка уперлась в потолок, необходимо начать работать со следующим столбцом.

Двигаем его до тех пор пока он не упрется вниз. Теперь можно двигать первый столбец вниз. И так далее, до тех пор пока все стрелочки не будут уперты в пол или потолок и не будет столбцов, которые можно двигать.

Однако, в рамках экономии памяти, будет решать эту задачу с помощью двух одномерных массивов длины $inline$n$inline$ — в одном массиве будут лежать сами элементы последовательности, а в другом их направления (стрелочки).

n,k = 3,3
arr = np.zeros(n)
direction = np.ones(n) # один указывает вверх, ноль указывает вниз def k_dim_gray(n,k): # печатаем нулевую последовательность print (arr) while True: ind = n-1 while ind >= 0: # условие на нахождение столбца, который можно двигать if (arr[ind] == 0 and direction[ind] == 0) or (arr[ind] == k-1 and direction[ind] == 1): direction[ind] = (direction[ind]+1)%2 else: break ind -= 1 # если не нашли такого столбца, то алгоритм закончил работу if ind < 0: break # либо двигаем на 1 вперед, либо на 1 назад arr[ind] += direction[ind]*2 - 1 print (arr)

Пример работы:

Сложность алгоритма — $inline$O(n*k^n)$inline$, по памяти — $inline$O(n).$inline$
Корректность данного алгоритма доказывается индукцией по $n$, здесь не будем описывать доказательство.

В следующем посте будем разбирать задачки на динамику.


Оставить комментарий

Ваш email нигде не будет показан
Обязательные для заполнения поля помечены *

*

x

Ещё Hi-Tech Интересное!

[Перевод] Введение в ptrace или инъекция кода в sshd ради веселья

Конечно, это несколько искусственная задача, так как есть множество других, более эффективных, способов достичь желаемого (и с гораздо меньшей вероятностью получить SEGV), однако, мне показалось клёвым сделать именно так. Цель, которой я задался, была весьма проста: узнать введённый в sshd ...

Дайджест свежих материалов из мира фронтенда за последнюю неделю №339 (12 — 18 ноября 2018)

Предлагаем вашему вниманию подборку с ссылками на новые материалы из области фронтенда и около него.     Медиа    |    Веб-разработка    |    CSS    |    Javascript    |    Браузеры    |    Занимательное Медиа • Подкаст «Frontend Weekend» #79 – Олег Поляков об основании CodeDojo и о том, как это стало основным местом работы• Подкаст «Пятиминутка React» ...