Петр Смолович

ведущий разработчик хостинг-провайдера и регистратора доменов REG.RU

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

Оценка сложности решения

Для начала убедитесь, что вы понимаете, что такое асимптотическая сложность O(n). В двух словах: это оценка сверху вашего алгоритма в сравнении с типичными функциями: 1, log n, n, n log n, n^2, n^3, 2^n, n!.

Например, получение элемента в массиве по индексу имеет сложность O(1), то есть занимает постоянное время, не зависящее от размера массива.

Поиск элемента массива по значению имеет сложность О(n), т. к. вам нужно пробежаться в цикле по n-элементам.

Сложность оценивается с точностью до константы, т.е. O(n/2) = O(n).

Старшие члены перебивают младшие: O(n^2 + n) = O(n^2).

Два вида сложности

У каждого алгоритма есть временнáя и она же вычислительная сложность (time complexity) — сколько операций нужно выполнить. Также у алгоритма есть затраты памяти (space complexity) — сколько дополнительной RAM ему требуется для работы.

Очень часто эти две величины взаимосвязаны. Например, вас могут попросить уменьшить затраты по памяти, но за это придется заплатить большим количеством вычислений.

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

Сложность строковых операций

Нет необходимости заучивать сложность каждой операции. Достаточно помнить, что большинство операций со строками «под капотом» делают посимвольную обработку. Если каждый символ обрабатывается за константное время O(1), то итоговая временная сложность будет O(n).

Трюк в том, чтобы понять:

• Сколько итераций цикла нужно пройти для получения результата? Иначе говоря, что есть n?
• В каких случаях цикл не нужен, либо наоборот, недостаточен.

Решение задач

Лучшая подготовка к решению задач — это решать их самостоятельно. На Hackerrank или LeetCode можно в том числе найти задачи по конкретной теме (конечно же про строки!).

Важные моменты при подготовке:

• Двигайтесь от простых задач к сложным.
• Засекайте время. Ваше решение должно уложиться в 30 минут максимум.
• Проговаривайте решение вслух: найдите напарника или возьмите резиновую уточку. Интервьюеру важен не только результат, он оценивает ваш подход к решению задач. Не полагайтесь на его навыки телепатии, идите навстречу.
• Сначала убедитесь, что вы поняли задачу, затем расскажите алгоритм решения на словах, и только потом начинайте писать код.
• Неоптимальное решение лучше, чем отсутствие решения. Можно вначале придумать грубый алгоритм, а потом его улучшать.

Пример 1. Палиндромы.

Напишите функцию, проверяющую, является ли фраза палиндромом (например, «довод»).

Решение 1. Обратить строку и сравнить с исходной.

			>>> s = "довод"
>>> s == s[::-1]
True
		

Насколько оно эффективное? Обращение строки стоит O(n) по времени и O(n) дополнительной памяти. Сравнение строк также O(n).

Итого: O(n) по времени, O(n) по памяти. Неплохо, но есть потенциал для улучшения.

Но более приоритетный вопрос — насколько оно правильное? Для палиндрома «а роза упала на лапу Азора» строки уже не будут совпадать, это окей?

Это вопрос к заказчику, то есть к интервьюеру. Можно сформулировать требования более чётко: нужно ли учитывать регистр? нужно ли учитывать все символы, или только буквы?

Разумный ответ заказчика: регистр не учитываем, сравниваем только буквы.

Решение 2. Убираем из строки лишние символы, переводим всё в нижний регистр. Затем обращаем и сравниваем с исходной.

			>>> s = "а роза упала на лапу Азора?"
>>> s = s.lower()
>>> for char in " ,.;:-?!":
...     s = s.replace(char, "")
... 
>>> s
'арозаупаланалапуазора'
>>> s == s[::-1]
True
		

Теперь правильно? Проверили, вроде бы да.

Что с эффективностью? По времени теперь стало O(k * n), где k — число пропускаемых символов. Если k невелико и мы знаем все лишние символы, то можно пренебречь ей как константой. Если лишних символов много или мы не знаем их все, можно заменить replace() на регулярные выражения.

			>>> s = "а роза упала на лапу азора?"
>>> re.sub("[\W]", "", s)
'арозаупаланалапуазора'
		

Итого: опять же, O(n) по времени, O(n) по памяти.

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

Решение 3. Сравниваем первый символ с последним, второй с предпоследним и т.д, пока не встретимся на середине. Спецсимволы пропускаем.

			def isPalindrome(s):
    begin = 0
    end = len(s) - 1
    while begin < end:
        # Пропускаем лишние символы
        while not s[begin].isalpha():
            begin += 1
        while not s[end].isalpha():
            end -= 1
        # Сравниваем текущий символ
        if s[begin].lower() != s[end].lower():
            return False
        # Едем дальше
        begin += 1
        end -= 1
    return True

print(isPalindrome("а роза упала на лапу Азора?"))
		

Тут уже приличный объём кода. Имеет смысл пройтись по нему вручную, проверить на баги и подумать о граничных случаях. Например, что будет, если begin станет больше end пока мы делаем инкремент во внутреннем цикле?

Что стало с эффективностью? Требования по памяти теперь О(1) — мы храним только переменные begin и end. По времени получаем те же О(n).

Стоит отметить, что решение 2 работает примерно одинаково независимо от содержания строки. А вот у решения 3 есть «лучший случай»: когда с первого символа понятно, что это не палиндром, функция вернет результат существенно быстрее — за О(1).

Пример 2. Газетные вырезки

Даны две строки A и B. Написать функцию, определяющую, можно ли составить строку B, используя только символы из строки A (каждую букву можно использовать только один раз).

Решение 1. Первое, что придёт в голову.

Идем в цикле по строке B, ища каждый символ в строке A. Если находим — удаляем его из A, не находим — сразу возвращаем False.

			def can_produce_substr(A, B):
    for char in B:
        char_index = A.find(char)
        if char_index < 0:
            return False
        A = A[:char_index] + A[char_index+1:]
    return True
		

Что может пойти не так с решением?

• Могут быть проблемы с удалением символа из строки, если он нулевой или последний. Спойлер — всё будет хорошо.
• Символы в разных регистрах учитываются как разные. Нужно уточнить задание, правильно ли это.
• Не будет ли проблем, из-за того что мы меняем исходную строку? Не будет, строки неизменяемы, исходная строка останется в памяти нетронутой.

Что со сложностью?

Цикл по B дает сложность O(B). Поиск по A умножает время на длину A в худшем случае. Плюс перезаписывание A на каждом шаге дает О(А) гарантировано.

Итого: О(A*B) по времени, O(A) по памяти.

Можно ли сделать лучше?

Давайте попробуем.

Решение 2. Ищем оптимизацию.

У нас есть две тяжелые операции: линейный поиск по строке и удаление символа из строки.

Вместо удаления символа можно например запоминать его номер как удалённый в отдельном списке. Точнее, в множестве, чтобы поиск был за О(1), а не О(n). Или можно преобразовать строку в список и удалять оттуда. Точнее, заменять на None, тоже для ускорения.

Вместо поиска по строке можно было бы преобразовать строку А в множество. Это даст поиск за О(1) и удаление за О(1). Но, к несчастью, мы потеряем информацию о количестве одинаковых символов в А.

Что делать? А давайте преобразуем А в словарь. Пусть символы из А будут ключами, а количество их вхождений — значениями. Поиск по ключам словаря будет за О(1), обновление значения — тоже за О(1). Сказано-сделано:

			def can_produce_substr(a, b):
    a_dict = {}
    for char in a:
        a_dict[char] = a_dict.get(char, 0) + 1

    for char in b:
        char_count = a_dict.get(char, 0)
        if char_count == 0:
            return False
        a_dict[char] = char_count - 1
    return True
		

Теперь временная сложность составляет О(A + B), что гораздо лучше (A * B). Фактически мы сделали линейную сложность вместо квадратичной.

За это мы заплатили необходимостью хранить в памяти дополнительный словарь размером О(А), что не сильно хуже хранения модифицированной строки О(А). Шалость удалась!

Заключение

Уверенное оперирование задачками такого типа — залог успешного прохождения собеседования на любой уровень. У сеньоров всё то же самое + знание алгоритмов, технологий и принципов проектирования. Задачи бывают попроще, бывают посложнее — тут уж как повезёт. Застрять на сложной задаче может быть нормально, главное не переставать думать, проговаривать мыслительный процесс и не бояться просить помощи. Решить задачу с подсказкой гораздо лучше, чем тупить, пока не закончится время.

Ну и чем больше практики, тем больше вероятность, что вы справитесь с чем угодно. Удачи!