Иллюстрация, я и ассаймент курсеры с первого подхода:

День 4 - Первый ассаймент 👨‍💻

Начал привыкать вставать в 6.30. Хотя еще тяжело 🙄. Сегодня добрался до ассаймента первой недели на курсере. За 2 часа получилось сделать первую версию, которая конечно же не прошла все грейдер чеки 🤔.

Следующий шаг:
1) Таки исправить задание, чтобы пройти минимум 95% проверок
2) Повторить материал и чекнуть видео гугл инжинера на тему Union-Find

День 5 - Конец первого ассаймента 🤔

Закончил править тесты для первого ассаймента на курсере. Поэтому позволю себе немного рефлексии на тему топика. Чтобы успешно выполнить задание первой недели - Percolation Problem, надо:

1) Максимально разобраться в такой структуре как Union Find. Разобрать каждый подход и обязательно заимплементить (кэп 🙂). Особенно взвешивание (weightening) и компрессию путей (Path Compression)👨‍💻
Поможет:
-> Видяшки от гугл инжинера. Отлично дополняют теорию первой недели. Плюс визуально приятно воспринимаются
https://www.youtube.com/watch?v=ibjEGG7ylHk&list=PLDV1Zeh2NRsBI1C-mR6ZhHTyfoEJWlxvq

2) Пробежать конспект, который записали по первой неделе

3) Заиимплементить первую версию API. Затем глянуть тесты, игнорируя кейсы с backwash problem. Пофиксить все и далее начинать разбираться с backwash. (о ней ниже) 👇

4) Есть проблема , с которой обязательно столкнетесь решаю задачу по Percolation. Называется “backwash”. Суть в том, что когда система перколирует - (нижняя граница связывается с верхней), элементы, даже закрытые и не соединные с открытыми компнентами, становятся заполненными (full site), из-за того, что присоединены к нижней вирутальной границе. Картиночка ниже.

Есть несколько решений данной проблемы:
1) 2ой инстанс UF (простое) 👍
2) Битовое состояние клетки (сложное, но более эффективное)💪

Оба способа дадут 100 баллов. Удачи в нелегком пути !)

А мы двигаемся дальше.

Напоминаю, что я еще веду цель вот тут, там только инфа по собесу:
https://smartprogress.do/goal/374957/

Там я пытаюсь структуризировать весь материал в ходе подготовки. Надеюсь , в итоге потом можно будет собрать “план”, по которому можно готовиться.

Stay Tuned 🙏

Ну вот и закончилась первая неделя курса алгоритмов на курсере 🎉. Сегодня разобрал тему Analysis of algorithms: Time and Space complexity.

На самом деле, это очень важный топик и хорошо, что он разбирается на первой неделе курса. Но, к сожалению, мне кажется информация , которая представлена в курсе, немного суховатая и очень теоритическая 🤔. Не хватает практических примеров, чтобы закрепить материал. Хорошо, что нашел прекрасного чувака, который на пальцах объясняет топик, как правильно пользоваться натацией Big O. Что такое lower and upper boundary, и почему Big Theta и Bit Omega нельзя применять к оценке worst and best case

Videos 1-16 - https://www.youtube.com/channel/UCZCFT11CWBi3MHNlGf019nw/playlists

Следующие шаги:
1) Повторить пройденный материал, решить 2 медиум задачки с литкода по union-find
2) Подготовиться ко второй неделе курса, отдохнуть и в бой 💪

Stay Tuned 🙏

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

Очень помогает перезагрузить мозг и восстановить силы.

План на завтра 🙃 :
1) Повторить материал по Algorithm Analysis
2) Закрыть первую неделю плана
3) Подготовить часть материала к фронтендовой конфе в СПб
4) Решить одну задачку по Union Find с плана следующей недели, если останется время

Ну вот и конец первой недели плана подготовки 🎉.
Краткая выжимка всего материала:

1) Coursera - Week 1

Union-Find - Path Compression / Weighting
Algorithm Analysis - Time and Space Complexity
Percolation Assignment

2) Полезный материал, который использовался для заркелпения темы:

Videos 1-16 - https://www.youtube.com/channel/UCZCFT11CWBi3MHNlGf019nw/playlists- videos by Abdul Bari. (Algo analysis, disjoint sets)
Google Engineer videos on Union Find


Поехали дальше 💪

На следующей неделе, выделю 3 дня на литкод и закрепления материала. Далее перейду к стеку, очередям и базовым сортировкам

День 9 - Leetcode time👨‍💻

Начал решать medium задачку на тему UF - https://leetcode.com/problems/regions-cut-by-slashes/
Не смог ее решить с первой попытки 🙄, но с голове сформировалось корректное решение. Завтра утром вернусь к ней и надеюсь закончу с ней. В плане, решить 2-3 задачи на UF и двинуть ко второй неделе на курсере 💪.

День - 10

Решил задачку - https://leetcode.com/problems/regions-cut-by-slashes/ 🎉

В первом решение наделал много ошибок, пришлось все трейсить на листочке. Стараюсь избегать IDE, когда ищу решение задачи. Не думал, что мне потребуется в сумме на “medium” 5 часов 🙄, это довольно много. Решил взять еще одну задачу на топик. Сейчас планирую отрефакторить текущее решение, пошарить на гит и литкод форум. Также добавлю подробные объяснения к задаче 🙂

План дальше:
1) Рефакторю текущее решение 🙈
2) Выкладываю на литкод, гитхаб
3) Пишу подробное объяснение 🤔
4) Беру следующую задачку 😱

Stay Tuned 💪

День 11

Запостил решение задачки на leetcode форуме -https://leetcode.com/problems/regions-cut-by-slashes/discuss/506740/Javascript-Verbose-DSU-%2B-Path-Compression-solution

Space Complexity - O(N^2)
Time Complexity - O(N*N*a(N)) - на самом деле, первый раз я посчитал это неправильно, в случае DSU (aka Union Find) с применением Path Compression и Weighing для оценки применяется обратная функция аккермана a(N).

Если хотите погрузиться в топик вам сюда -
1) https://habr.com/ru/post/266859/
2) https://neerc.ifmo.ru/wiki/index.php?title=%D0%A1%D0%9D%D0%9C_(%D1%80%D0%B5%D0%B0%D0%BB%D0%B8%D0%B7%D0%B0%D1%86%D0%B8%D1%8F_%D1%81_%D0%BF%D0%BE%D0%BC%D0%BE%D1%89%D1%8C%D1%8E_%D0%BB%D0%B5%D1%81%D0%B0_%D0%BA%D0%BE%D1%80%D0%BD%D0%B5%D0%B2%D1%8B%D1%85_%D0%B4%D0%B5%D1%80%D0%B5%D0%B2%D1%8C%D0%B5%D0%B2)

Но если в кратце, обратная функция аккермана, это функция, которая с увеличением N растет очень медленно, что в теории, позволяет нам сказать, что это почти O(1). Я бы не стал глубоко закапываться в мат. анализ, поэтому двигаем дальше 😁


Следующий шаг: решим задачку на тот же топик. friends circles - https://leetcode.com/problems/friend-circles/

Подробное описание решений к обеих задач постараюсь выложить к выходным.

Stay Tuned 🙏

День 12

Продолжил решать leetcode. Сегодня за 2 часа смог решить 3 medium задачки на Union FInd 💪. Мне они показались сильно проще, чем первая, В целом, чувствую, что этого хватит и можно начинать вторую неделю на курсере.

Вот эти задачки:
1) https://leetcode.com/problems/friend-circles/
2) https://leetcode.com/problems/redundant-connection/
3) https://leetcode.com/problems/most-stones-removed-with-same-row-or-column/

Задачи показались очень простыми 👨‍💻. Основная задача в них заимплеменить Disjoint Set и пройтись циклом по входным данным. В этом плане задача из 11 дня показалась на много интереснее.

Следующие шаги:
1) Доделать подробное описание задачи Regions Cut By Slashes
2) Пробежаться глазми по всему, что решил.
3) Наклеить стикеры на доску с задачами, с кратким решением

Думаю в субботу уже смогу начать проходить вторую неделю. Пока идем точно по плану 🙂

День 14.

Начал проходить следующую неделю на курсере. Тема: Stack and Queues, Elementary Sorts 👨‍💻. Планирую закончить данную неделю быстрее, так как хорошо знаком с топиком. Буду также дополнять материал, если попадется что то интересное в процессе.

Планы на ближайшие дни:
1) Закончить теорию по стекам и очередям
2) Выполнить ассаймент на курсере
3) Поработать над материалом для конференции по фронтенду.

Приятных выходных 🙏

День 15 - Время второго ассаймента 👨‍💻

Закончил тему стека и очередей. Вообще довольно простая неделя курса. Мне никакой дополнительный материал не понадобился. Из советов:
1) Имлементить в процессе просмотра теории каждый вариант очереди и стека (на связном списке, массиве)
2) Складывать все имплементации в папочку недели. Они потом понадобятся в процессе ассаймента.
3) Если вы никогда не писали на джаве, то немного почитать про интерфейсы Iterator и Iterable. Как они применяются для итерирования по коллекции, можно глянуть внутренние имлементации.

Для ассаймента:
1) Deque - использовать двусвязаный список.
2) RandomizedQueue - массив.

Для имплементации RandonizedQueue нужно ресайзить массив, как было показано в лекциях, для того, чтобы иметь всегда оптимальный размер и не хранить лишние референсы. Чтобы вытаскивать рандомный элемент из массива и при этом избежать дырок, я использовал следующий простой алгоритм:
1) Берем элемент по рандомному индексу 🤷
2) Запоминаем его 🤔
3) Меняем местами с последним элементом
4) Удаляем последний элемент 💥

Так как нам не важен порядок в массиве, это вполне валидный способ. Для имлементации итератора, я просто внутри итератора создал еще один инстанc структуры и отдавал рандомный элемент.

*По итогу*: 100 / 100 💪

Из дополнительного, курс заставляет считать Space Complexity и на это есть тесты. Поэтому стоит 1 раз разобраться как считать место. Ниже приведу пример:

public class Deque<Item> implements Iterable<Item> {
    // 16 Bytes - Object overhead

    private int length = 0;         // 4 bytes
    private Node first, last;       // 8 + 8 = 16 bytes ref overhead

    private class Node {
        // 16 overhead (object) + 8 bytes for inner class = 24
        private Item data;          // 8 bytes (ref)
        private Node next;          // 8 bytes (ref)
        private Node prev;          // 8 bytes ref
        // Total overhead = 24 + 8 + 8 + 8 = 48 * N (elements)
    }

Из примера ниже получаем:

48N + 16 ( obj ) + ( 8 + 8 ) (refs) + 4 (int) + 16 ( iterator ) + 8 ( inner class iterator ) = 48N + 60

Что укладывается в рамки задание

N <= 48n + 192 bytes

Далее:
1. Следущая часть курса. - Elementary Sorts

Stay Tuned 💪

День 16 - Конец 2ой недели принстонского курса 🎉🎉🎉

Сегодня закончил разбор простейших сортировок (selection, insertion, shell). Вообще данная неделя курса отличается относительной простотой ассаймента и материала. Из интересного - пришлось немного разобраться с сортировкой Шелла. Хотя она не сильно отличается от обычной вставками.

Так как неделю закончил на 5 дней быстрее. Порешаю немного задачек на литкоде на тему очередей и стека.

Следующие шаги:
1) Решить 3 medium и 3 easy задачки на стек и очереди.
2) Повторить материал недели
3) Перейти к 3ей неделе

Идем дальше 💪

День 17 - Литкодим 👨‍💻

Сегодня ничего необычного. Решал задачи на литкоде на тему стека. Всего решил 4 задачи - 2 medium | 2 easy. 4 задачи решил за 40 минут, а вот 5ая меня нагнула 🤯🤯🤯. И я сидел почти 3 часа, смотря на доску, пытаясь найти решение. В итоге нашел, но решил завтра ее пересмотреть.

Завтра снова порешаю литкод и думаю приступить к 3ей неделе курса по алгоритмам.

Литкодим дальше 🤓

День 19 - Приступил к 3ей неделе 🚂

Закончил решать литкод. Решил дополнительно 2 medium задачи. В этот раз справился чуть меньше, чем за час. Думаю, пока хватит и пора приступать к следующей неделе курса по алгоритмам 🙂

Небольшое summary:
1. Изучена 2ая неделя ( Элементарные сортивроки, стек. очередь)
2. Решено 3 medium и 3 easy задачки на тему стека и очередей
3. Решен ассаймент от курса по алгоритмам ( 100 / 100 )

Задачки были несложные, главное сразу уловить подход. Возможно правильнее было бы решать их по frequency. Но так как пока литкод не основной фокус, премиум не беру.
Сложностей с данной темой, думаю, возникнет мало. Мне показалось, что тема Disjoint Set и его применения, была более интересной, так как на нее нужно было потратить больше времени и сил. Особых рекомендаций и замечаний сделать на этой неделе не могу.

Список решенных задачек:
1. Baseball Game - 682
2. Daily Temperature - 739
3. Minimum Add to make Parathenses valid - 921
4. Remove outmost parentheses - 1021
5. Remove All adjacents duplicates in string - 1047
6. Minimum remove to make parentheses valid - 1249

По номеру их можно легко найти на литкоде.

Планы на следующий этап:
1. Закончить 3 неделю курса и выполнить ассаймент ( там он будет достаточно противный 🙄)
2. Сделать сравнительную табличку по сортировкам
3. Посмотреть задачи на литкоде, если они есть на эту тему

Поехали 🚅

Сегодня мне написал рекрутер из Google 🙄

Сказать, что я не готов, это ничего не сказать. Так как интервью проходить сейчас бесполезно, вежливо договорился с рекрутером вернуться к этой теме ближе к лету.

Но было приятно 🙂

День 20 - Много-много теории 🤯🤯🤯

Посмотрел видео по Merge Sort у Сенджвика. Сама сортировка объясняется очень хорошо, но все же я считаю, что на неделе курса упущены важные моменты для понимания темы, а именно:

1. Merge Sort относится к алгоритмам Divide and Conquer 👊. А значит, было бы хорошо объяснить, что это за тип проблем и почему оно так называется.

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

Каждый разгруженный вагон - дает вам результат s1,s2,s3,s4 . Соединив результаты, вы получается разгруженный состав = решенная проблема.

Тоже самое и с данными, у вас есть массив данных. Вам надо его отсортировать. Мы делим массив на под массивы и сортируем уже их. Полученные под-решения, объединяем.

2. Все проблемы Divide & Conquer - рекурсивные 👨‍👦‍👦 . А это значит, что для правильной оценки алгоритма и его понимания нам нужны
Рекурентные отношения прямиком из дискретки ( ага, 2ой курс универа ) 🥺 . В теории недели они используются, но не объясняются. Поэтому понять Time Complexity не так просто.

3. Надо ли разбираться? Надо! 🤓 Но глубоко ли? Нет! Достаточно разобрать базовые вещи для того, чтобы понимать следующие алгоритмы:
1. Binary Search
2. min/max search
3. Merge & Quick Sort
4. Strassen Matrix Multiplication

Для избрал такой путь:
1. Изучить видео 18-29 вот из этого плейлиста https://www.youtube.com/watch?v=4V30R3I1vLI&list=PLDN4rrl48XKpZkf03iYFl-O29szjTrs_O&index=19

Чувак от бога просто объясняет все. Где ты был в моем универе 😭
2. Далее перейти к Quick Sort
3. Выполнить ассаймент курсеры

Вот и все пока. Жарим дальше 🔥🔥

День 21 - Recurrent Relations

Потратил почти 3 часа для того, чтобы разобраться с рекуррентными отношениями и анализаом рекурсивных алгоритмов. Дошел до Masters Theorem и понял, что я все 🤯. Завтра буду пересматривать часть материала по этой теме.

Сегодня хочу закончить с курсеровской теорией по Merge Sort и приступить к ассайменту. Завтра досмотрю видосы по Masters Theorem и повторю материал.