Сегодня начал первую неделю курса принстона по алгоритмам. Единственный пока минус курса - язык программирования. К сожалению, курс привязан только к Java. Выполнить ассайменты на своем любимом языке не получится. Я не писал на джаве почти 2 года, но в целом полезно прослезится и тряхнуть старяной, особенно после JS и TS 🙂

План на неделю:
1. Изучить теорию по Union Find
2. Заимлементить DS c описанными подходами на Java
3. Просмотреть видосы по данной теме от гугл инжинера
4. Выполнить финальный ассаймент
5. Выжить и дальше вставать в 6 утра

Полезные ссылки стараюсь добавлять в цель на smartprogress.

Stay Tuned 🙏

2 день подготовки - 6.30 am 🙊

7.00 am - 10.00 am - Закончил еще одну секцию курсеры по Union-Find. Немного пришлось подумать про Weightening и Path Compression. В голове не сразу улегся подход.

Понял, чтобы лучше осваивать топики 🙄:

1) Имлементим каждый подход самостоятельно, не смотрим на решение, пока совсем не застряли до полного отчаяния 👨‍💻
2) Полезно просматривать уже прочитанный материал. Легче дается изученное. Даже если что-то сразу не получается, на следующий день идет на много проще.
3) Делать заметки - полезно. Особенно, когда их смотришь на следующий день

Завтра:
1) Повторю весь материал
2) Посмотрю видосики от гугл инжинера по Union-FInd
3) Попробую начать недельный ассаймент на курсере

Stay Tuned 🙏

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

День 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) Наклеить стикеры на доску с задачами, с кратким решением

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