Слайд из курса со сравнинем комплексити операций различных имлементаций Symbol Tables

День 43 - Сбалансированные деревья. Красно-черное дерево, B-Trees 🤯

Закончил первую часть теории 5ой недели по сбалансированным деревьям. Теория довольно сложная и потребовала глубокого разбора.
Основные вещи, которые проходятся на неделе:

2-3 Trees
Очень важно разобрать данный вид деревьев, так как они является базой для понимания Красно-Черного дерева на основе деревьев бинарного поиска - Red-Black BST
Имлементировать данную DS не надо. Это займет очень много времени и сил и вы все-равно не запомните, так как операции удаления и вставки, имееют очень много операций трансформаций над деревом. Как, мне кажется, важно запомнить Time Complexity и понять базовый принцип работы структуры.

Red-Black Binary Search Trees
А вот тут стоит подготовить свою нервную систему. Готовьтесь к тому, что придется потратить пару дней для того, чтобы вкурить и понять эту DS. Основный принцип, что мы с помощью BST иммитируем структуру 2-3 дерева и все операции направлены на поддержание данной структуры. Как начать и не сдаться?

1. Берем первую и самую простую операцию - search. Здесь не требуется никаких изменений по-сравнению с обычным BST. Это обычный поиск по бинарному дереву. Имлементим данную операцию.

2. Понять, как связь между двумя линками помечается красной или черной. Посмотреть из теории 2-3 Дерева, что такое 3-node и 4-node. Научиться конвертировать 3-Node в бинарное дерево на листочке.

3. Освоить операции поворота узла влево и вправо (rotateLeft и rotateRight), которые используется для поддержания дерева сбалансированным. Это несложная операция, которая требует проработки на листочке или доске. Пару раз достаточно нарисовать все и будете вертеть узлы как шашлык 😁

4. Учимся превращать воображаемый 4-Node в 2 Node путем смены цвета связей между узлами. flipColors

5. Разбираемся с финальным боссом - insert. Там есть несколько кейсов, каждый кейс стоит разорать на листочке
- 2 левых узла красные h.left == RED && h.left.left == RED ( поворот направо )
- Правый красный, левый черный ( поворота налево )
- Левый и Правый красный ( смена цветов )

Посмотрите, как каждая операция поддерживает структуру нашего красно-черное дерево в виде 2-3 дерева. Как только в голове придет понимание как это все соотносится, будет на много легче ☺️ Я реально страдал, пока разбирался 😭

6. Есть операция, хуже финального босса - это удаление. У Сенджвика написано 2 научных работы о том, как удалять узлы из такого дерева. Лично мне кажется, это то, что можно пропустить и не пытаться разбирать. Алгоритм запомнить очень сложно, много условий, кода и трансформаций. Врятли после курса вы вспомните об этом методе и врятли на собеседовании вас попросят его написать 😁
Если очень интересно, в учебнике Сенджвика есть имлементация этого метода. Я ее даже прочел, но закрыл как страшный сон 🙈
Все предыдущие операции ( вставка. поиск, повороты ) дают 90% базы, о том, как работает данная структура данных, а нам важно умение применять и понимать, что применяешь.

Полезно, но опционально: B-Trees
В курсе также рассказыается про данный вид деревьев, которые активно применяются в базах данная и различных индексах. Для себя нашел эту тему полезной, так как неплохо расширяет кругозор. Сможете по-умничать и сказать, как устроен поиск по индексу в SQL базе данных 😁

Вот полезное видео на эту тему, одного просмотра достаточно для понимания:
https://www.youtube.com/watch?v=aZjYr87r1b8&list=PLDN4rrl48XKpZkf03iYFl-O29szjTrs_O&index=77

Следующие шаги:
1. Geometric Applications of BST - звучит как жара 🔥
2. Последний ассаймент курса 🤯

Stay Tuned 👍

#algorithms_part_1, #bst, #red_black_tree, #week_5

Финальная сравнительная табличка имлементаций Symbol Table

День 48 - Конец 5 недели 🎉🎉

Закончил последний ассаймент 5ой недели курса Kd Trees 🎉. Было интересно.

Небольшое саммари, как подходить ко второй части теории недели и ассайменту 🤔 :

1. Нужно хорошо понимать BST из 4й недели. Если сможете с нуля написать его и реализовать базовые операции, задание не будет сложным

2. К сожалению, курсера содержит старое описание задание. На сайте принстона имеется обновлённая версия и чек лист с частыми вопросами.
Я сразу не догадался поискать его, в итоге типичные проблемы и вопросы пришлось додумывать самому :), а в чеклисте они уже были расписаны.

Ссылка на обновлённое задание:👉
https://www.cs.princeton.edu/courses/archive/spring19/cos226/assignments/kdtree/specification.php

Ссылка на чек-лист:👉 https://www.cs.princeton.edu/courses/archive/fall19/cos226/assignments/kdtree/checklist.php

3. К заданию приложены полезные клиенты визуализаторы Range Selection и Neighborhood Selection. Не поленитесь их скачать и дебажить на них ваш код, очень помогает :)

4. Если что-то непонятно, пересмотрите снова теорию по Kd tree. На следующий день обычно становится понятнее.

5. Реализацию стоит начинать с методов 👉 size, search, insert 👈. Так как в целом, эти методы совпадают с BST и вы быстро их напишите.

6. По началу очень сложно представить в голове деление плоскости, когда добавляем новые узлы в дерево. Стоит проработать это на доске 👨‍🏫 прежде, чем писать код.

Следующие шаги :
1. Неделя 6ая, считается опциональной на курсе, думаю быстренько её пройти и перейти ко второй части курса.

2. Обновить цель на smartprogress, добавить пройденный материалы, расписать следующую половину теоретической подготовки.

Идём дальше 👍

Всем хороших выходных и не болеть 🤭

День 50 - Завершение первого части курса по алгоритмам 🎉🎉🎉

Закончил 6ую неделю курса по алгоритмам. Неделя не содержит никаких заданий и теория относительно простая. На данной неделе рассматриваются хэш-таблицы - еще один вариант Symbol Tables

Если хотите погрузиться в тему, рекомендую следующие материалы👇:

1. Структуры данных в картинках: https://habr.com/ru/post/128017/ , автор потрясающе объясняет детали имлементации хэш-таблиц в джаве. Для фронтендеров, наверное стоит просто разобраться с общей концепцией, но если вы генералист, советую максимально изучить данную серию статей 🤔

2. Плейлист от гугл инжинера, автор подробно рассказывают про теорию, коллизии в таблице, варианты ее разрешения и что не мало важно6 приводит код, который можно посмотреть и зареимплементить, если совсем интересно (ps так и сделал 😊 )
Ссылка: https://www.youtube.com/watch?v=2E54GqF0H4s

Ниже оставляю финальную сравнительную таблицу имлементаций Symbol Tables 💻

Следующие шаги:
1. Обновить цель на smartprogress
2. Начать изучение первой недели

Идем Дальше 💪

Обновил цель на smartprogress. Добавил туда следующие степы по подготовке и материал. Если у вас есть какой-либо полезный материал по темам, присылайте мне, добавим в док 👍

https://smartprogress.do/goal/374957/

День 57 - Графы и геморрой 🙈

Закончил работать над 7ой неделей курса по алгоритмам. Могу сказать, что данная неделя одна из самых сложных пока на курсе. Что проходим?

1. Undirected Graphs
2. Directed Graphs

Теория графов довольно обширная и алгоритмов целая гора. Как мне кажется, материала на курсе не хватает, пришлось брать дополнительно 👨‍🏫 . И так, материал, который я рекомендую для просмотра / прочтения:

Видео с канала гугл инжинера:

1. Введение в теорию графов https://www.youtube.com/watch?v=eQA-m22wjTQ&list=PLDV1Zeh2NRsDGO4--qE8yH72HFL1Km93P

2. Какие проблемы решают графы - https://www.youtube.com/watch?v=87X57ldq1ok&list=PLDV1Zeh2NRsDGO4--qE8yH72HFL1Km93P&index=2

3. DFS - https://www.youtube.com/watch?v=7fujbpJ0LB4&list=PLDV1Zeh2NRsDGO4--qE8yH72HFL1Km93P&index=3

4. BFS - https://www.youtube.com/watch?v=oDqjPvD54Ss&list=PLDV1Zeh2NRsDGO4--qE8yH72HFL1Km93P&index=4

5. BFS on grid - https://www.youtube.com/watch?v=KiCBXu4P-2Y&list=PLDV1Zeh2NRsDGO4--qE8yH72HFL1Km93P&index=5

Как подходить к теории на курсере?
Здесь лучший совет будет - имлементировать следующие вещи самостоятельно:

1. UndirectedGraph и DirectedGraph. Отличий на самом деле минимум. Разница только в том, что в первом варианте графа, вершины связаны в обе стороны всегда.

2. Обход в глубину DFS

3. Обход в ширину BFS

4. Топологическая сортировка

5. Connected and Strongly Connected Components

Не поленитесь и имлементируйте все.


————————————
Ассаймент 7ой недели
————————————
Тут нам предстоит написать свой WordNet, программа по поиску однородных слов.

Как начать? 🤔

1. Обязательно посмотреть в чек лист - https://www.cs.princeton.edu/courses/archive/spring19/cos226/assignments/wordnet/checklist.php . В нем содержится подсказки и частые вопросы по имплементации данного задания. Странно, что опять пришлось его искать самостоятельно. Курсере стоит добавить его в ссылки на ресурсы.

2. Дополнительные разъяснения по заданию, ссылка из чеклиста. Лично мне очень помогли, так как после прочтения задания на сайте, я не понимал, что мне надо в итоге сделать. https://www.youtube.com/watch?v=EtPfujaKHwc&feature=youtu.be

3. Советую начать с парсинга файлов с hypernyms и synsets. Используйте необходимые структуры для хранения. Имлементировать ничего не нужно, используйте пакет java.lang и algs4 либу

Cпойлер: HashMap и Digraph

4. Для определения, зациклен ли граф - можно использовать класс DirectedGraphCycle

5. Далее переходим к SAP - Shortest Ancestor Path. Тут главное не за оверинженирить. Существует популярная на лит коде проблема Least Common Ancestors. Которая фактически повторяет то, что пытаемся сделать мы. Есть несколько решений - динамика - одно из них. Не надо его применять. Мы ограничены структурой данных пакета и от нас ожидают наиболее простое решение - наивное 😂

6. c Outcast сложностей возникнуть не должно, это самая простая часть задания.

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

Next Steps - Leecode ❤️

Разминка:
1. https://leetcode.com/problems/find-the-town-judge/

Основная часть:

1. Topological Sort - https://leetcode.com/problems/course-schedule-ii/

2. Cycle Detection - https://leetcode.com/problems/course-schedule/

3. Check Graph is Bipartite - https://leetcode.com/problems/is-graph-bipartite/

4. Escape Dungeon Problem - https://leetcode.com/problems/escape-a-large-maze/

5. DFS - https://leetcode.com/problems/find-eventual-safe-states/

Идем дальше 💪

День 60 - Решаем литкод 🤔

В связи со временным переездом в другой город ✈️, смог приступить к задачам только сегодня. Решил 4 задачки на графы.

Разобью задачи по типу проблемы:

Немного размяться:

997. Find the Town Judge

Простенькая задачка, чтобы по-упражняться на графах. Комментарии не требуются 😄

Топологическая сортировка и поиск цикла в графе.

1. 207 - Course Schedule
2. 210 - Course Schedule II

Обе задачи сводятся к тому, чтобы топологически отсортировать граф. В первой, просят определить можно ли это сделать, во второй вывести отсортированный массив. Тут надо просто один раз изучить алгоритм топологический сортировки, я взял Kahn's Algorithm, разобрал его и реализовал обе задачи. Алгоритм очень простой 👍

Рисуете все на листочке или доске, проделываете каждый шаг. Так хорошо запоминается и укладывается все в голове.

Определение двудольного графа ( Bipartite Graph )

785. Is Graph is bipartite

Интересная задачка. Тут просто нужно разобраться что такое Bipartite Graph и как он выглядит.

Поможет: https://www.geeksforgeeks.org/bipartite-graph/

У меня ушло примерно по 30-40 минут на каждую задачу. Но сейчас, скорость решения не преследую, главное закрепить теоритический материал.

Что дальше ? 🙈
1. https://leetcode.com/problems/escape-a-large-maze/
2. https://leetcode.com/problems/find-eventual-safe-states/

Всем stay home и не болеть, сейчас это актуально, как никогда 💪

День 62 - Закончил решать задачки на графы ☄️

Сегодня решил 2 задачки:

1036 - Escape a large maze ( hard 🤔 )
Задача хоть и с пометкой - hard, но не является сложный. Перед нами Dungeon Problem aka Maze. - матрица миллион на миллион. Нам нужно понять, можно ли найти выход. Основная сложность, оптимизировать, чтобы не искать путь полностью и выбрать правильные эвристику для оценки

Если сложно, помогут вот эти ссылки. Там нет решения задачи, скорее полезный материал👇:
1. https://www.youtube.com/watch?v=KiCBXu4P-2Y&list=PLDV1Zeh2NRsDGO4--qE8yH72HFL1Km93P&index=5 - BFS on grid
2. https://cs.stanford.edu/people/abisee/gs.pdf - Презентация стенфорда рассматривающие основные алгоритмы поиска путей

Ну и на крайний случай, ссылка на мое решение на JS с комментами:
https://leetcode.com/problems/escape-a-large-maze/discuss/561992/Javascript-BFS-solution-with-explanation

802. Find Eventual Safe States

Тут отрабатывается стандартный DFS. Задача показалась не очень сложной. Ссылка на решение:
https://leetcode.com/problems/find-eventual-safe-states/discuss/562069/Easy-to-understand-Javascript-solution

В общем, после решение набора задачек на графы, чувствую себя на много увереннее в теме. Готов приступать к 8 Неделе курса по алгоритмам 💪

Следующие шаги:
1. Начать 8 неделю курса
2. Обновить материалы на smartprogress

Всем хороших выходных 👍

День 67 - Конец теории 8ой недели - Часть 1 🤔

Закончил изучение теории 8ой недели - Shortest Paths, Minimum Spanning Tree. Неделя очень насыщенная и интересная в плане теории.

Разберем каждую тему по порядку👇

Minimum Spanning Tree
Тут Сенджвик дает нам intro в Greedy 👨‍🏫 алгоритмы, которое мне показалось совсем недостаточным чтобы понять основную концепцию.

Отличное пояснение дает Abdul Bari вот здесь👇
https://www.youtube.com/watch?v=ARvQcqJ_-NY&list=PLDN4rrl48XKpZkf03iYFl-O29szjTrs_O&index=40&t=0s

Далее разбираются основные алгоритмы для нахождения Minimum Spanning Tree - далее MST.

Kruskal's Algorithm
На практике, довольно простой алгоритм. Советую имлементить его в ходе прохождения курса.

Чтобы максимально эффективно разобраться с ним, нам понадобится👇

1. Знание структуры Union Find прямиком из 1ой недели - используется, для того того чтобы эффективно понять, что вершина уже в MST
2. Знание приоритетной очереди - Priority Queue из 4ой недели - Сортирует ребра по весу
3. Имлементация взвешенного графа. Единственное отличие от обычного - ребро представляется в виде объект Edge(v,w,weight).
4. Сам алгоритм - Сенджвик довольно понятно его объясняет.

Полезный материал, который поможет👇
https://www.youtube.com/watch?v=4ZlRH0eK-qQ&t=700s

Prims's Algorithm - lazy version
Отличается от Крускала тем, что тут мы начинаем с 0 вершины и идем по графу по соседним вершинам, кладя ребра в приоритетную очередь. Требования к знаниям такие же как в случае с Крускалом. Имеет один drawback, для того, чтоы обновить вес ребра, приходится класть в MinPQ дубликат. Фиксится с использованием eager версии алгоритма.

Полезный материал👇
1. Prim's explanation https://www.youtube.com/watch?v=jsmMtJpPnhU&t=193s
2. Abdul Bari example https://www.youtube.com/watch?v=4ZlRH0eK-qQ&t=700s

Prims's Algorithm - eager version 😳
А вот тут я немного приуныл. Алгоритм несложный, основное отличие, что мы избегаем хранения дублируемых ребер, которые кладем в приоритетную очередь, путем использования IndexPriorityQueue 🤯. Это небольшое расширение над обычной PQ, которая позволяет нам эффективно изменять приоритет элементов, которые мы храним в ней.

Странно, что Сенджвик не разбирает это на 4 неделе. Для того, чтобы полностью понять, как все работает, советую самостоятельно ее заимплементить. Потратьте на это время, очень поможет!

Материал для погружения👇
1. Index PQ https://www.youtube.com/watch?v=DT8xZ0Uf8wo
2. Prims Eager version - https://www.youtube.com/watch?v=xq3ABa-px_g

Конец 1 части 👨‍🏫

День 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

Не болеем 💪