Ну вот и закончилась первая неделя курса алгоритмов на курсере 🎉. Сегодня разобрал тему 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 и повторю материал.

День 23 - Collinear Points

Закончил изучать теорию по рекуррентным отношениям 🤓. Основная сложность в том, чтобы просто прорешать эти уравнения для 3ех видов рекурсивных функций:

1. Decreasing Function - T(n) = T(n -1) + f(n)
2. Dividing Function - T(n) = T(n / 2) + f(n)
3. Root function - T(n)= T(sqrt(n)) + f(n)

После изучения материала, теперь очень легко определять Time Complexity для любых рекурсивных алгоритмов. Думаю усилия стоили того. Также разобрал Master Theorem для этих функций. Скажу так, штука полезная, но запоминать это не надо :) В каждом случае, довольно несложно написать recurrent relation и решить его одним из возможных методов:

1. Tree Trace ( строим дерево вызовов и выводим сложность)
2. Substitution ( Решаем уравнение )

Сегодня перешел к заданию 3й недели Collinear Points. Брутфорсный солюшн написал за полчаса. А вот, эффективный с использованием алгоритма сортивроки точек, пока не осилил, не проходят все тест кейсы. Думаю вернусь к проблеме еще завтра на свежую голову и попробую решить 🤯

А пока, идем дальше 👊

День 30 - Конец ассаймента 3 недели

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

Закончил задание Colininear Points. Очень неприятное :)

Небольшое summary:
1. Вообще не понравилось 😭
2. Пришлось потратить много времени, чтобы прийти к алгоритму для решения задачи. Вот что у меня вышло:

1. - Представляем, что каждая точка является началом только одного сегмента
2. - Проходимся циклом по точкам
2.1 - Берем точку p[i]
2.2. - Сортируем точки в порядке увеличения угла, создаваемого с точкой p[i]
2.3. - Бахаем еще один цикл, исключая первую точку , так как она в отсортированном массиве является точкой, относительно который мы сортируем его
2.3.1 - В список кладем точку p[j] если пустая, если нет, сравниваем последнюю из списка точку и текущую по углу, который они создают с p[i]. Если он одинаковый - наши точки находятся на одной линии. Кладем текущую точку в список.
2.3.2 - Как только у нас набралось 3 и более точки в списке и мы не имеем больше точек с одним углом, мы можем сотворить сегмент.

Чтобы избежать дубликатов, во время прохода в циклt, мы представили, что каждая точка, является началом только одного сегмента, значит у нас есть только один минимум. Пока мы проходим все точки в двойном цикле, у нас будут встречаться саб-сегменты, которые нужно исключить. Пример:

A - B - C - D, на первой итерации origin = A, это минимальная точка, а D максимальная. Значит наш сегмент - (A,D)
Следующая итерация :
A - B - C - D, но теперь origin = B, и это не минимальная точка и мы не можем добавить сегмент (B, D)

Что делаем?
Кладем в список все колинеарные точки, пример (D,C, B) , origin - A. Сортируем список - получаем (B,C,D) . Если origin меньше чем первый элемент списка - значит он является началом сегмента и мы добавляем сегмент в результат. В случае, если бы origin = B, B не меньше чем A, и это значит, что нам встретился дубликат.

В общем, получилось набрать 100 / 100 Вроде и несложно, но времени заняло порядочно 😔

Завтра хочу закончить 3ую неделю и перейти к 4ой 🤯

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

День 32 - Начало 4ой недели

Закончил полностью 3 неделю курса, повторил весь прошлый материал. Все-таки конспект очень хорошо помогает в этом 😁

Summary недели:
1. Изучены Quick Sort & Merge Sort - для полнейшего закрепления, рекомендую следующие видео:
https://www.youtube.com/watch?v=7h1s2SojIRw&list=PLDN4rrl48XKpZkf03iYFl-O29szjTrs_O&index=36
https://www.youtube.com/watch?v=mB5HXBb_HY8&list=PLDN4rrl48XKpZkf03iYFl-O29szjTrs_O&index=34
2. Сделал небольшой dive deep в recurrent relations 🤓. Об их важности для понимания алгоритмов Divide & Conquer уже писал не раз.
https://t.iss.one/frontend_engineer_blog/28 👈 вот тут вместе с материалом, который стоит изучить
3. Выполнил курсеровский ассеймент 🤯
4. Повторил материал прошлых недель

Следующие шаги:
1. Изучение 4ой недели курса
2. Поиск хороших дополнительных материалов
3. Немного литкода на тему Priority Queue

Идем дальше 👊

Табличка базовых сортировок со 2ой и 3ей недели курса

День 35 - Priority Queues. Binary Trees, Heap, HeapSort 🤔

Закончил изучение первой части теории 4ой недели курса. В целом, все понравилось и было относительно несложно, но пришлось дополнить обучение парочкой видео. Чтобы быть молодцом и понять первую часть теории, нужно:

1. Разобраться с бинарным деревом . Понять термины - Full Binary Tree, Complete Binary Tree.
2. Написать PriorityQueue просто на основе неупорядоченного массива 👩‍💻
3. Затем перейти к теме хипа. Нарисовать операции вставки / удаления в дерево на листочке / доске / конспекте 🤓 Только так можно понять и запомнить алгоритм.
4. Заимлементить BinaryHeap (thanks cap)
5. Далее стоит разобраться с преобраованием обычного массива в хип. Метод называется heapify. Если получилось сделать все предыдущие пункты, то эти 3 строчки кода напишутся очень быстро
6. Перейти к HeapSort. Сама сортировка элементарная, но нужно понимать все предудыщие пункты.

Вот материалы, которые стоит посмотреть, если будете браться за топик:
1. Abdul Bari’s (каждый раз думаю, огонь мужик ) - https://www.youtube.com/watch?v=HqPJF2L5h9U&list=PLDN4rrl48XKpZkf03iYFl-O29szjTrs_O&index=33&t=0s
2. Google Engineer videos 14-19 https://www.youtube.com/watch?v=wptevk0bshY&list=PLDV1Zeh2NRsB6SWUrDFW2RmDotAfPbeHu&index=14

Следующие шаги:
1. Сделать ассаймент на курсере - 8 Puzzle.
2. Перейти ко второй части теории этой недели.

Приятных выходных ☺️

День 39 - Конец ассаймента 4ой недели.

Бурные праздничные дни прошли 😁 Сегодня закончил задание 4ой недели - 8-puzzle. Задание оказалось на много проще 3ей недели 🤔. Основная задача, воспользоваться Priority Queue и заимлементить алгоритм для поиск оптимального пути A*. Сам алгоритм неплохо расписан в задании, поэтому сложностей с его имлементацией возникнуть не должно.

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

Также почти закончил со второй частью теории недели - Symbol Tables. Завтра осталось повторить несколько моментов и можно двигаться дальше 👊