Решаем задачи с LeetCode

Підписуйтеся на Telegram-канал «DOU #tech», щоб не пропустити нові технічні статті.

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

FizzBuzz, конечно, задание показательное, но очень уж набившее оскомину. Где взять больше интересных задач? Память сразу же подкидывает главное «хранилище» программистских задачек, давно ставшем синонимом подготовки к собеседованиям, LeetCode. В этой статье я дам несколько советов о том как начать «прокачивать» свои скилы на LC и покажу разные варианты решения нескольких задач на Python.

Знайте возможности языка

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

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

Для простоты, на собеседованиях обычно сокращают задание, фокусируясь на основном вопросе. Например, в этой задаче можно не добавлять условие про попадание числа в интервал 32-битных целых (Python защищает от потенциальных проблем с переполнением, а написать if с двумя сравнениями могут почти все). Но в этой статье давайте рассмотрим решение целиком.

Задание это весьма не сложное, и пойти тут можно двумя путями: используя преобразование в строку или серией делений на 10. Разумеется, «более правильным» является второй способ, хотя то, что кандидат использует средства языка — тоже хороший знак. LeetCode такие решения «принимает», да и на собеседованиях вариант вроде приведённого ниже вполне может стать отправной точкой интересной беседы.

class Solution:
    def reverse(self, x: int) -> int:
        is_neg = x < 0
        pure = int(str(x).strip("-")[::-1])
        
        result = -pure if is_neg else pure

        if result < -2147483648 or result > 2147483647:
            return 0
        else:
            return result

Отмечу что заворачивать решение в класс Solution — предложение самого LeetCode.

На самом деле, я бы даже предпочёл увидеть такое решение, чем «правильное», потому что тут сразу видно владение Python: удаление префикса с помощью метода .strip() (не все знают что он может принимать параметры), инверсия строки с помощью оператора среза [::-1]. Но даже в этом случае есть что улучшить. Например, сохранить переменную знака не как булевский флаг, а как одно из двух чисел: -1 или 1 и потом просто помножить на него результат.

class Solution:
    def reverse(self, x: int) -> int:        
        sign = -1 if x < 0 else 1
        
        result = sign * int(str(x).strip("-")[::-1])

        if result < -2147483648 or result > 2147483647:
            return 0
        else:
            return result

Можно ещё немного полихачить и вычислить sign как-то так

sign = x // abs(x)

Но тут в силу очевидных причин ещё придётся проверять x на равенство нулю в начале функции, да и, пожалуй, это уже идёт чуть-чуть в ущерб читаемости.

«Правильное» решение пишется большинством кандидатов как-то так (на этот раз я опущу проверку диапазона).

num = abs(x)

result = 0
while num > 0:
    last_digit = num % 10
    result *= 10
    result += last_digit
    num //= 10

return -result if x < 0 else result

Решение достаточно эффективное, его можно ещё сократить, записав меньшим количеством строк, но это уже опциональное улучшение.

Кстати, на схожем принципе строятся очень многие похожие задачи, начиная с вот этой, и заканчивая классикой вроде преобразования числа в строковую запись в другой системе счисления. Вообще, советую вам потренироваться в манипуляциях с числами: например, написать сложение двух чисел неограниченной длины. Это задание есть на LeetCode, но они его усложнили использованием связанных списков. Для тренировки можно сперва сделать сложение для чисел, хранящихся в виде строки или массива цифр и подумать, какие тут есть способы обхода сложностей и оптимизации. Также полезным навыком будет умение манипулировать битами и понимание роли логических операторов в этом.

Понимайте ресурсоёмкость

Рассмотрим ещё одну задачу. На вход функции подаётся список строк и нужно найти общий для всех этих строк префикс максимальной длины. Например, для списка ["programming", "product", "procrastination"] — ответом будет "pro". На LeetCode это задание помечено как easy (как, кстати, и ставшая уже мемом задача инверсии бинарного дерева), но именно такие задачи и хороши для собеседований, тут есть о чём поговорить. Относительно опытный Python программист, знакомый с функцией zip и концепцией передачи параметров может написать что-то такое.

class Solution:
    def longestCommonPrefix(self, strs: List[str]) -> str:
        result = []
        for items in zip(*strs):
            if len(set(items)) == 1:
                result.append(items[0])
            else:
                break
                
        return "".join(result)

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

Можно блеснуть лихостью и записать всё в виде однострочника.

"".join(items[0] for items in zip(*strs) if len(set(items)) == 1)

Выглядит это эффектно, но, кроме непонятности, у данного кода есть ещё одна проблема: он весьма не оптимален. Высокоуровневые конструкции языка скрывают от нас манипуляции с данными, которые в случае больших строк и массивов относительно накладны по скорости и памяти. Я пишу относительно, потому что современные процессоры — очень быстрые, а памяти — много, поэтому проблема будет заметна только на больших списках/строках либо если это будет часто повторяемая операция.

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

def lcp2(strs: List[str]) -> str:
    if len(strs) == 0:
        return ""

    lcp_len = 0

    while True:
        try:
            if any(strs[0][lcp_len] != strs[idx][lcp_len] for idx in range(1, len(strs))):
                break
        except IndexError:
            break

        lcp_len += 1

    return strs[0][:lcp_len]

Идея ловить исключение для обработки выхода «за пределы» какой-то из строк — достаточно интересна, хотя решение с циклом while True делает метод достаточно «хрупким», есть риск попасть в вечный цикл. С этим примером, кстати, так и происходит, если подать ему на вход список из одной строки. В целом, это можно исправить с помощью второй проверки.

if len(strs) == 1:
    return strs[0]

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

if not strs:
    return ""

min_str = min(strs, key=len)

for idx, chr in enumerate(min_str):
    for other in strs:
        if other[idx] != chr:
            return min_str[:idx]

return min_str

Тут у нас, конечно, появляется «лишний» проход по списку в поисках самой короткой строки, но зато мы экономим память. Тут также важно не забыть, что цикл может завершиться потому что min_str «закончилась», в таком случае она и является нашим общим префиксом.

Не используйте «читы»

Вообще, «прокачиваясь» на LeetCode надо понимать, какую цель вы ставите перед собой, иногда бывает так, что задачи уровня «hard» решаются с помощью встроенных средств языка. Например, вот эта. Я намеренно беру задачи из самого начала списка LeetCode, чтоб уменьшить «спойлерность» статьи. Задача формулируется достаточно просто: у вас есть два отсортированных массива произвольной длины, нужно найти медиану массива, образованного их слиянием. «Правильное» решение в данном случае затянет на отдельную статью, поэтому если вы хотите знать как «нужно» сделать — прекрасное объяснение есть на самом LeetCode.

Но на самом деле, сайт принимает вот такое решение.

from statistics import median

class Solution:
    def findMedianSortedArrays(self, nums1: List[int], nums2: List[int]) -> float:     
        return median(nums1 + nums2)

Что особенно забавно, этот вариант работает быстрее чем 18% всех решений и оптимальней чем 80% решений по памяти, впрочем, статистика самого LeetCode тут не особо показательна.

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

Ищите «паттерны»

Постепенно, решая задачи, начинаешь понимать некоторые шаблоны, например, многие задания можно свести к некому варианту «парсинга» ввода с использованием упрощённых вариантов автоматов. Так что, если вы не знакомы с этим походом, очень советую устранить данный пробел. Всегда создавать полноценную грамматику, конечно, перебор, но с некоторым «срезанием углов» этот метод позволяет решать многие прикладные задачи. Вот типовой пример проблемы с LeetCode, требующий использования упрощённого варианта подхода. В этом задании все манипуляции сводятся к сравнению с предыдущим (или следующим) элементом.

Вот сама задача. На вход подаётся отсортированный список уникальных целых чисел, нам надо преобразовать его в список минимальных диапазонов идущих подряд чисел, используя указанный синтаксис. Например, список [[0,1,2,4,5,7]] преобразуется в ["0->2","4->5","7"], так как у нас есть три диапазона: от 0 до 3, от 4 до 5 и отдельно 7.

Сразу приведу решение.

class Solution:
    def format_range(self, min: int, max: int) -> str:
        return f"{min}" if min == max else f"{min}->{max}"

    def summaryRanges(self, nums: List[int]) -> List[str]:
        if len(nums) == 0:
            return []

        result = []
        start = 0

        for idx in range(len(nums)-1):
            if (nums[idx+1] - nums[idx]) != 1:
                result.append(self.format_range(nums[start], nums[idx]))
                start = idx + 1

        result.append(self.format_range(nums[start], nums[-1]))

        return result

Как видите, оно очень прямолинейно и укладывается в приведённую выше схему. Мы храним начало очередного диапазона и проходимся по списку, «подглядывая» следующее значение. Если оно больше чем на 1 отличается от текущего, значит текущий элемент — конец очередного диапазона. Мы сохраняем найденный диапазон в список результатов и устанавливаем начало текущего диапазона на следующий за текущим элемент (он с него в самом деле и начнётся).

Ну и в конце нам надо не забыть добавить последний диапазон, так как цикл его не обработает. По схожему принципу строится много задач в стиле «удалить повторы из строки», «найти длину максимальной не-убывающей подпоследовательности» и так далее. Если же вы хотите потренироваться в более формальном подходе и всё-таки применить конечный автомат на практике, вот классическое задание парсинга числа из строки. Вы можете попытаться тут обойтись и без КА, но почти наверняка решение включающее его в неявном виде родится у вас само.

Заключение

Я хотел закончить каким-то абзацем в стиле «надеюсь я сумел вас заинтересовать решением задач на LeetCode...». Но потом подумал, что это звучит слишком шаблонно, поэтому просто скажу задачи оттуда нужны не только для желающих устроиться в FAANG, иногда они действительно позволяют по-новому посмотреть на свой язык программирования и оптимизацию кода.