День 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. Контест, просплю ли я его снова?

Идем дальше 💪

День 108 - Binary Trees, Graphs, BFS, DFS, Topsort

Ну что, последние дни прошли насыщеннее, чем я думал 🤓. Чем больше решаешь задачи, тем больше не хочешь их решать и тратить время. Это мотивировало меня решать их абсолютно все свободное время 🤢 в надежде быстрее закончить это.

Всего получилось решить: 55 задач 💪

Правда, многие из них мне были уже знакомы, так как я прорешивал их во время курса Сенджвика. Разобьем по темам и по порядку, в котором стоит за них браться.

✅ Binary Trees - Первое, что следует сделать, это понять все возможные обходы дерева, я уже писал, но вот эта карточка, мне очень сильно помогла.

- 94. Binary Tree Inorder Traversal
- 144. Binary Tree Preorder Traversal
- 145. Binary Tree Postorder Traversal

✅ DFS - учимся в глубину

Разминочка 🍼
- 100. Same Tree
- 101. Symmetric Tree
- 104. Maximum Depth of Binary Tree
- 112. Path Sum
- 226. Invert Binary Tree
- 230. Kth Smallest Element in a BST
- 250. Count Univalue Subtrees

Продолжаем 💪
- 98. Validate Binary Search Tree
- 105. Construct Binary Tree from Preorder and Inorder Traversal
- 113. Path Sum II
- 572. Subtree of Another Tree
- 617. Merge Two Binary Trees
- 654. Maximum Binary Tree
-
Пострадаем ⚠️
- 235. Lowest Common Ancestor of a Binary Search Tree
- 236. Lowest Common Ancestor of a Binary Tree
- 297. Serialize and Deserialize Binary Tree
- 437. Path Sum III
- 543. Diameter of Binary Tree
- 545. Boundary of Binary Tree
- 662. Maximum Width of Binary Tree

✅ BFS - задачки на bfs показались супер однотипными, у меня возникли трудности лишь с парочкой. Все задачи в среднем одинаковой сложности:

- 102. Binary Tree Level Order Traversal
- 107. Binary Tree Level Order Traversal II
- 103. Binary Tree Zigzag Level Order Traversal
- 116. Populating Next Right Pointers in Each Node
- 111. Minimum Depth of Binary Tree
- 199. Binary Tree Right Side View
- 637. Average levels of binary tree
- 662. Maximum Width of Binary Tree
- 133. Clone Graph

⚠️ Но я пострадал вот тут:
- 117. Populating Next Right Pointers in Each Node II
- 863. All Nodes Distance K in Binary Tree

✅ Graphs - тут было проще. часть задач уже решал, разминаемся на простеньких:
- 802. Find Eventual Safe States
- 997. Find the Town Judge
- 743. Network delay time
- 785. Is Graph Bipartite? - не простенькая, выкладывал в канале материалы о двудольных графах. Советую их посмотреть прежде чем решать
- 787. Cheapest Flight within k stops

✅ Topsort - многие задачи требуют понимания алгоритма топологической сортировки, на канале неоднократно уже выкладывал все материалы по ней. Как по мне, так очень стремно, если тебе на интервью попадается такая задача, так как не зная алгоритм, вероятность, что иннутивно решишь, крайне мала

207. Course Schedule
208. Course Schedule II
209. Graph Valid Tree
210. Minimum Height Trees

✅ Union Find - Спасибо дядя Сенджвик 👨‍🏫. Некоторый тип задач на графы, помимо DFS и BFS замечательно решаются через Union Find. И тут мы обращаемся к первой неделе первого курса и радостно потираем ладони, ведь UF - наше супер оружие

- 547. friend-circles
- 684. redundant-connection
- 947. most-stones-removed
- 959. regions-cut-by-slashes
- 200. Number of Islands
- 323. Number of Connected Components in an Undirected Graph

Все выше задачи легко решаются уничтожаются с Union Find. Однако есть одна сложность - помнить имлементацию данной структуры. У меня получилось ее выучить на зубок, но возможно, на интервью можно будет сказать "предположим у меня есть uf 😃"

Ух, получилось много сегодня 🧐. Далее нас ждет:
1. Binary Search Trees
2. Trie

Благодаря праздникам, иду вперед плана, надеюсь как можно скорее покончить с задачами.

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

День 115 - ленивая неделя 🐻 - | Trie, BST, Top - K

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

Из того, что получилось сделать:

Trie - префиксное дерево

1. 677 - Map Sum pairs
2. 648 - Replace words
3. 642 - Design autocomplete system
4. 211 - Add and search word, data-structure design

Не стоит здесь смотреть на лейбл - хард. Все задачи решаются путем правильного использования Trie. Разобраться с ним - основная задача. Есть вероятность, что на интервью придется сделать простой Trie, поэтому целесообразно набить руку.

Если есть желание, можно также посмотреть на Ternary Trie. Господин Сенджвик кстати придумал и также разбирал на курсе. Решает проблему жирного потребления памяти и несложно имлементируется.

У литкода есть отличная карточка - https://leetcode.com/explore/learn/card/trie/

BST - бинарное дерево поиска

Вот тут просто скорее рефрешер операций с БСТ после Сенджвика. Если проходили курс, легко вспомните :)

5. 173 - Binary Search Tree iterator
6. 701 - Insert into a Binary Search Tree
7. 700 - Search in BST
8. 450 - Deletion in BST

Top-K Elements - тип задач, где надо найти Nый самый самый ( наименьший / наибольший )

Так же как и с Trie. Много задач решаются применением Priority Queue aka Heap. Я очеееень сомневаюсь, что фронтендера будет их спрашивать. Учитывая, что в js нет хипа совсем. Но для общего саморазвития прорешал вот эти задачи

9. 215. Kth Largest Element in an Array - вот тут в первые понадобился quick-select. Все-таки стоит заучить merge и quick sort...
Освежить знания поможет - https://www.youtube.com/watch?v=hGK_5n81drs

10. 230. Kth Smallest Element in a BST

Задачки ниже решил на джаве, из-за наличия в ней хипа.

11. 347. Top K Frequent Elements
12. 973. K Closest Points to Origin

Рефлексия 🙈

Надо отдыхать, если чувствуешь, что уже тяжело и ничего не хочется. Мне очень помогли следующие вещи:
- Снизить рабочую нагрузку, если есть такая возможность
- Сходить в однодневный поход 🏞
- Почитать книгу 📜
- Позалипать в игру 😂

Полная смена деятельности помогла перезагрузится. На этой неделе возвращаюсь в рабочий ритм 💪

Следующие шаги:

1. Разобраться задачи по Backtracking
2. Intro to Dynamic Programming? 😳 - TBD

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

День 117 - Backtracking | Перебирай меня полностью 😂

Зарешал набор задач по Backtracking. Всего решил 13 задачек.

Могу сказать, что первые 2-3 задачи вынесут мозг, так как каждая решается рекурсивно и нужно рисовать стек вызовов, чтобы понять, что происходит. А так, большинство задач - просто перебор возможных вариантов

Но! Есть и хорошая сторона - это паттерн. Для всех 13 задач, он индентичен. Поняв его, остальные задачи будут проще.

Мне отлично помогли видосы по Backtracking от товарища Абдула. Смотрим под номером 63-71 👨‍🏫, а далее приступаем к задачам.

https://www.youtube.com/watch?v=DKCbsiDBN6c&list=PLDN4rrl48XKpZkf03iYFl-O29szjTrs_O&index=63

Че по задачам то?💁‍♂️

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

Начинаем с этих задач

39. Combination Sum
46. Permutations
77. Combinations
78. Subsets
494. Target Sum
17. Letter Combinations of a Phone Number
22. Generate Parentheses
784. Letter case permutation

Чуток усложняем, в основном хэндлим дубликаты 🤔
Из названий понимаем, что это вариации задач выше с чуть более сложным условием.

40. Combination Sum II
47. Permutations II
90. Subsets II
216. Combination Sum III
131. Palindrome Partitioning

Dynamic Programming 🙈
Для фронтендеров, хорошие новости, задачи по динамике, в большинстве случаев, не дают 🎉. Это подтверждает опыт опрошенных знакомых и тщательное ковыряние форума Blind и Leetcode. Решил, что не буду тратить на это время 💁‍♂️

Что дальше?

1. Я прорешал все запланированные топики по задачам. Всего получилось 176 задач. Первые интервью, у меня планируются с AWS, поэтому я дополнительно пробегусь по спискам Top Amazon Questions и Top Interview Questions, и решу самые часто встречаемые из них.

2. После этого, начинаю проходить мок-интервью 2-3 раза в неделю. Все-таки за чашечкой зеленого чая, задачи решаются менее стрессово, чем на виртуал онсайте 😂

3. И можно будет начинать фронтовые темы 🎉 Но об этом позже.

Не болейте👨‍💻

Паттерн для backtracking задач с перебором

День 124 - Конец Алго Подготовки 🎉

Закончил решать задачки из списка Top-amazon questions и часть Top Interview questions. В моем случае, не так много нужно было решать, так как большинство уже было решено на прошлых неделях и малая часть из них

Вот разбивка по темам 🧐

📙 Design - обожаю такие вопросы :)
146. LRU Cache
155. Min Stack
380. Insert Delete GetRandom O(1)

📙 Top-k-elements
692 - Top K Frequent words

📙 Trie
1268 - Search Suggestion System

📙 Min-PQ
1167 - Minimum Cost to connect sticks

📙 Stack
227 - Basic Calculator II

📙 Сет, сортировка и мапа
12. Integer to Roman
13. Roman to Integer
49. Group Anagrams
819. Most Common Word
937. Reorder Data in Log Files

✅ Итого: 14 задач
✅ Общие статы: 71 / 110 / 6 ( easy / medium / hard ) = 187 задач

На этом я заканчиваю литкодить. Хватит ли этого? Не знаю :) Скоро проверим 😂

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

Следующие шаги ☄️

Front-End подготовка ❤️
Наиболее интересная и полезная часть.

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

📄 Примерный план

✅ General Knowledge
Вопросы, которые встречаются на любом интервью даже в РФ.
- HTML Questions
- CSS Questions
- Javascript Questions

✅ Advanced Topics
- Accessibility
- Optimisation and Web Performance

✅ Practical Questions
Задачки, которые обычно говорят сделать на доске или онлайн.

- Component Design in Vanilla JS - пишем простенькие компоненты на ваниле
- Designing general usage functions - debounce, throttle and etc
- Working with DOM API - вертим дом на вертеле
- Data-Structure design

Боевые условия - Mock Interview 💪

Для этого буду пробовать свои силы для тестовых интервью. Площадки которые хочу использовать:

Pramp - (бесплатно). Есть несколько вариантов интервью Front / Algo / Sys-Design. Говорят, много индусов.

https://t.iss.one/FaangInterview - очень крутой телеграмм чат, боже храни админов 🙏Большинство подписчиков скорее всего оттуда. Много полезных материалов, особенно для генералистов . Ребята устраивают бесплатные мок-сессии, за что им огромное спасибо 👍

Всем добра 🙏

День 132 - Готовим фронтенд 🧔 | Тестовые интервью

✅ Подошла к концу первая неделя фронт-подготовки.

В основном повторял Javascript Core вопросы.
Как и обещал, начал готовить 👉 док 👈 со всеми материалами. Док пока еще сырой, заполняется по мере подготовки. Если считаете, что можно добавить в него что то, пишите, буду очень благодарен 🙏

Сделаем жизнь фронтендерам чуточку легче 💪

Большое количество вопросов я взял из репы вот отсюда
Отфильтровал самые очевидные и дополнил подробными личными заметками наиболее интересные.

✅ Курсы, чтобы повторить / прокачать JS Core:

- JavaScript: Hard Parts - офигенный курс, разбирающий наиболее сложные места в JS. Решил пробежаться по нему еще раз. Тот самый advanced материал, для глубокого понимания языка.

- Deep Javascript Fundamentals - курс от создателя знаменитой серии книг You don't know JS. Кайл, имеет в некоторых моментах, специфичное мнение о правильных вещах в JS, НО, узкие места разбирает отлично

- JavaScript: Recent Parts Еще один курс Кайла по последним нововведениям, напоследок, чтобы отшлифовать 😀

Курсы очень рекомендую 👍

✅ CSS
Тут я несильно заморачивался. Но может помочь, если считаете, что нужно освежит знания

CSS Core:

- CSS in Depth v2

Сетки:
1. Advanced CSS Layout
2. CSS Grids and Flexbox for Responsive Web Design

✅ Мок интервью - Pramp

Я прошел 5 алго мок интервью на Pramp по алго. Моей первой задачей была вариация Two Sum, как же я тупил 😄 Мысли кратко:

1. С реальным человеком оказалось намного сложнее, но только первые 2 раза. Затем привыкаешь.

2. Бывали выбросы, в виде ребят, которые выключали mic и вебку, и решали задачу молча, этого я не понимал.

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

Фронтовые интервью буду проходить на выходных, посмотрим, что за зверь.

✅ Leetcode Mock

Премиум, открывает возможность проходить мок интервью по компаниям. Задачки решаются на время и кажется, на много продуктивнее решать по таймеру. Я прошел:

1. 4 Amazon Phone intreview - довольно простые изи / мед задачки

2. 2 Amazon Online Assesment intreview - задачки идут из этого списка

3. 1 On-site - мед / хард из TOP Amazon Questions

Литкод строит статистику по темам, где можно видеть проблемные места. Но для этого надо пройти 15-20 моков.

Следующие шаги 🏋️‍♀️

1. Component Design in Vanilla JS
2. Designing general usage functions
3. Продолжаю проходить алго / фронтенд моки

Идем Дальше 💪

День 139 - Конец фронтендовой подготовки 📚

Закончил готовить фронтенд темы к интервью. Вообще, это самая приятная и несложная для меня часть, в отличии от алго, так как связана с твоими повседневными задачами.

Что разобрал?

Весь разобранный материал с заметками лежит 👉 здесь 👈

Там найдете код, демки и конспект

👨‍🏫 General usage functions - то, что применяем не думая

Тут все просто, на интервью часто спрашивают заимлементить какую-либо функцию из библиотеки. Наиболее частые из них.

- throttle / debounce
- compose, pipe
- bind
- async-await
- extend
- memo
- flatten
- promisify

🍨 Ванильные компоненты - мир, в котором нет фреймворков и либ

На фронт интервью в большие компании, часто дают задачки по типу - "а давай сделаем компонент на ваниле". Многие на этом валятся, так как за годы использования Реакта, Ангуляра, Вью все это забывается.

Сделал в рамках 20-30 минут следующие компоненты для тренировки:

- Sortable Table
- Media Card
- Accordion
- Star Rating
- Carousel
- Tabs

Нужно помнить, у нас не будет никаких бабелей, вебпаков и тд. Только html и js без автокомплишена. Все компоненты найдете в доке в секции Vanila Components. Если есть желание что то добавить, пишите 🙏

🌲 DOM API - шашлык из дом элементов 🥓

Советую повторить основные методы работы с домом. Так как задачки на деревья для фронта - наиболее частые. В основном это задачи с литкода, просто адаптированные под DOM.

💻 Data structure design - боль фронтендера

Для нас важны несколько структур

BST - Binary Search Tree
UF - Union Find aka Disjoint Set
Trie - Prefix Tree

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

Менее важно, больно, но иногда нужно: Priority Queue

♿️ Accesability - делаем веб доступным для всех

Очень важный топик! Особенно, если идете в Google В Амазоне, по опыту коллег, вопросы на эту темы простые. Но, в гугле, просто насилуют! Я серьезно, максимально серьезно!

Вот несколько курсов, чтобы подтянуть эту тему:

1. https://frontendmasters.com/courses/web-accessibility
2. https://frontendmasters.com/courses/javascript-accessibility

💫 Оптимизация и производительность

Моя любимая тема, на работе потратил очень много времени, чтобы привести в порядок перформанс приложения. Тут могу порекомендовать сайт Ивана Акулова. Много контента по оптимизации производительности и разборов реальных юзкейсов. В доке расписал основные моменты.

Вот еще неплохой курс на эту тему

1. https://frontendmasters.com/courses/web-performance/

На этом все, перехожу к финальным этапам 💪:

1. Frontend System Design - честно, не знаю пока как к этому готовиться. Буду искать информацию. Рад любым Вашим предложениям.

2. Behavioral Questions

Всем добра и тепла 🔆

День 154 - Подходим к финалу истории 🏁

Последние 2 недели шлифовал System Design и Behavioral Questions. Разберем по порядку:

✅ System Design

Тут фронтендерам немного легче, чем генералистам. К сожалению, материала почти нет. Нашел хороший пример того, как выглядит System Design для фронтендера. Ниже объясню ключевые особенности

Основной фокус - фронтенд архитектура. Ключевые моменты:

1. Разбивка страница на компоненты
2. Загрузка данных. Где и в каком месте загружаем данные? Как передаем их вниз по дочерним компонентам
3. Дизайн REST API для получения и отправки данных, тут стоит хорошо разобраться с HTTP протоколом, разобрать REST архитектуру. Особенно, отличия HTTP v1 от HTTP v2
4. Оптимизация приложения. Разбивка на ленивые модули. Сжатие и тд.
5. CSS Архитектура - ( подставь любимую методологию )
6. Дизайн Система - не путать с System Design, перед разработкой каждого приложения, мы описываем его Styleguide, используемые компоненты и тд. Следуем ему. Так приложение получается консинстентным. Делать на интервью не нужно, но упомянуть обязательно 😀

Все выглядит очень несложно, так как мы это делаем каждый день. Большинство моментов разобрано во фронтенд доке 💪

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

✅ Прошел следующие курсы:

1. Grokking System Design Interview курс показался очень поверхностным, но для интервью пойдет. Достаточно разобрать базовые принципы и основные термины. Советую сделать упор на популярные приложения - Twitter, Instagram, Facebook. Это хороший пример больших фронт-енд приложений. Хотя в реале facebook ужасен 🤮
2. Design Data Intensive Applications - хорошая книга, прочитал не всю. К сожалению, большая часть того, что написано, приходит с хорошим бэкэндовым опытом. Рекомендовать для чисто фронтендера не могу, так как боюсь, что много вещей применить не получится на практике.
3. Плейлист по RESTfull архитектуре от Java Brains - старенький и есть немного джавы, но неплохой рефрешер

✅ Behavioral Part

Если идете в Амазон, внимательно смотрим 14 Leadership принципов. Я подготовил по 2 истории на каждый. Исходя из моего опыта и опыта знакомых, нужно отнестись к этой части очень серьезно! Проработайте свои истории. Используйте структуру STAR или PAR для ответа на вопрос. Мне помог вот этот ресурс: https://interviewgenie.com/
На каждый принцип, есть пример ответов с разбором.

🔥 С понедельника рассылаю резюме в следующие компании: 🔥

- Amazon AWS ( Vancouver )
- Apple ( Vancouver )
- Microsoft ( Munich )
- Google ( Munich, Swiss )
- Electronic Arts ( Vancouver )
- Facebook ( London )

Опыт интервью буду и примеры задач буду выкладывать в канале, если позовут вообще 😀Посмотрим, что из этого выйдет.

Следующие шаги:
1. Повторяю узкие места фронте
2. Повторяю топ алго задачки на литкод

The War Begins 🔥