🐍💼 Подготовка к собеседованию по Python: решаем 5 интересных задач

Проверяем двоичные деревья на симметричность, вычисляем расстояние Дамерау-Левенштейна и оцениваем сложность алгоритмов.

Задание 1

Напишите программу, которая принимает на вход целое число, и возвращает целое число, цифры в котором переставлены в обратном порядке. Например, если введено число 561, программа должна вернуть 165, а если -578, то -875. Решите задачу двумя способами – с использованием методов строк и без. Какое решение более эффективно?

Решение

При использовании методов строк задача решается максимально просто:

Для решения без использования строк нужно запустить цикл while, который будет выполняться до тех пор, пока num_remaining не станет равным нулю. В каждой итерации цикла происходит следующее:

• Умножаем result на 10 и прибавляем к нему остаток от деления num_remaining на 10 (таким образом, последняя цифра числа num_remaining становится первой цифрой числа result).
• Затем num_remaining делится нацело на 10, чтобы удалить последнюю цифру.
• После окончания цикла возвращается значение result, причем если исходное число num было отрицательным, то возвращается -result.

Например, если num равно 123, то в первой итерации цикла result станет равным 3, а num_remaining станет равным 12. Во второй итерации result станет равным 32, а num_remaining станет равным 1. В третьей итерации result станет равным 321, а num_remaining станет равным 0, что приведет к завершению цикла. В итоге функция вернет число 321. Временная сложность этого решения – O(n), где n равно числу цифр в числе:

Сравним быстродействие решений:

Решение, использующее методы строк, работает заметно быстрее:

Это связано с тем, что встроенная функция [::-1] для инвертирования строки в Python реализована на C-уровне и оптимизирована для работы с символами.

🐍 Библиотека питониста

Больше полезных материалов вы найдете на нашем телеграм-канале «Библиотека питониста»

🐍💼 Библиотека собеса по Python

Подтянуть свои знания по Python вы можете на нашем телеграм-канале «Библиотека собеса по Python»

🧩🐍 Библиотека задач по Python

Интересные задачи по Python для практики можно найти на нашем телеграм-канале «Библиотека задач по Python»

Задание 2

Вычислите частное от деления x на y, где х и y – целые положительные числа. Допустимые операции – сложение, вычитание и побитовый сдвиг.

Решение

Это задачка с подвохом – простейшее решение, при котором y в цикле вычитается из x до тех пор, пока остаток не станет меньше, чем y, окажется самым затратным. Например, если y = 1, a x = 231 –1, для вычисления потребуется 231 – 1 итераций:

Более оптимальный подход:

• Найти наибольшее число k, при котором 2k y <= x.
• Вычесть 2k y из x.
• Добавить 2k к частному.

К примеру, если х = (1011)2 и y = (10)2, то k = 2, поскольку 2 * 22 <= 11 и 2 * 23 > 11. Мы вычитаем (1000)2 из (1011)2, получаем (11)2, добавляем 2k = 22 = (100)2 к частному, и обновляем значение x = (11)2.

Главные преимущества при использовании 2k y – это значение очень эффективно вычисляется с помощью битового сдвига, а значение x уменьшается по крайней мере вдвое с каждой итерацией. Однако наш алгоритм все еще далек от совершенства: если для представления частного от деления x на y потребуется n битов, вычисление будет завершено за O(n) итераций. Если наибольшее k, при котором 2k y <= x, вычисляется итеративно через k, каждая итерация имеет временную сложность O(n), что в итоге приведет к O(n2) алгоритму.

Более эффективный способ найти k в каждой итерации – учесть, что k последовательно уменьшается. То есть вместо того, чтобы каждый раз проверять, что 20y, 21y, 22y меньше либо равно x, после первого обнаружения k, при котором 2k y <= x, в последующих итерациях с x нужно сравнивать 2k-1y, 2k-2, 2k-3y и так далее.

В приведенном выше примере после обнаружения первого k значение частного равно (100)2 к, а x = (11)2. Теперь наибольшее число k, при котором 2k y <= (11)2 равно 0, поэтому мы добавляем 20 = (1)2 к частному, которое после этого будет равно (101)2. Продолжаем цикл с (11)2 – (10)2 = (1)2. Поскольку (1)2 < y, вычисление завершается – частное равно (101)2, остаток равен (1)2. По сути, оптимальное решение применяет деление путем вычитания к двоичным числам и обрабатывает дополнительный бит с каждой новой итерацией. Мы используем сдвиг влево на power разрядов, так как это соответствует умножению на 2**power. Предполагая, что сдвиг и операция сложения занимают О(1), получим решение с временной сложностью O(n):

Сравним время выполнения брутфорсного и оптимизированного алгоритмов:

Результат:

💼 Вакансии по Python, Django, Flask

Лучшие вакансии из мира Python @pydevjob

Задание 3

Имеются текст text и подстрока st. Напишите программу, которая находит индекс первого вхождения st в text.

Решение

Брутфорсный подход – создать вложенный цикл:

Временная сложность этого алгоритма O(nm), где n – длина текста, а m – длина подстроки. Эффективнее использовать один из специальных алгоритмов поиска подстроки – Бойера-Мура, Рабина-Карпа или Кнута-Морриса-Пратта. Воспользуемся алгоритмом Рабина-Карпа – его преимущество в том, что хеши вычисляются очень быстро, а сравнивать строки приходится только при совпадении хешей. Это значительно ускоряет поиск по сравнению с перебором всех срезов подряд:

Вывод:

При условии правильного выбора хеш-функции временная сложность этого решения равна O(n+m).

Задание 4

Напишите функцию для проверки симметричности двоичного дерева. Примеры деревьев:

Первое и третье деревья симметричны, а второе – нет.

Решение

В соответствии с условием симметричным деревом считается дерево, которое симметрично и с точки зрения структуры, и с точки зрения значений узлов. Чтобы проверить дерево на симметричность, можно создать его зеркальное отражение и сравнить его с оригиналом. Временная и пространственная сложность такого алгоритма – O(n), где n – число узлов. Проверку можно оптимизировать, если вместо создания отражения целого дерева сравнивать пары поддеревьев – временная сложность такого подхода O(n), а пространственная – O(h), где h – высота дерева:

Пример использования с заданными в условии деревьями:

Вывод:

Задание 5

Напишите программу для подсчета количества правок, которые нужно выполнить, чтобы преобразовать строку S1 в строку S2. Например, для преобразования слова «лимузин» в «лимонад» нужно сделать 4 правки, а для приведения слова «кошка» к слову «кофта» достаточно 2 изменений.

Решение

Брутфорсный подход – перечислить все строки, отличающиеся на 1, 2, 3 и так далее символов от первой строки, пока не получим вторую строку. В худшем случае нужно будет перебрать 2n вариантов. Более оптимальный подход – воспользоваться алгоритмом вычисления расстояния Дамерау-Левенштейна.

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

Принцип вычисления расстояния Левенштейна выглядит так:

1. Допустим, у нас есть две строки S1 и S2, которые мы хотим сравнить. Мы создаем матрицу M размером (len(S1) + 1) x (len(S2) + 1). Каждая ячейка матрицы M[i][j] будет представлять минимальное расстояние между подстроками S1[0:i] и S2[0:j].

2. На первом этапе инициализируются первая строка и первый столбец матрицы M: в ячейку M[i][0] помещаем значение i, а в ячейку M[0][j] помещаем значение j, так как для превращения пустой строки в S1 или S2 необходимо выполнить i или j операций вставки или удаления соответственно.

3. Затем заполняем оставшуюся часть матрицы M. Для этого рассматриваем каждую пару символов S1[i-1] и S2[j-1]. Если они совпадают, то M[i][j] просто равно M[i-1][j-1], и ничего менять не нужно. В противном случае, M[i][j] равно минимуму из следующих трех значений:

• M[i-1][j] + 1 (удаление символа из S1)
• M[i][j-1] + 1 (вставка символа в S1)
• M[i-1][j-1] + 1 (замена символа в S1 на символ из S2)

Результат – в нижем правом углу матрицы M (M[len(S1)][len(S2)]) окажется минимальное расстояние между строками S1 и S2. Это значение равно минимальному количеству операций вставки, удаления и замены, необходимых для преобразования S1 в S2. Вот так выглядит матрица вычисления расстояния Левенштейна для слов «кошка» и «кофта»:

Временная сложность этого решения – O(len(s1)*len(s2)):

Вывод:

***

Материалы по теме

• 🐍 Функции в Python: 5 задач для тренировки *args, **kwargs и lambda-функций
• 6 алгоритмов решения задач по спортивному программированию
• 🐍🧩 Обработка вложенных списков и матриц в Python: 5 задач с решениями для совершенствования навыков