Привет!
Этим постом начинается обзор задачек по алгоритмам, которые крупные 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^{k/2} - C_k^{k/2 -1})*k)$inline$, дополнительной памяти требуется $inline$O(k)$inline$.
При заданных параметрах вызов функции $inline$f(cnt, ind, k, init)$inline$ выведет следующее:
2. Теперь рассмотрим итеративный способ решения этой задачи.
В этом случае идея будет принципиально другой — нужно ввести понятие лексикографического порядка на скобочных последовательностях.
Все правильные скобочные последовательности для одного типа скобок можно упорядочить, учитывая то, что $inline$'('<')'$inline$. Например, для n=6 самой лексикографически младшей последовательностью будет $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$2^n$inline$. Если каждое подмножество представить в виде массива индексов, где $inline$0$inline$ означает, что элемент не входит в множество, а $inline$1 $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$1 < 0$inline$ (это конечно странно, но так надо, и сейчас поймем почему). Например, для $inline$n=4, k=2$inline$ самой младшей и старшей будут последовательности $inline$[1,1,0,0],[0,0,1,1]$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$, здесь не будем описывать доказательство.
В следующем посте будем разбирать задачки на динамику.
Автор: temkahap
