Розв’язуємо задачі на Leetcode. Загальний підхід та конкретний приклад

Усім привіт, мене звати Іван. Маю 6-річний досвід роботи в IT, працював на початку своєї кар’єри в стартапі, потім Luxoft, зараз в EPAM. Обіймаю посаду старшого розробника.

Leetcode.com — це вебсайт, на якому люди, переважно інженери-розробники програмного забезпечення, хочуть вдосконалити свої практичні навички кодингу. Також ви можете порівняти ваш код, написаний для розв’язання певної проблеми, з рішеннями інших програмістів.

Leetcode здебільшого використовується для двох випадків:

1. Розв’язання проблем структури даних, алгоритмів, тому що це цікаво.
2. Підготовки та практики кодування інтерв’ю, тому що це надійний спосіб отримати офер від світових компаній, таких як, наприклад FAANG.

Часто це другий варіант.

Мета цієї статті — запропонувати покрокові інструкції розв’язання проблем і показати приклад, як вирішувати їх поетапно.

Важливо визначити процес розв’язання задачі. Найфундаментальніше, що потрібно зробити перед написанням коду, це спочатку зрозуміти алгоритми й різні техніки.

Розглянемо процес з трьох кроків, які допомогли мені як у вивченні цих методів, так і у розв’язанні проблем.

Крок 1

Спочатку я б визначив спосіб ймовірного рішення. Я б розділив способи рішення на кілька категорій, які б покривали більшість проблем:

• Trees (BST and BT)
• LinkedList
• Arrays & Strings
• Graph & Trie
• Search & Sort
• Dynamic programming

Крок 2

Другий крок — визначення методу розв’язання для кроку 1. Всі можливі методи розв’язання проблем вже були придумані до нас, не потрібно винаходити велосипед знову, потрібно тільки вивчити їх і зрозуміти.

На мій погляд, спочатку потрібно спробувати розв’язувати проблему (можливо, навіть найгіршим способом). З мого досвіду, якщо одразу націлитись на найкраще рішення, є висока ймовірність застрягти й втратити будь-яку надію на розв’язок.

1. Trees (BST and BT):
   
   • Tree traversal
   • DFS
   • BFS
2. LinkedList:
   
   • Two pointer technique
   • Slow and fast pointer
   • Backtracking
   • Reverse list & process
3. Arrays & Strings:
   
   • Two pointer technique
   • Sliding window
   • Sort data and search
   • Backtracking
4. Graph & Trie:
   
   • DFS
   • BFS
   • Topological sort
   • Recursion
5. Search & Sort:
   
   • Sort data & search
   • Backtracking
6. Dynamic programming:
   
   • Bottom-up
   • Top-down

На Leetcode завдання розбиваються за рівнем складності.

Крок 3

Reduce time complexity. Найпростіший спосіб його зменшення — це використання stack, queue, map, list, set.

Порівняйте складність алгоритму, яку ви отримали при розв’язанні проблеми та оптимальну складність, а потім подумайте про те, як ви могли б надалі вдосконалювати рішення. Нижче наведено приклад.

Приклад розв’язання задачі з Leetcode

Given an array of integers nums and an integer target, return indices of the two numbers such that they add up to target.

Example 1:

Input: nums = [2,7,11,15], target = 9
Output: [0,1]
Explanation: Because nums[0] + nums[1] == 9, we return [0, 1].

1. Перше рішення, яке приходить на думку, полягає в тому, щоб пройти лінійно через масив і знайти потрібну суму:

Time complexity O(n*n)

2. Проблемою поточного коду в алгоритмі пошуку елементів є O(n) ми можемо покращити його до O(log(n)), використовуючи бінарний пошук.

def twoSum(self, nums, target):
        for i in range(len(nums)):
            j = bisect_left(nums,target - nums[i])
            if i >= 0:
                return [i, j]

Time complexity O(n*log(n))

3. Найкращим результатом буде складність всього алгоритму — O(n). Тоді виявляється, що сам пошук елементів повинен займати складність O(1). Єдине, що дає таку складність, це hash table:

    def twoSum(self, nums: List[int], target: int) -> List[int]:
        hashmap = {}
        for i in range(len(nums)):
            complement = target - nums[i]
            if complement in hashmap:
                return [i, hashmap[complement]]
            hashmap[nums[i]] = i

Time complexity O(n)

Висновок

Подивитись у вкладку «Solution» значно легше, аніж знайти вирішення самостійно. Навіть якщо ваш алгоритм виконує найгірше завдання, я б рекомендував спочатку оцінити складність виконання перед безпосереднім поглядом у вкладку «Solution». Якщо ви не в змозі розв’язати проблему більше ніж за 10 хвилин, потрібно набратись терпіння і все ж таки намагатись зробити це без «Solution», адже таким чином ви ніколи нічого не дізнаєтесь.

Потрібно зрозуміти розв’язання проблеми належним чином. Приклад output і тест випадки, наведені в задачах Leetcode, є простими. Якщо взяти це як джерело істини та почати проєктування алгоритму, ваш код зазнає невдачі. Тому я б порадив спробувати різні тестові випадки, щоб переконатися, що ви розумієте всі сценарії й лише тоді кодувати їх. Таким чином, ви будете охоплювати всі виклики EDGE і багато чому навчитися під час процесу.

Сподобалась стаття? Підписуйтесь на автора, щоб отримувати сповіщення про нові публікації на пошту.

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