Data Science: Алгоритмы и Структуры данных

​Зачем на собеседованиях спрашивают про алгоритмы? Причин несколько: — В процессе работы вы можете сменить много раз язык разработки и используемые фреймворки. Но знание алгоритмов — это некая общая база, которая позволит легко переключиться между технологиями. — Вероятно, вам дадут задачи и спросят про алгоритмы и структуры данных, которые мало используются в реальных проектах. Так компания хочет проверить, насколько вы заинтересованы в работе. Об этом подробно рассказал разработчик, который проводит алгоритмические секции собеседований в «Яндекс»: https://youtu.be/oB_FEwky2wo

​Красно-чёрное дерево: что это за структура и как понять его свойства Студенты технических специальностей часто сталкиваются с понятием красно-чёрного дерева (КЧД). Эта структура данных относится к бинарным деревьям поиска и позволяет сделать вставку, удаление и поиск нужного элемента за время O(log n). Чтобы понять основные принципы построения КЧД, можно сначала изучить 2-3 дерево. Если его превратить в бинарное дерево, то оно будет красно-чёрным. Подробнее об этом — в статье: https://tproger.ru/articles/ponimaem-krasno-chjornoe-derevo-chast-1-vvedenie

Визуализация 16 сортировок Написано полностью на Java. Предупреждаем, можете залипнуть. Исходники на GitHub: https://github.com/w0rthy/ArrayVisualizer

​Структура данных пирамида (двоичная куча) в Java Пирамида представляет собой дерево значений. Значение узлов в неё больше или равно значениям узлов-потомков. Поэтому верхний элемент всегда будет иметь максимальное значение Подробнее о пирамиде и её реализации на Java: https://javarush.ru/groups/posts/3083-strukturih-dannihkh-piramida-dvoichnaja-kucha-v-java

Реализация множества алгоритмов и структур данных на C# На GitHub можно найти много полезного. В том числе крутой репозиторий, в котором собраны реализованные на C# алгоритмы и структуры данных. Рекомендуем посмотреть хотя бы на популярные алгоритмы, например сортировки или алгоритмы поиска. Где покопаться в коде: https://github.com/TheAlgorithms/C-Sharp

​Визуализация поиска пути в клетчатом лабиринте На GitHub есть интересный интерактивный инструмент, где вы можете построить свой лабиринт и посмотреть, как работают различные алгоритмы поиска пути в графе. Начальные и конечные точки можно двигать, а работу самих алгоритмов можно настроить. Выглядит залипательно. Поиграться: https://qiao.github.io/PathFinding.js/visual/

Как работает ArrayList ArrayList — это класс, который выполняет функции массива в Java и обладает несколькими полезными методами. Если вы не можете разобраться до конца, как он работает, то в статье наглядно показано, что происходит в массиве во время операций: https://javarush.ru/groups/posts/1936-rabota-arraylist-v-kartinkakh--

Изучаем числа Фибоначчи В этом видео вы познакомитесь с понятием числа Фибоначчи, а также узнаете, как написать программу на Java, вычисляющую требуемое число Фибоначчи: https://youtu.be/2kSx7wMAhcc

Алгоритм Евклида В задачах по программированию нередко требуется найти наибольший общий делитель (НОД) двух чисел. Для решения используют алгоритм Евклида. Мы нашли ресурс, на котором просто объясняется, как работает алгоритм Евклида в двух вариациях: через деление и через вычитание. А примеры реализации нахождения НОД написаны на Python. Ссылка: https://younglinux.info/algorithm/euclidean

​Решаем задачу о поиске пары ближайших точек Представьте, что перед вами множество точек. Как найти пару точек, которые будут находиться на минимальном расстоянии друг от друга? Одно из решений задачи сводится к использованию метода «разделяй и властвуй». Более подробно о нём рассказано в видео с примером реализации на Python: https://youtu.be/Dx5eiQdv4k8

Слышали ли вы о гипотезе Коллатца? Наверняка нет. Этот интересный математический фокус не имеет математического доказательства, но и опровергнуть никто не смог. Попробуйте загадать любое целое положительное число и затем следуйте простому алгоритму: 1. Если число чётное, разделите его на 2. Иначе умножьте его на 3 и прибавьте 1. 2. Повторите шаг 1 с полученным числом. Подробнее об этом фокусе читайте здесь: https://tprg.ru/eApw

Связные списки: объяснение и реализация на JavaScript В связном списке данные хранятся друг за другом. При этом в каждом элементе списка содержится поле с данными и поле с ссылкой на следующий элемент. В видео показано, как реализовать собственный связный список со всеми необходимыми методами: https://youtu.be/QdCyTTid9-U

Реализуем на C# поиск суммы цифр числа В этом уроке рассматриваются два метода: с помощью рекурсии и с помощью циклов: https://youtu.be/c4h0FKXkWf8

​Структура данных «очередь» (queue) — принципы работы С понятием очереди вы наверняка хорошо знакомы. В программировании она используется для обработки данных, запросов и событий в том порядке, в котором они попали в очередь. Подробнее об этой структуре данных поясняется в ролике: https://youtu.be/fmHyFTji-Lc

Двоичное (бинарное) дерево поиска Структуры данных «деревья» широко распространены в программировании, например каталог проекта или DOM-дерево в веб-разработке. Среди них особенно выделяется двоичное дерево поиска, которое позволяет существенно ускорить поиск элементов. Подробнее о структуре двоичного дерева и его реализации в коде: https://tproger.ru/translations/binary-search-tree-for-beginners/

Ищем повторяющиеся элементы в массиве Предположим, вам нужно найти дубликат элемента в массиве. Как бы вы решили эту проблему? Сначала подумайте, а затем загляните в статью, чтобы узнать о различных способах решения: https://nuancesprog.ru/p/2340/

​Классические алгоритмы генерации лабиринтов Попробуйте свои силы в генерации лабиринтов — интересном проекте, который можно реализовать на любом популярном языке программирования. Работа над проектом отточит ваши навыки кодинга, а результат пригодится, если вы соберётесь в геймдев. Алгоритм двоичного дерева и алгоритм SideWinner: https://tprg.ru/RWAC Алгоритм Олдоса-Бродера и алгоритм Уилсона: https://tprg.ru/IneP

​Ищем кратчайший путь в лабиринте: объяснение на Python Поиск пути является одной из типичных задач в программировании. Однако принципы алгоритмов поиска достаточно трудно освоить новичкам. Понять лучше алгориты поиска пути можно на примере задачи по поиску выхода из двухмерного лабиринта. А руководство поможет разобраться с реализацией на Python популярного алгоритма поиска пути — алгоритма Дейкстры: https://habr.com/ru/company/piter/blog/596029/

Возврат нескольких значений из функции Python Чтобы в Python вернуть из функции сразу несколько значений, нужно воспользоваться структурами данных. Так вы можете передать из функции данные в виде списка, кортежа или словаря. Как это сделать, объясняется в статье: https://pythonist.ru/vozvrat-neskolkih-znachenij-iz-funkczii/

Реализуем односвязный список на C++ У массивов в C++ есть недостаток — к существующему массиву нельзя добавить дополнительный элемент. С этой задачей справляются динамические структуры данных. Одной из них является односвязный список (теория). За три урока вы сможете реализовать эту структуру данных на C++: часть 1, часть 2 и часть 3.