Последний курс по алгоритмам, который вам понадобится

Добро пожаловать на суперувлекательный, удобный для начинающих курс по структурам данных и алгоритмам. Действительно ли это последний курс по алгоритмам, который вам понадобится? Если вы хотите пройти сложные вопросы на собеседовании, то да! Вы узнаете о временной сложности big o, фундаментальных структурах данных, таких как массивы, списки, деревья, графы и карты, а также алгоритмах поиска и сортировки.

Этот курс и другие подобные ему доступны в рамках нашей видеоподписки Frontend Masters.

Введение

Введение

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

Основы

Временная сложность Big O

ThePrimeagen обсуждает обзор Big O, включая, что это такое, почему он используется, и некоторые основные понятия. В этом сегменте также приводится пример кода Big O.

Структура данных массивов

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

Вопросы и ответы по массивам

ThePrimeagen отвечает на вопросы студентов о том, не существует ли в массиве операций insert, push или pop, и нужно ли указывать размер массива и распределение памяти при инициализации. Вопросы о том, создается ли что-то, имеющее массив, при создании массива в JavaScript и насколько велик массив, который инстанцируется, также рассматриваются в этом сегменте.

Поиск

Линейный поиск и настройка ката

ThePrimeagen обсуждает поиск по массиву с помощью алгоритма линейного поиска. В этом сегменте также рассматривается настройка TypeScript-библиотеки Kata и описание реализации алгоритма линейного поиска.

Алгоритм бинарного поиска

ThePrimeagen демонстрирует алгоритм поиска, который прыгает вперед на десять процентов, обсуждает возможные подводные камни этого поиска и показывает, чем отличается алгоритм бинарного поиска. Двоичный поиск – это эффективный алгоритм для нахождения элемента из отсортированного списка элементов.

Псевдокод бинарного поиска

ThePrimeagen рассказывает о создании и реализации в псевдокоде алгоритма двоичного поиска.

Реализация бинарного поиска

ThePrimeagen демонстрирует реализацию алгоритма двоичного поиска на TypeScript и использует машину kata для проверки правильности алгоритма. Алгоритм двоичного поиска многократно уменьшает вдвое часть отсортированного списка, которая может содержать целевой элемент, пока возможные места не будут сужены до одного.

Проблема двух хрустальных шаров

ThePrimeagen обсуждает варианты решения задачи

ThePrimeagen рассказывает о реализации решения задачи о двух хрустальных шарах. В этом фрагменте также рассматриваются вопросы студентов о путешествиях с использованием кубического корня из N.

Сортировка пузырьков

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

Реализация пузырьковой сортировки

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

Структуры данных связного списка

ThePrimeagen обсуждает обзор структур данных связанных списков, включая реализацию удаления и вставки. В этом фрагменте также рассматривается вопрос студента о том, нет ли индекса в связанном списке.

Сложность связанных списков

ThePrimeagen обсуждает временную и пространственную сложность связанных списков. Вопрос студента о вставке F также рассматривается в этом сегменте.

Очередь

ThePrimeagen обсуждает функцию очереди, линейной структуры данных, которая следует принципу “первым пришел – первым ушел” (FIFO). Очередь поддерживает такие операции, как peek, enqueue, dequeue и print().

Реализация очереди

Вопросы и ответы по очереди

ThePrimeagen отвечает на вопросы студентов о том, означает ли отсутствие хвоста отсутствие узла, разъясняет метод peek и почему this.tail.next устанавливается на новый узел.

Стек

ThePrimeagen демонстрирует линейную структуру данных, которая следует принципу Last In First Out, противоположную очереди – стек. В стеке последний элемент, помещенный внутрь стека, удаляется первым.

Реализация стека

Массивы

Массивы и связный список

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

ArrayList

ThePrimeagen демонстрирует возможность написания операций со списками, таких как get, push и pop для массивов, используя ArrayList.

ArrayBuffer

ThePrimeagen обсуждает объект ArrayBuffer, который используется для представления общего буфера необработанных двоичных данных фиксированной длины.

Вопросы и ответы по структурам данных

ThePrimegen проводит эмпирический тест на то, какая структура данных используется под капотом с помощью `const a = []`. Вопросы студентов о том, являются ли сдвиг и сдвиг экспоненциальными, какой тип операции является slice, и где это может использоваться в практическом коде, также рассматриваются в этом сегменте.

Рекурсия

Рекурсия

Рекурсия

Поиск пути: Базовый случай

ThePrimeagen рассматривает пример поиска пути с использованием базового случая, реализуя и тестируя пример MazeSolver в машине kata.

Поиск пути: Рекурсивный пример

Вопросы и ответы по рекурсии

ThePrimeagen отвечает на вопросы студентов о том, что происходит, когда рекурсивная функция больше не может двигаться вперед, как был найден конечный путь MazeSolver, и есть ли сценарии, в которых изменение направления рекурсии улучшит производительность.

Быстрая сортировка

Алгоритм быстрой сортировки

ThePrimeagen обсуждает алгоритм QuickSort как алгоритм, использующий технику “разделяй и властвуй”. Алгоритм выбирает поворотный элемент и перестраивает массив так, что элементы, меньшие, чем поворотный элемент, перемещаются в левую сторону от поворотного элемента, а элементы больше – в правую сторону. Затем алгоритм рекурсивно сортирует подмассивы слева и справа от поворотного элемента.

Реализация QuickSort

ThePrimeagen рассказывает о реализации и тестировании алгоритма QuickSort в машине kata. В этом сегменте реализованы как функция QuickSort, так и функция разбиения.

Двусвязный список

Связный список: prepend, insertAt и append

ThePrimeagen рассказывает о реализации дважды связанного списка, включая функции prepend, insertAt и append.

Связанный список: remove, get и removeAt

ThePrimeagen рассказывает о реализации второй половины двусвязного списка, включая remove, get и removeAt.

Вопросы и ответы по связному списку

ThePrimeagen отвечает на вопросы студентов об использовании VIM, о том, приведет ли установка remove undefined к поломке, откуда взяты методы, а также о причинах использования методов Java.

Отладка связанного списка

ThePrimeagen рассказывает об отладке функции remove части дважды связанного списка. В этом фрагменте также рассматривается вопрос студента о примере отслеживания удаленных узлов.

Деревья

Обзор деревьев

ThePrimeagen обсуждает обзор более продвинутых структур данных, известных как деревья, и рассматривает некоторые термины на примере доски. Дерево может быть пустым, без узлов, или дерево может быть структурой, состоящей из одного узла, называемого корнем, и нуля или одного или более поддеревьев.

Обходы деревьев

ThePrimeagen обсуждает и демонстрирует на доске посещение узлов с помощью трех типов обхода – до, после и после.

Реализация обхода дерева

ThePrimeagen в реальном времени кодирует три типа обхода деревьев. Обход в порядке следования обходит одно поддерево узла, посещает узел, а затем обходит другое его поддерево. Предварительный обход посещает узел, а затем обходит оба его поддерева. Послепорядковый обход обходит оба поддерева узла, а затем посещает узел.

Древовидный поиск

Поиск по принципу Breadth-First

В ThePrimeagen обсуждается использование структуры данных очереди для выполнения поиска в порядке возрастания и время работы.

Реализация поиска в порядке возрастания

ThePrimeagen показывает, как реализовать поиск по принципу “вперед-назад” на двоичном дереве, проталкиваясь в очередь вместо рекурсии. В этом фрагменте также проводится краткое обсуждение предпочтений студентов в выборе метода поиска в глубину и в ширину.

Практика поиска

ThePrimeagen рассматривает пример вопроса интервью, в котором сравнивается содержимое и форма. Поиск в глубину сохраняет форму дерева, а поиск в ширину – нет.

Реализация сравнения двоичных деревьев

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

Поиск в глубину: Найти

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

Поиск по глубине: вставка

ThePrimeagen пишет псевдокод для демонстрации вставки в двоичное дерево и показывает, что делать в нулевом случае.

Глубина-первая: Удалить

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

Вопросы и ответы по бинарному дереву поиска

ThePrimeagen отвечает на вопросы студентов о том, будет ли дерево сбалансировано после вставки, AVL по сравнению с красно-черным, может ли удаление одного и того же узла привести к разным деревьям, и существуют ли другие способы создания деревьев.

Реализация поиска по глубине

ThePrimeagen обсуждает структуру данных кучи как двоичное дерево, в котором каждый дочерний и внучатый узел меньше (MinHeap) или больше (MaxHeap) текущего узла. В этом сегменте также рассматриваются вопросы студентов о том, считается ли это двусвязным списком и реализуется ли это в массиве.

Реализация кучи

ThePrimeagen рассказывает о реализации и тестировании структуры данных MinHeap с использованием массива JavaScript в машине ката. В этом сегменте реализованы методы insert и delete.

Tries

ThePrimeagen обсуждает визуализацию попыток как автозаполнения, демонстрирует структуру дерева тройки с помощью псевдокода и реализует дерево тройки в kata-машине. Вставка и удаление в дереве тройки также рассматриваются в этом сегменте.

Графы

Обзор графов

ThePrimeagen обсуждает обзор графов как серии узлов со связями и терминологию, связанную с графами. В этом сегменте рассматривается следующая лексика: цикл, ациклический, связный, направленный, неориентированный, взвешенный, dag, узел и ребро.

Поиск матрицы смежности

ThePrimeagen демонстрирует представление графов в матрице смежности. Breadth-first и depth-first поиски все еще существуют на графе и практически не отличаются от поиска на дереве.

Реализация BFS на матрице смежности

ThePrimeagen рассказывает о том, как реализовать и протестировать поиск по глубине на матрице смежности с помощью машины kata. Матрица смежности – это двумерный массив размером V x V, где V – количество вершин в графе.

Реализация DFS на списке смежности

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

Кратчайший путь Дейкстры

ThePrimeagen обсуждает кратчайший путь Дейкстры, что это такое, где он используется, и демонстрирует некоторые его варианты. Кратчайший путь Дейкстры – это алгоритм, который находит кратчайшие пути между узлами в графе.

Реализация кратчайшего пути Дейкстры

ThePrimeagen рассказывает о реализации и тестировании версии кратчайшего пути Дейкстры в машине kata.

Время выполнения кратчайшего пути Дейкстры

ThePrimeagen обсуждает время работы кратчайшего пути Дейкстры, показывая в псевдокоде, что происходит за сценой. В этом сегменте также рассматривается вопрос студента о том, много ли вопросов о графах задают на собеседованиях.

Карты и LRU

ThePrimeagen обсуждает обзор терминологии карт, включая коэффициент загрузки, ключ-значение и коллизию.

Кэш LRU

ThePrimea