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

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

Задание 1

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

Решение

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

def reverse_integer(num):
    num_str = str(num)
    if num_str[0] == "-":
        reverse_str = "-" + num_str[:0:-1] 
    else:
        reverse_str = num_str[::-1]

Для решения без использования строк нужно запустить цикл 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 равно числу цифр в числе:

def reverse_integer(num):
    result, num_remaining = 0, abs(num)
    while num_remaining:
        result = result * 10 + num_remaining % 10
        num_remaining //= 10
    return -result if num < 0 else result

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

import timeit

def reverse_integer_1(num):
    result, num_remaining = 0, abs(num)
    while num_remaining:
        result = result * 10 + num_remaining % 10
        num_remaining //= 10
    return -result if num < 0 else result

def reverse_integer_2(num):
    num_str = str(num)
    if num_str[0] == "-":
        reverse_str = "-" + num_str[:0:-1] 
    else:
        reverse_str = num_str[::-1]
    return int(reverse_str)

# Тестируем на случайном числе из 10000 цифр
num = int("".join(str(i % 10) for i in range(10000)))

# Сравниваем время выполнения двух функций
t1 = timeit.timeit(lambda: reverse_integer_1(num), number=100)
t2 = timeit.timeit(lambda: reverse_integer_2(num), number=100)
print(f"Время выполнения решения с циклом: {t1:.6f} секунд")
print(f"Время выполнения с методом строк: {t2:.6f} секунд")

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

Время выполнения решения с циклом: 9.354593 секунд
Время выполнения с методом строк: 0.213387 секунд

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

Задание 2

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

Решение

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

def divide(x, y):
    quotient = 0
    remainder = x
    while remainder >= y:
        remainder -= y
        quotient += 1
    return quotient

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

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

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

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

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

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

def divide (x, y):
    result, power = 0, 32
    y_power = y << power
    while x >= y:
        while y_power > x:
            y_power >>= 1
            power -= 1
        result += 1 << power
        x -= y_power
    return result 

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

import timeit

def divide_1(x, y):
    quotient = 0
    remainder = x
    while remainder >= y:
        remainder -= y
        quotient += 1
    return quotient

def divide_2(x, y):
    result, power = 0, 32
    y_power = y << power
    while x >= y:
        while y_power > x:
            y_power >>= 1
            power -= 1
        result += 1 << power
        x -= y_power
    return result

x, y = 1000000, 7
time_1 = timeit.timeit(lambda: divide_1(x, y), number=1000)
time_2 = timeit.timeit(lambda: divide_2(x, y), number=1000)
print(f"Время выполнения брутфорсного алгоритма: {time_1}")
print(f"Время выполнения оптимизированного алгоритма: {time_2}")

Результат:

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

Задание 3

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

Решение

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

def find_st(text, st):
    n = len(text)
    m = len(st)
    for i in range(n - m + 1):
        j = 0
        while j < m and text[i+j] == st[j]:
            j += 1
        if j == m:
            return i
    return -1

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

import functools

def rabin_karp(text, st):
    if len(st) > len(text):
        return -1 
    BASE = 33
    text_hash = functools.reduce(lambda h, c: h * BASE + ord(c), text[:len(st)], 0)
    st_hash = functools.reduce(lambda h, c: h * BASE + ord(c), st, 0)
    power_st = BASE**max(len(st) - 1, 0) 
    for i in range(len(st), len(text)):
        if text_hash == st_hash and text[i - len(st):i] == st:
            return i - len(st) 
        text_hash -= ord(text[i - len(st)]) * power_st
        text_hash = text_hash * BASE + ord(text[i])
    if text_hash == st_hash and text[-len(st):] == st:
        return len(text) - len(st)
    return -1 

text = "В роще-чаще рыщет ящер, ищет пищи подходящей"
st = "ще"
print(rabin_karp(text, st))

Вывод:

4

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

Задание 4

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

Дерево 1:
        1
       / \
      /   \
     2     2
    / \   / \
   3   4 4   3

Дерево 2:
        1
       / \
      /   \
     2     2
    / \   / \
   3   5 6   3

Дерево 3:
        1
       / \
      /   \
     2     2
    /       \
   5         5

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

Решение

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

def is_tree_symmetric(tree):
    def check_symmetric(subtree_0, subtree_1):
        if not subtree_0 and not subtree_1:
            return True
        elif subtree_0 and subtree_1:
            return (subtree_0.data == subtree_1.data
                    and check_symmetric(subtree_0.left, subtree_1.right)
                    and check_symmetric(subtree_0.right, subtree_1.left))
        return False
    return not tree or check_symmetric(tree.left, tree.right)

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

from collections import namedtuple
Node = namedtuple('Node', ['data', 'left', 'right'])

tree1 = Node(1, Node(2, Node(3, None, None), Node(4, None, None)), Node(2, Node(4, None, None), Node(3, None, None)))
tree2 = Node(1, Node(2, Node(3, None, None), Node(5, None, None)), Node(2, Node(6, None, None), Node(3, None, None)))
tree3 = Node(1, Node(2, Node(5, None, None), None), Node(2, None, Node(5, None, None)))
           
for t in [tree1, tree2, tree3]:
  print(is_tree_symmetric(t))

Вывод:

True
False
True

Задание 5

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

Решение

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

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

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

Основные идеи решения:

Рекурсия. Алгоритм работает рекурсивно, начиная с конца обеих строк. Он сравнивает последние символы каждой строки:

• Если символы совпадают, они игнорируются, и функция вызывается для оставшихся подстрок.
• Если символы различаются, то выбирается минимальная операция из трех возможных: вставка, удаление или замена символа. Каждая операция увеличивает счетчик на 1.

Базовые случаи:

• Если одна из строк пуста (т.е. все символы удалены), то для преобразования нужно просто добавить (или удалить) оставшиеся символы второй строки.
  
• Для пустой строки требуется столько операций, сколько символов в другой строке.
  

Динамическое программирование. Чтобы избежать избыточных повторных вычислений для одних и тех же подстрок, промежуточные результаты сохраняются в специальной таблице (матрице). Это позволяет существенно сократить время работы алгоритма, снижая его сложность до O(n * m), где n и m — длины строк.

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

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

       | к | о | ф | т | а |
   --------------------------
   | 0 | 1 | 2 | 3 | 4 | 5 |
-----------------------------
 к | 1 | 0 | 1 | 2 | 3 | 4 |
-----------------------------
 о | 2 | 1 | 0 | 1 | 2 | 3 |
-----------------------------
 ш | 3 | 2 | 1 | 1 | 2 | 3 |
-----------------------------
 к | 4 | 3 | 2 | 2 | 2 | 3 |
-----------------------------
 а | 5 | 4 | 3 | 3 | 3 | 2 |
-----------------------------

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

def levenshtein_distance(S1, S2):
    def fill_matrix(S1_idx, S2_idx):
        if S1_idx < 0:
            return S2_idx + 1
        elif S2_idx < 0:
            return S1_idx + 1
        if M[S1_idx][S2_idx] == -1:
            if S1[S1_idx] == S2[S2_idx]:
                M[S1_idx][S2_idx] = (fill_matrix(S1_idx - 1, S2_idx - 1))
            else:
                substitute_last = fill_matrix(S1_idx - 1, S2_idx - 1)
                add_last = fill_matrix(S1_idx - 1, S2_idx)
                delete_last = fill_matrix(S1_idx, S2_idx - 1)
                M[S1_idx][S2_idx] = (1 + min(substitute_last, add_last, delete_last))
        return M[S1_idx][S2_idx ]
    M = [[-1] * len(S2) for _ in S1]
    return fill_matrix(len(S1) - 1, len(S2) - 1)
print(levenshtein_distance('кошка', 'кофта'))

Вывод:

2

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

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