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

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

Усім привіт, мене звати Іван. Маю 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 і багато чому навчитися під час процесу.

Сподобалась стаття? Натискай «Подобається» внизу. Це допоможе автору виграти подарунок у програмі #ПишуНаDOU

👍ПодобаєтьсяСподобалось15
До обраногоВ обраному12
LinkedIn
Дозволені теги: blockquote, a, pre, code, ul, ol, li, b, i, del.
Ctrl + Enter
Дозволені теги: blockquote, a, pre, code, ul, ol, li, b, i, del.
Ctrl + Enter

Якого бiса оце leetcode.com/...​es-in-even-length-groups записано як medium
Коли оце leetcode.com/...​reverse-nodes-in-k-group сидить в хардах?

Companies: Zopsmart
Точно не Жопсмарт?

if i >= 0:
return [i, j

Це взагалі неправильне рішення, бо цикл завершиться на першому проходженні завжди

Це взагалі неправильне рішення, бо цикл завершиться на першому проходженні завжди

Блд, а я в код то навіть і не сильно вчитувався, зачепився за bisect

lmgtfy.app/...​king the coding interview

І особисто від себе додам, що якщо зібралися проходити співбесіди з кодінгом, то розберіться з алгоритмічною складністю, бо купа людей код написати можуть, а от розмовляти про його ефективність не можуть

Прям як на парах) 95% просто не викупило про що розмова

Очень рекомендую посмотреть на Ютубе курсы от Alvin Zablan, там их штуки 3 бесплатных, вот один из них youtu.be/tWVWeAqZ0WU

Дякую за статтю, на днях не знайшовши чогось такого в гуглі довелось самому посидіти і зробити собі таку шпаргалку :)

Маю ~400 вирішених задач на літкоді. Я б сказав, що заняття на літкоді потрібно починати не з літкоду, а з якоїсь книги чи курсу по алгоритмах. Бо ви можете довго і нудно придумувати якусь техніку, а потім виявиться, що її вже 100 років назад придумали і гарно описали, і реалізували краще за вас. Більше того, вона має стандартну назву і на співбесіді може бути достатньо сказати, що «ми тут використаємо BFS / north-west corner method / two pointers technique», на що інтерв’ювер кивне головою, поставить галочку «зараховано» і перейде до наступної задачі. Ну бо чого втрачати час, якщо ви знаєте назву методу, то ви його при потребі напишете, а як не напишете, то загуглите. От інша справа коли ви назви методу не знаєте — ви будете придумувати велосипед і швидше за все з перших кількох спроб він вийде кривий і косий.

Так, як варіант. Я б ще рекомендував класику — «Introduction to Algorithms», якраз он четверте видання вийшло. І ще я проходив розділ leetcode.com/explore — теж трохи структурує знання.

Маю ~400 вирішених задач на літкоді.

Как это конвертировалось в бабос?

Я б сказав, що це трохи нагадує термін «потенціальна енергія» з фізики. Якщо вона є — її можна на щось витратити і, можливо, буде якийсь результат (а може і ні). Інша справа коли накопиченої енергії нема — тоді результату точно не буде.

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

Я имел ввиду «как у вас конвертировалось 400 задач в капусту?»

Фаанг півроку назад давав 300 к за л5, співбесіди туди в основному через літкод. Десь так воно конвертується. В локальній пісочниці не монетизується.

Працюю вже більше 15 років в ІТ, перший раз стикнувся з цим літкодом на співбесіді, яку звичайно провалив. Потім сів порішав пару десятків задач і не знайшов в жодній із них якогось практичного застосування на проектах, це все мені нагадує олімпіадки або лабораторні роботи в унівєрі на 2 курсі. Я маю на увазі, що за весь цей час роботи розробником — ніразу не було нічого подібного до Merge K linked arrays чи buy sell with max profit. Все ще вважаю це все брєдом, який можна порішать за тиждень практики — ніякого реально експіріенса кандидата воно не відображає.

я теж недавно тільки пішов на отой літкод подивитись.

спочатку зацікавив розділ SQL.
В цілому — у проді такий код писати — буде заборонено, база буде лягати від тих рішень.
А складні — то взагалі — такє точно перекладають з БД на клієнта, або пишуть зберігаємі процедури

Загальний розділ — задачкі на знання оптимізації арифметичних дій — то мабудь ембедерам та в гейдеві треба. мене від них майже фізично нудить. хоча зробив декілька середнього рівня, можу! :)

Мені ж сподобались задачкі на пошуки оптимальних шляхів.
Від практичного програмування — далекі, просто цікаво було. Якесь відчуття — як в «дитинство» попав :)

це все мені нагадує олімпіадки або лабораторні роботи в унівєрі на 2 курсі.

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

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

+++
Сам помітив за собою у Штатах десь років 6 тому, як я ходжу кругами навколо редактора, у той час як колега-американець прямо при мені відкрив редактор, тупо нашпарив код, щоб щось спробувати. Я пронікся. Аж ще кілька разів тренажери сліпого друку пройшов, і літкодив теж, щоб отак шпарити. Код, ще так як він, не шпарю, але порівняно із собою 2016 року — кодострочильний ріст видно. Ну і у Slack ого-го, як строчу, щоб швидко щось вияснити :-).

Це тому мабуть, що мало хто із вчителів пояснює їм, що кожна помилка наближує їх до перемоги. Помилки це як точки виходу із деяких зачарованих кіл. Є здається навіть такий напрямок Error Driven Programming
А щоб хоч у чомусь помилитися треба щось написати. Бо знання складається із вміти правільно та вміти неправільно бо саме так full functionality will been achived

я теж недавно тільки пішов на отой літкод подивитись.

спочатку зацікавив розділ SQL.

— Mom, can we have Leetcode?
— No. We have Leetcode at home
Leetcode at home:
Write an SQL query to report all customers who never order anything

який можна порішать за тиждень практики

Bullshit)

Якщо ніколи в житті не рішав то булшіт, але якщо 15 років тому в унівєрі лаби не списував то дуже легко згадується.

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

Вы верхнюю границу пишите для уровней изи/медиум/хард, а то люди будут сидеть и седеть

намагатись зробити це без «Solution», адже таким чином ви ніколи нічого не дізнаєтесь

Сомнительное предложение, как раз из солюшена хоть что-то и можно понять.

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

Це слушна думка. Я згоден що одразу відкривати відповідь це не варіант. Але рекомендації в цілому такі — якщо за час не виходить вирішити проблему, треба дивитися як її вирішити, в ідеалі декілька рішень передивитися що в топі.
Замість 3-4 годин на вирішення задачі котра не виходить краще просуватися далі і вивчати як такі задачі вирішувати.

І ще пам’ятати що якщо ми говоримо про інтерв’ю на кодінг то там в нас 45 хвилин, є сенс тренуватися вирішувати задачи з 30-40 хвилин.

є сенс тренуватися вирішувати задачи з 30-40 хвилин.

Приходить саме з практикою

Цікавий сервіс. Мені ще подобається www.hackerrank.com та www.codewars.com/dashboard — як на мене, хакерранк має перевагу бо там є прям цілий блок для підготовки на співбесіду або кодревʼю, не кажучи про багато іншого.

Якщо не пробували, спробуйте ще codility.com

як на мене, хакерранк має перевагу бо там є прям цілий блок для підготовки на співбесіду

отаке
leetcode.com/assessment
чи таке
interview.leetcode.com/interview
?

Чи навчальні модулі?
leetcode.com/explore

LC75 — самое то.
Правда есть идиотизм, если не решил все задачки в срок, раздел курса надо начинать сначала

LC75 — самое то.
Правда есть идиотизм, если не решил все задачки в срок, раздел курса надо начинать сначала

ти про це?
leetcode.com/study-plan/leetcode-75
я навіть не чув про цей урл раніше :-), все якось своїми шляхами

Спочатку подумав, що ти про ось цю, 75-ту задачку, хз, чого вони її поставили medium,а не easy, може через слово sort, хоча там сходу бачу двопрохідний трюк
leetcode.com/problems/sort-colors

Сорі за занудство

def twoSum

->

def two_sum

Ну і пітоністи юзають enumerate

Таким чином, ви будете охоплювати всі виклики EDGE

-> Таким чином, ви будете охоплювати всі edge cases

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

ожидание: Given two sorted arrays nums1 and nums2 of size m and n respectively, return the median of the two sorted arrays. The overall run time complexity should be O(log (m+n))

реальность: Given an array of integers nums and an integer target, return indices of the two numbers such that they add up to target

Сьогоднішній mandatory disclaimer:
свинцю плавленого свинособакам у горлянку!
---

Disclaimer 2:
я давній (але не все ще не 100% проходящий) учасник leetcode-забігів, зокрема гляньте на теми про «24 онсайти» — dou.ua/forums/topic/28593 і про «7-8 онсайтів» — dou.ua/forums/topic/40684
---

Дякую за початок. Тепер кілька зауважень до покращення.
Задачка, яку ви розглядаєте
leetcode.com/problems/two-sum

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

Бінарний пошук працює на сортованих даних. У описі задачки цього нема. У вашому тексті це теж пропущено. Якщо bisect_left сортує на ходу, то варто було би про це згадати. Якщо не сортує, але попередньо треба посортувати — то теж треба було б згадати.

Time complexity O(n*log(n))

Знову ж таки у цій складності стирчать вуха сортування, але перед тим ви згадали про O(log(n)), а не O(n*log(n)).

А щоб мало не показалось, фолловап на 3Sum, далi на 4, 5 та NSum

Чи не бажаєте поділитись посиланням на свій профіль на LC?

Підписатись на коментарі