День 68 - Конец теории 8ой недели - Часть 2

Краткий обзор второй части теории недели 🤔 Данная часть знакомит нас с основными алгоритмами поиска кратчайших путей в графе:

1. Алгоритм Дейкстра
2. Алгоритм для Edge Weighted Acyclic Graph на основе топологической сортировки
3. Алгоритм Беллмана-Форда

Сами алгоритмы несложные и легко реализуются, и в целом похожи немного друг на друга. Ниже приложил полезные материалы по каждому из них:

Дейкстра:
1. Abdul Bari - https://www.youtube.com/watch?v=XB4MIexjvY0&list=PLDN4rrl48XKpZkf03iYFl-O29szjTrs_O&index=45
2. William Fillset https://www.youtube.com/watch?v=pSqmAO-m7Lk&list=PLDV1Zeh2NRsDGO4--qE8yH72HFL1Km93P&index=15&t=760s

Здесь нам снова понадобиться IndexMinPQ, поэтому советую, если не изучили, посмотреть материал на эту ДС

DAG:
1. William Fillset - https://www.youtube.com/watch?v=TXkDpqjDMHA&list=PLDV1Zeh2NRsDGO4--qE8yH72HFL1Km93P&index=13

Беллман-Форд
1. William Fillset - https://www.youtube.com/watch?v=lyw4FaxrwHg&list=PLDV1Zeh2NRsDGO4--qE8yH72HFL1Km93P&index=16

Советую также уделить особое внимание алгоритму Дейкстра, так как он необходим для выполнения задания 8ой недели 👨‍🏫

Ниже прикладываю небольшое саммари по использованию каждого из алгоритмов. Слайд из презентации Сенджвика:

День 68 - Конец ассаймента 8ой недели ☄️

Завершил задание 8ой недели - Seam Carver 🎉 Задача решает проблему content-aware image resizing - изменение размера картинки с сохранинием наиболее важных частей контента, путем расчета "энергии" пикселя

Мне понравилась задача, особенно зная, что данный алгоритм применяется внутри современных графический редакторов. и самое главное, она решается с помощь графов и алгоритма поиска кратчайшего пути Дейкстра 👨‍🏫 На первый взгляд, задача кажется сложной, но достаточно внимательно вчитаться и начать имлементить простые методы - станет легче 😊

Как начать и не сдаться? 💪

1. Повторяем алгоритм Дейкстра для поиска SP

2. Имлементим первые методы SeamCarver
- getPicture() - возвращаем копию картинки
- width() - возвращаем ширину картинки
- height() - возвращаем высоту картинки
- energy(x, y) - расчитываем по формуле из задания энергию пикселя
- SeamCarver конструктор, в двумерный массив, записываем энергию каждого пикселя

3. Тестим расчет энергии через утилитный класс ShowEnergy, который идет в комплект к заданию вместе с файлами для тестов

4. Далее переходим к самому сложному:
- findVerticalSeam() - seam - это полоса пикселей, которую мы можем "вырезать" из картинки. По-сути это поиск кратчайшего пути, где весом является энергия пикселя. Ищем этот кратчайший путь, записываем номера колонок и возвращаем.

- transponse() - просто переворот картинки, для того, чтобы не имлементить findHorizontalSeam()
- findHorizontalSeam() - Делаем transpose() картинки и вызываем findVerticalSeam()

На этом основные методы закончились, удаление removeHorSeam & removeVerSeam, не представляют сложности, по-сути это просто копирование массивов исключая наши horizontal & vertical seam.

Следующие шаги:
1. Обновить материалы на smart-progress 👨‍🏫
2. Решить: https://leetcode.com/problems/network-delay-time/
3. Решить: https://leetcode.com/problems/cheapest-flights-within-k-stops/
4. Начать 9ую неделю курса ☄️

Идем дальше 💪

День 70 - Начало 9 недели

Закончил решать задачки:
1. https://leetcode.com/problems/network-delay-time/
2. https://leetcode.com/problems/cheapest-flights-within-k-stops/

Обе задачи являются неплохой практикой по практике алгоритмов Shortest Paths в графе. Нужно выбрать алгоритм, который вам нравится 🤔

1. Дейкстра
2. DFS
3. Беллман-Форд

Я выбрал Bellman-Ford, так как он не требует использования Priority Queue для решение задачи. В JS нет стандартной имлементации этой ДС 😔. Поэтому, если вы на джаве или шарпах, то Дейкстра для вас не проблема.

Min cut - Max Flow

Также, начал теорию 9ой недели. Как я понимаю, это заключительная часть по графам на курсе 🎉

Следующие шаги:
1. Закончить 1 тему недели Min cut - Max Flow
2. Выполнить assignment Baseball Elimination

Идем дальше 💪

День 74 - Конец ассаймента 9ой недели 🎉

Закончил изучать первую часть теории - Network Flow. Разобьем все по порядку:

Теория
Мне было немного тяжело воспринимать теоритический материал на этой неделе. Пришлось пересматривать по 5-6 раз видосы 🤯, чтобы разобраться, как же считается этот граф и флоу. В последний день, уже снились сны, что я на листке рисую граф и поток 😂

И так, полезные видео, чтобы влиться в топик:
1. Разбор алгоритма Форда - Фалкерсона https://www.youtube.com/watch?v=LdOnanfc5TM&list=PLDV1Zeh2NRsDGO4--qE8yH72HFL1Km93P&index=34&t=0s
2. Max-Flow / Min-Cut - https://www.youtube.com/watch?v=oHy3ddI9X3o

Понять основные моменты и термины:
1. Augmenting Path - Если простыми словами, путь от источника (source) до стока (sink)
2. Bottleneck - ребро с наименьшей пропускной способностью (capacity)
3. Flow Augmenting - Обновление значений потока на пути в augmenting path
4. Residual Graph & Residual Edge - Обратный граф и ребро.

Все термины отлично разъясняются в видео выше 👨‍🏫. Сам алгоритм несложный в имлементации, но технические моменты обновления ребер графа придется разобрать на листочке. Рисуете сначала алгоритм с нуля вместе с обходом графа на доске / листе бумаги, обновляем capacity ребер, только так можно победить 😂

Доказательства 🤯
Я не стал погружаться в доказательство, почему алгоритм Форда-Фалкерсона находит Min-Cut и Max-Flow. Но если сильно хочется, советую посмотреть раздел учебника - Section 6.4 (pp. 886–902) and 5.1 in Algorithms, 4th edition. Там все довольно подробно объясняется 👨‍🏫

Baseball Elimination Assignment 👨‍🏫

ps: Следующую часть лучше прочитать, только когда будете делать задание, иначе без контекста не сложно понять :)

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

Как выполнить задание и не сдаться? 💪
Читаем презентацию: https://www.cs.princeton.edu/~wayne/papers/baseball_talk.pdf

1. Начинаем с самого простого, считываем таблицу из текстового файла и записываем в нужные структуры:

- массив с количеством побед win[teams.length]
- массив с количеством проигрышей losses[teams.length]
- массив с оставшимися играми rem[teams.length]
- массив с количеством матчей команд с другом другом games[teams.length][teams.length]
- массив команд teams[teams.length]
- мапа для конвертации индекса команды в название Map<int,string>

Для того, чтобы построить FlowNetwork, чтобы определить вылетит ли команда, нам нужно:

- Все матчи где не участвует эта команда - пилим отдельный метод на это и возвращаем все матчи, других команд
- Размер сети - Количество команда + Количество матчей + sink node + source node

2. Теперь у нас есть все, чтобы построить сеть:
- Коннектим с помощью FlowEdge sink node c нодами команды и выставляем им capacity = w[target] + r[target] - w[current], где target команда, которую проверяем на вылет, a current - текущая.

Зачем это делаем? Так мы ограничиваем количество побед, которых команда может получить. Далее поясню.

- Соединяем матчи с командами, тут capacity не ограничен, ставим Infinity
- Соединяем source node c матчами, capacity будет равен количеству оставшихся игр у команда games[team1][team2]

Я долго не мог уловить момент с распределением capacity, пока хорошенько не вчитался в течении 2 дней 😂

Суть такова: если ребра из source node, во время работы алгоритма Фалкерсона, заполняются не полностью, это значит что ограничение, которое мы создали в соединении команд и sink node нарушается, если бы они наполнились полностью. А это значит, что команда не может победить так как количество игр, распределенное между командами будет больше, чем количество возможных побед искомой команды.

В целом, это базовые советы, которые решают 90% задачи.

Следующие шаг: Закончить теорию по Radix Sort

#week_9 #assiignment

День 76 - Конец 9 недели 🎉

Закончил изучать теорию по Radix Sort и Key-Counting sort. Мне данная часть курса не особо понравилась, уж слишком сухой материал у Сенджвика, как мне кажется. Зато теперь вы точно будете знать, как отсортировать массив миллиона интов за O(N) 😂

Я посмотрел вот эти видео, чтобы полностью разобраться в топике:
1. https://www.youtube.com/watch?v=1mh2vilbZMg
2. https://www.youtube.com/watch?v=XiuSW_mEn7g

А вот забавное видео на эту тему: https://www.youtube.com/watch?v=k4RRi_ntQc8

Следующие шаги:
1. Начинаю 10 неделю - Tries & Substring search, как мне кажется, неделя будет насыщенной и интересной 💪
2. Обновить Smart Progress

Идем дальше ☄️

День 79 - Конец 10 недели 😳

Получилось закончить неделю в рекордные 2 дня. По ощущениям, теория на этой недели оказалась довольно несложной. Разберем все по порядку:

Tries
Преффиксные деревья или "бор", в русской литературе. Данная тема разбирает одну из имплементаций Symbol Tables. Лично я, никогда не использовал Tries на практике, но был приятно удивлен, на сколько это полезная структура данных при работе со строками. Применение trie, довольно широкое

- Синтаксические проверки слов
- Знаменитый Т9 - (о да, он был написан с использованием Trie
- Автодополнения в строке поиска
- Маппинг REST эндпоинтов в серверных фреймворках

Все это прекрасно дополняется сравнением с хэш таблицей. Я не использовал дополнительные материалы на этой неделе. Так как объем теории вполне sufficient для понимания.

Для погружения, я бы рекомендовал сделать следующее:

1. Напишите интерфейс StringST с базовыми методами таблицы символов

2. Имлементируйте самостоятельно TrieST, тут вам очень поможет первый курс, так как рекурсивные методы практически идентичны секции с деревьями

3. Для обычного Trie, мы используем довольно много места, для каждого узла приходится создавать массив длинной R, где R количество уникальных символов алфавита (26 для английского например), для этого дядюшка Сенджвик придумал структуру Ternary Trie 👨‍🏫, у которой нет такого недостатка. Имлементим ее тоже.

👉 Почему важно самостоятельно заимлементить это? 👈

В большинстве языков, нету стандартной имплементации Trie, а вот задачи на собесе дать по ним могут :troll-face:
К тому же, это знание вам понадобится, чтобы выполнить задание недели 🤔

Substring Search 👨‍🏫
Тут скорее не на столько практичная, сколько академическая и для личного кругозора теория, о том как организован современный поиск по строкам. В большинстве случаев, данные вещи уже есть в практически любом языке программирования. Как мне кажется, сильно заострять внимание на этом не стоит, но знать полезно.

Assignment - Boggle

Задание представляет собой игру, квадрат 4х4, с буквами английского алфавита, нам надо собрать все возможные слова. Задание является отличной практикой Trie и как мне показалось, является одним из самых простых за оба курса.

Как победить? 👌
1. Задание предполагает, что мы считываем словарь с английскими словами, который потом будет использовать для поиска нужного слова. Первое, что мы делаем - имлементим BoggleTrie.

Базовые методы:
- get
- put
- contains

Тут смело возвращаемся к теории недели и пилим ДС. Тут есть одна особенность. R = { буквы англ алфафита } = 26. Но в игре используются большие буквы, а это значит, что Индекс первой заглавной А = 65 (из таблицы ASCI), нам надо привести индекс к обычному виду 0 .. 26, для этого используем OFFSET = 65

2. После имлементации trie, считываем наш словарь и кладем все слова в ДС

3. Все слова есть, теперь надо организовать поиск. Как это сделать? DFS 👨‍🏫. BoggleBoard, это квадрат 4х4, а значит, нам надо для каждой клетки выполнить DFS. Двигаться можем в 8 сторон ( юг, запад, восток, север + диагонали). Если встречаем слово из словаря, кидаем его в результат.

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

Следующие шаги:
1. Идем вперед графика - Week 11 - RegExp, Data Compression. На этой недели нас ждет последнее задание на курсе 🎉
2. Обновить smart progress

Не болеем 💪

Небольшое сравнение имлементаций ST

День 81 - Конец 11 и 12 недели - Финал Курса 🎉

Сегодня я полностью закончил курс Algorithms and Data Structures from Princeton.

Я не ожидал, что последние 2 недели получится закрыть за 4 дня, учитывая, что на предыдущих неделях, я еле укладывался в неделю 🧐. На самом деле, это не от того, что я очень умный :troll: , просто 11,12 неделя преподносятся на курсе, как более-менее опциональные , и зная это заранее, я бы не стал на них тратить время. Курс вообще считается законченным, если закрыть 11ую неделю. И так по порядку.

Week 11 - Regular Expressions and Data Compressions 💩

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

Week 12 - Reductions, NP problems 👩‍💻

Опциональная неделя, которая в целом мне показалась полезна. Дается неплохой разбор и определение NP hard и NP complete проблем и много сухой теории. Если хотите сразу и по-существу и разобрать все эти термины:

- P vs NP - Determenistic | Non-Determenistic problem
- Satisfiability
- Reduction
- NP-Hard vs NP-Complete

товарищ Абдул за 32 минуты расскажет и пояснит все: вот тут

Лично я когда читал описание некоторых задач, не понимал, что означает, что проблема - NP Hard или NP Complete. После этого видео, все встает на свои места. Обязательно рекомендую к просмотру 👍

Я бы хотел написать больше, но это весь правдивый итог по последним 2ум неделям 🧐

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

Следующие шаги:
1. Сделать пост-дэшбоард со всеми ссылками
2. Обновить материалы на smart-progress, пройдусь по всем постам, соберу инфу в кучу
3. Начать планирование следующей итерации подготовки

Спасибо всем, кто писал и проходил курс вместе со мной 💪 Было очень приятно видеть комментарии от Вас ❤️

Ближайшие 2 месяца я планирую сфокусироваться на литкоде и решении алгоритмических задач. Все полезные материалы и коментарии буду также выкладывать здесь и на smart-progress

Бомбим дальше 🔥

Когда закончил курс, который длился почти 3 месяца:
https://www.youtube.com/watch?v=kJ_7ELaZ7ak

Общий отзыв по курсу Сенджвика 👨‍🏫

Решил небольшое саммари курса. И так, курс состоит из 2ух частей и по 6 недель каждая. Итого - 12 недель = 84 дня

Время за которое у меня получилось его пройти: 81 день, с учетом того, что я еще еще иногда решал литкод на темы недель.

Ну как курс?

Я не жалею ни секунды, потраченного времени на него. По-хорошему, это то, что должна давать универская подготовка (ха-ха). Даже если вы сеньор-помидор 🧔, будет полезно пройти его, я открыл для себя много новых вещей. Самое главное, нашел дыры в своей теоритической подготовке и залатал их. Могу только рекомендовать пройти его

Расписание, по корому я проходил курс:

1. 3-4 часа в будние дни, я решал задачи и изучал теорию ( половину курса я вставал утром, до основной работы, вторую половину, решил попробовать после работы).
2. 6 часов в выходные выполнял задания недели (assignments)

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

Общие заметки:

1. На ассайменты может уходить больше, чем день, не сдавайтесь ✊. Даже имея почти 5 лет коммерческого опыта, я сидел как школьник и не понимал, после прочтения инструкции по ассайменту

2. На неделях, где разбираются структуры данных, обязательно нужно имлементировать ее самому ( кроме исключений, в виде некоторых операций над Red Black Tree ). Только так придет полное понимание

3. Решайте 5-10 задач на литкоде на топик ДС, которую прошли. Поможет закрепить материал.

4. Использование дополнительных материалов в виде ютубчка и прочих сервисов - must - на курсе.

5. Мотивация в самом начале будет на максимуме, но постепенно, вы будете чувствовать, что становится лениво и тяжело. Это нормально :) Мне помогло в конце каждой недели заказывать набор сушей, дофамин в мозг никогда не помешает

Недели, которые, по моему мнению, можно пропустить 👎

1. Week 6 - Hash Tables, довольно поверхностно, лучше взять другой материал. Серия статей на хабре Структуры данных в картинках, полностью покрывает данную тему
2. Week 11,12, 11 неделя не супер practical для интервью, а 12ую, лучше заменить на видео с канала Абдула, съэкономите 2 часа жизни.

Сейчас чувствую себя, как выжатый лимон 😵. Решил дать себе 2-3 дня на отдых и планирование дальнейшей подготовки.

Пока в кратце план такой:
1. 1.5 - 2 месяца литкода, минимум 200-250 решеных задач
2. 1.5 месяца на фронтендовые топики + System Design, на этом этапе начну проходить мок интервью
3. Неделю на софт-скилную подготовку и тренировку с нативом
4. В конце июля начинать подаваться через реферралов.

Всем не болеть 😊

Week 0 - Leetcoding, да начнется дроч 😂

И так, сегодня я начал решать литкод. Скажу честно, меня расстраивает, что индустрия IT в северной америке, скатилась к тому, чтобы сидеть и надрачивать алгоритмические задачки, которые иногда далеки от реальности и фронтенда подавно :) Но, это не самое худшее в целом.

Я не знаю идеального гайда по гринду, поэтому буду ориентироваться на опыт других людей.

С чего начинаем:

1. Grocking Coding Interview - книга, буду ее изучать и параллельно решать задачи. Не планирую вычитывать ее полностью, буду разбирать по теме и выбирать самые интересные задачки.

2. Leetcode Patterns - большинство задач на литкоде, сводится к определенному паттерну. Разбираем и нарешиваем задачи по каждому из них. По темам, выглядит это примерно так:

- Arrays
- Two pointers / Fast and Slow pointers
- Modified Binary Search
- Merge Intervals
- K-Way Merge
- Sliding Window
- Top 'K' Elements
- Topological Sort
- BFS
- DFS
- Two Heaps
- Graphs
- Backtracking
- Dynamic Programming 🤯

Задачки по каждому паттерну, можно найти вот здесь:
https://seanprashad.com/leetcode-patterns/

Задачи буду делить на 3 категории A, B, C.
- А - решил легко 💪
- В - хорошо подумал 🤔
- С - плакал в подушку 😭

Все самые хорошие задачи , материалы и заметки по ним, буду выкладывать здесь 👨‍🏫

3. Контесты - Начиная с первой недели, буду участвовать в литкодовских контестах. Результаты буду тоже выкладывать сюда и я почти уверен, что они будут не очень :)

План до конца недели:

1. Решить задачки из списка выше на тему Arrays

2. Решил также посмотреть литкодовский материал на массивы:
https://leetcode.com/explore/learn/card/fun-with-arrays/
По ощущениям, там что то легкое, но надо проверить 😁

3. Прочитать Introduction и Algorithms Analysis главу из Grocking Coding Interview

Не болейте и stay home 💪

День 89 - Leetcode Arrays 🍼

Решил 26 задачек на тему массивов.
Разобьем самые хорошие по категориям и уровню моих страданий ( А, B, C ):

Повертеть, покрутить массив - используем интуицию 🧐

1. 54 Spiral Matrix ( А )
2. 941 Valid mountain array ( A )
3. 1089 Duplicate Zeros ( A )
4. 48 Rotate Image ( C ) - вот тут очень хитрая работа с индексами. Долго думал, но посмотрел решение в итоге.
5. 73 Set Matrix Zeros ( C )

Введение в Two-Pointers - для того, чтобы начать вникать 👶🏻

6. 283 move яeroes ( А ) - Разминка №1
7. 485. Max consicutive ones ( А ) - Разминка №2
8. 905. Sort Array By Parity ( B )
9. 487. Max Consecutive Ones II ( B )
10. 88. Merge Sorted Array ( B ) - Неплохая задачка на 2 указателя.
11. 448.Find All Numbers Disappeared in an Array ( B )
12. 977.Squares of Sorted array ( B )
13. 1299. Replace Elements with Greatest Element on Right Side ( B ) - учимся заходить сзади

14. 287. Find the duplicate number ( B ) - вот тут надо посмотреть алгоритм Флойда 👨‍🦳, чтобы разобраться.

Рекомендую вот эти видео:
1. https://www.youtube.com/watch?v=pKO9UjSeLew ( посмеяться )
2. https://www.youtube.com/watch?v=9YTjXqqJEFE ( разобраться )

Backtracking
14. 79. Word Search ( B ) - Немного не в тему. Несложная задачка, особенно после Сенджвика. Но придется сделать несколько оптимизаций, чтобы прошли все тест кейсы.

Ехидные
15. 442.Find duplicates numbers ( С ) - задачка простая, но меня заставила изрядно подумать и потупить. Помогло построение полной таблички работы цикла и перемещениям по индексам

Я указал самые интересные задачки, которые мне попались и заслуживают вашего внимания. В список не попали задачки вот из этого материала: https://leetcode.com/explore/featured/card/fun-with-arrays/
Так как там в основном они тривиальные.

Следующие шаги:
1. Решить 10-15 задач на Two Pointers
2. Повторить задачи с пометкой B и решить снова с пометкой C

Литкодим дальше 👨‍💻

День 95 - Sliding Window & Two Pointers 👬

Изначально планировал решать задачи только на 2 pointers, но пока решал, заметил, что в этих задачах часто используется паттерн Sliding Window, поэтому решил расширить пул задач для этой недели.

Итого решено: 18 задач

Разобьем все по темам, уровню моей боли и порядку, в котором стоит их решать 💁‍♂️

Градация боли: А - изи, В - подумал, С - поплакал 😢

Two Pointers - работа с двумя указателями.

1. (1) Two Sum (A) - на самом деле нифига не 2-p, хотя стоит тег. Но задача подводит нас к проблемам посложнее с использованием two pointers
2. (83) Remove duplicates from sorted list (A)
3. (833) - Backspace string compare (A)
4. (977) - Squares of a sorted array (A)
5. (167) - Two Sum input array is sorted (A)
6. 3Sum (C) - усложнение задачи two sum.
7. 3SumClosest ( B )

Sliding Window
Сначала надо разобрать паттерн и понять как его применять, мне помогли вот эти ссылки:
1. https://www.geeksforgeeks.org/window-sliding-technique/
2. https://medium.com/leetcode-patterns/leetcode-pattern-2-sliding-windows-for-strings-e19af105316b

В целом, все задачи очень похожи. Пострадаете над одной, другие пойдут относительно легче 👨‍🏫

8. 713 - Subarray products less than K (C)
9. 209 - Minimum Size subarray Sum ( B )

Далее очень похожие задачи на применине sliding window на строки.

10. 424 - Longest Repeating character replacement ( C )
11. 3. - Longest Substring without repeating character ( B )
12. 159 - Longest Substring with at most 2 distinct characters ( B )
13. 340 - Longest Substring with at most 2 distinct characters ( A ) повторяет предыдущую
14. 904. Fruit Into Baskets (A) - притворяется сложной, но упрощается к предыдущим задачам, если прочитать внимательно описание
15. 567 - Permutations (B)

Задачи, которые я бы решил в конце. Так как их проще решать, когда есть опыт двух подходов:

16. 11 - Container with a most water
17. 75 - Sort Colors
18. 763 - Partition labels

Немного рефлексии и самокритики
1. Проспал контекст в 5.30 утра 😒
2. К сожалению, очень часто не укладываюсь во временные лимиты для интервью. У меня на medium в среднем уходит по 40-50 минут на задачу, а иногда и 2 часа.
3. Grokking Coding interview, пока отложил. Не получается параллелить книгу с решением задач, теряю фокус. Решил сосредоточиться на литкоде. Видимо у меня в голове однопоточный JS 😂

Следующие шаги:
1. 10-15 задач Fast & Slow Pointers
2. Повторить задачи с пометкой (С) с прошлой недели

Идем дальше 💪

День 101 - Fast & Slow pointers

Закончил решать задачки на паттерн с медленными и быстрыми указателями. Задачки на эту тему показались мне более интуитивными и не требующими специальных знаний, кроме LinkedList.

Пререквизиты для темы 👨‍🏫

1. Разобраться со связанными списками - если проходили сенджвика, врятли для вас это будет проблемой
2. Разобраться с алгоритмом флойда, для нахождения цикла, уже писал об этом в постах выше
3. Посмотреть, как применяются два указателя, вот тут целая серия статей:
https://www.pluralsight.com/guides/algorithm-templates:-two-pointers-part-1

Че решил то?
Мне понравилась литкодовская карточка https://leetcode.com/explore/learn/card/linked-list/, разбирает классические проблемы на списках, а так список такой, как обычно в рекомендуемом порядке:

Задачки для разминки 💪

707. Design Linked List
141. Linked List Cycle
142. Linked List Cycle II
876. Middle of the Linked List
2. Add Two Numbers
21. Merge Two Sorted Lists
430. Flatten a Multilevel Doubly Linked List

Посложнее 🤔

206. Reverse Linked List
143. Reorder list
160. Intersection of Two Linked Lists
19. Remove Nth Node From End of List
203. Remove Linked List Elements
234. Palindrome Linked List
138. Copy List with Random Pointer
24. Swap Nodes in Pairs

Где я затупил 😔

61. Rotate List
708. Insert into a Sorted Circular Linked List.

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

Следующие шаг: решаем задачки на бинарный поиск 💪

Всем не болеть 😊

День 105 - Binary Search + Binary Trees

Закончил решать задачки по бин-поиску ☄️

Для начала, надо бы разобраться, что это такое и как применять. Для этого отлично подходит литкодовская карточка: https://leetcode.com/explore/learn/card/binary-search/

Там разбираются 3 паттерна бин-поиска

1. Классический - возращаем искомый индекс

Для извращенцев 😍

2. Вариант, когда нужно получать доступ к правому элементу от текущего во время поиска
3. Вариант, когда нужен доступ к левому и правому элементу от текущего во время поиска

Первый раз, когда я на это посмотрел, реакция была - WTF 🤔. Нафига выделять 3 варианта бин-поиска? В итоге, все задачи начинал решать обычным и вроде даже получилось, потом стал замечать, что иногда приходится править кондишены, чтобы получить верный ответ и прозрел, потому что иногда я повторял эти 2 странных варианта.

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

BTW, есть еще один паттерн бин-поиска, так называемый Петропоиск, этот вариант я прочитал в группе литкодовцев, вот метода, где можно узнать подробно. Лично я его не применял :)

https://github.com/petr-kalinin/progtexts/releases/tag/v2014.11.01

И так, задачки:

Разминаемся 🍼

704. Binary Search - имлементим классику
278. First Bad Version - применяем классику 1
374. Guess Number Higher or Lower - применяем классику 2
162. Find Peak Element - включаем мозг, чтобы понять как применить классику
69. Sqrt(x) - необычное применение бинпоиска
50. Pow(x,n) -
349. Intersection of Two Arrays - не бин поиск, но нужна для следующей
350. Intersection of Two Arrays II

Думаем 🤔

34. Find First and Last Position of Element in Sorted Array
74. Search a 2D Matrix
240. Search a 2D Matrix II
152.Find peak element
852. Peak Index in a Mountain Array
744. Find smallest letter greater than target
153. Find Minimum in Rotated Sorted Array
154. Find Minimum in Rotated Sorted Array II

Где я долго тупил 😢

33. Search in Rotated Sorted Array
658. Find Closest K elements

Итого: 17 задач 👨‍💻

Задачки с бин-поиском для меня были ночным кошмаром, так как нужно быть очень внимательным, чтобы не напутать индексы во время поиска. Но на 3-4й день стало на много проще :)

Дополнительно 👨‍🏫
Решил перед графами взглянуть на секцию с Binary Tree, потренить траверсы. В целом неплохо. Можно спокойно проделать все вот эту карточку: https://leetcode.com/explore/learn/card/data-structure-tree/

Основной упор идет на работу с pre-order, in-order, post-order. Я думаю еще вернуться к этой теме, так как вообще тема с траверсом деревьев напрямую связана с фронтовыми задачками на DOM :)

В следующей серии:
1. Graphs
2. BFS - расширяемся
3. DFS - идем в глубь
4. Topological Sort - вспоминаем господина Сенджвика
5. Контест, просплю ли я его снова?

Идем дальше 💪