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

Рекурсия и сортировка Quick Sort простыми словами на JavaScript Если хотите разобраться, как устроена рекурсия и сортировка массива Quick Sort, то читайте статью ниже. В ней автор простыми словами разбирает эти алгоритмы на JavaScript. 👉Читать статью

ГК «Астра» - звучит грозно и непонятно. Кто стоит за продуктами? Команды там или подразделения? Чем занимаются разработчики и что они используют? Расставляем все точки над i в Astra Team. Здесь мы рассказываем о том, кто и как меняет ход IT. В канале вы узнаете интересные факты о ведущем российском вендоре и познакомитесь с нашими разработчиками. Они расскажут о достижениях, работе в команде и своих задачах. Новости, инсайты от ведущих специалистов, вакансии и полезные подборки от профессионалов своего дела - все это ждет вас в Astra Team! Присоединяйся к тем, кто меняет ход IT! https://t.me/+6CsnY08TfPZiOTAy

Шаги решения любой задачи Нашел статью недавно и понимаю теперь где я косячил в самом начале. Никогда не пытайтесь сразу решать задачу оптимизированно. Или, что еще хуже, тупо не разбираясь в самой проблеме стараться ее зазубрить. Поверьте - это не выход и так вы ничему не научитесь. В статье описываются шаги того, что надо сделать приступая к любой проблеме: 1. Понять саму проблему 2. Выбрать общее направление по решению проблемы. 3. Подумайте что вы можете сделать (используя ваш предыдущий опыт) 4. Попробуйте найти, что вы не можете сделать. А также в этом кейсе подумайте и над исключительными ситуациями, которые могут произойти. 5. Только теперь подумайте над тем, что вы можете улучшить в текущем решении.

Экспоненциальный поиск или Finger Search Finger Search ищет элемент в отстортированном массиве, перескакивая 2 ^ i элеентов на каждой итерации, где i представляет значение переменной управления циклом. После идет проверка: присутствует ли элемент поиска между последним и текущим переходом. Как это работает? 1. Проходите по элементам массива по 2 ^ i за один раз, выполняя поиск условия:

Array[2 ^ (i - 1)] < valueWanted < Array[ 2 ^ i]

Если 2 ^ i больше, чем длина массива, установите верхнюю границу равной длине массива 2. Выполните двоичный поиск между массивами Array[2 ^ (i - 1)] и Array[2 ^ i]

Алгоритм Interpolation Search 1. В цикле вычисляем значение позиции (pos), используя формулу, что обсуждали в предпоследнем посте. 2. Если есть совпадения, то вернуть индес элемента и выйти из цикла 3. Если элемент меньше, чем позиционный элемент, вычислить положение для левого подмассива, в противном случае в правом подмассиве 4. Повторять, пока не найдется совпадение или пока подмассив не уменьшится до нуля.

Выбор позиции для поиска в Interpolation Search Чтобы разделить массив на две части, мы используем следующую формулу:

mid = Lo + ((Hi - Lo) / (A[Hi] - A[Lo])) * (X - A[Lo]), где

A - наш искомый массив X - элемент, который мы ищем Lo - наименьший индекс массива Hi - наивысший индекс массива An - значение, хранящееся под индексом n в списке. Если средний элемент больше, чем искомый элемент, то позиция снова вычисляется, но уже в подмассиве. Это продолжается до тех пор, пока размер подмассива не уменьшится до нуля

​​Java — один из самых популярных языков программирования. Он универсален и выступает основой всех типов сетевых приложений. Специалисты, работающие с этим языком, востребованы на рынке. Если хотите к ним присоединиться, участвуйте в бесплатном тематическом онлайн-интенсиве. Узнайте подробности: 👉 https://epic.st/qYqKfK Сразу после регистрации отправим вам на почту гайд по профессии Java-разработчика. Из него вы узнаете, сложно ли изучить Java, сколько зарабатывают специалисты и как начать карьеру в этой сфере. 📌 Никакой скучной теории — только самый интересный материал и мощная практика. За 3 дня вы примерите на себя профессию Java-разработчика и поймёте, в каком направлении двигаться дальше. 📌 Спикером выступит директор центра подбора IT-специалистов SymbioWay Даниил Пилипенко. Он поделится секретами профессии и лайфхаками, расскажет, как найти первого заказчика. 🎁 Всех ждут подарки. Участвуйте, задавайте вопросы и получите сертификат на скидку 10 000 рублей на любой курс Skillbox. Присоединяйтесь к онлайн-интенсиву с 27 по 29 апреля в 15:00 по московскому времени.

Алгоритмы и структуры данных: примеры реализаций на JavaScript Если вы изучаете JavaScript, загляните в репозиторий на GitHub, в котором собраны реализации структур данных и множества популярных алгоритмов. К каждому алгоритму приложено короткое пояснение, которое поможет разобраться в коде. Весь материал разделён на два уровня: для начинающих и для продвинутых: https://github.com/trekhleb/javascript-algorithms

Введение в криптографию и шифрование Когда-то материал из этой лекции читали в МГУ целых полгода. Поэтому в статье автор не углублялся в работу шифров и рассказал об общих терминах в криптографии и шифровании, а также разобрал простым языком несколько алгоритмов шифрования: https://habr.com/ru/company/yandex/blog/324866/ Лекция на YouTube: https://youtu.be/mE_s-R5wvpw

Операции над Min Heap 1. getMin - возвращает корневой элемент вашего Min Heap 2. extractMin - удаляет минимальный элемент из MinHeap (сложность О(logN) из-за того что надо поддерживать свойства кучи) 3. reduceKey - уменьшает значение ключа (так же сложность O(logN) 4. insert - вставка нового элемента (занимает также O(logN)) Добавит вам новый ключ в конец дерева, если новый ключ больше, чем родительский, вам не придется ничего делать. В противном случае нужно пройти вверх, чтобы исправить свойства кучи 5. delete - удаление ключа (также займет в худшем случае O(logN)

Представление Двоичной кучи Как мы вчера уже поняли - двоичная куча - это полноценное двоичное дерево. Представляется куча в виде массива. Корневой элемент будет всегда в arr0 (нулевом индексе массива). В табличке (на картинке) - как раз указано, как в дальнейшем берутся индексы. Есть интересные свойства: 1. arr(i-1) / 2 - вернет всегда родительский узел 2. arr(2 * i) + 1 - вернет левый дочерний узел 3. arr(2 * i) + 2 - вернет правый дочерний узел

​​Reverse Linked List Операция заключается в себе то, что нам необходимо последний узел - первым, и соответственно перевернуть все остальные элементы также. Для этого нам надо перейти сначала в конец списка. Конец списка(односвязного) всегда указывает на NULL своим указателем next. Теперь нам надо поменять его ссылку next на предыдущий элемент (который идет за ним). Мы должны убедиться, что последний узел не является потеряным. Таким образом у нас будет создан временный узел, который выглядит как головной, указывающий на последний узел. Теперь надо сделать (через цикл), чтобы все левые узлы указывали не на следующий элемент, а на свой предыдущий. Эту операцию надо сделать всем узлам, кроме первого. Первый же узел должен указывать на Null. Теперь можем взять тот temp head и установить его как оригинальный head. Вуаля, мы перевернули наш связный список

​​Операция вставки в связный список (LinkedList) Добавление нового узла в связный список - это не такое и простое действие для понимания. Поэтому стоит его разобрать (как и все последующие действия). На изображении вы можете увидеть подробности. А пока поговорим про операции. Давайте представим ситуацию, когда мы хотим вставить узел С между узлами A и B. Соответственно наша ссылка next нашего узла C должна сначала начинать указывать на узел(node) B. После чего узел A также должен сменить свою ссылку next на новое место: на узел С, который мы и вставляем. Соответственно у узла А пропадет ссылка на узел B, которая была изначально. Аналогичные шаги надо будет сделать, если узел вставляется в начало списка (только с указателем head не забыть его поставить на новое значение) Вставка в конец, новый узел будет указывать указателем next на Null - тоже не забудьте это.

Будущим аналитикам данных и специалистам по DS важно дружить с математикой. Если вы чувствуете, что нужно освежить знания и восполнить пробелы — пройдите курс от Яндекс Практикума. Он подойдёт тем, кто учится анализу данных или проходит собеседования. Поможем подготовиться ко всем каверзным вопросам и претендовать на оффер в компании, где ценят знания математики. Курс сделан для людей: не фундаментальный вузовский учебник, но и не научпоп. ◼️ Объясняем сложное простым языком, с примерами и иллюстрациями. ◼️ Вписываем практические задачи в бизнес-кейсы. ◼️ Объясняем, как абстрактные формулы связаны с анализом данных. ◼️ Разбираем типовые задачи из собеседований. Вы не останетесь один на один с тервером, матаном и линалом. Опытные преподаватели математики всегда на связи в чате, чтобы объяснить непонятное. → Оцените формат и пройдите бесплатный вводный урок: https://practicum.yandex.ru/math-for-da-ds/

​​Операция вращения массива Задача: Написать функцию rotate, которая вращает массив размера n на d элементов Способ решения 1: использование дополнительного массива К примеру нам даны следующие параметры на входе: arr = 1, 2, 3, 4, 5, 6, 7, d = 2, n = 7 1. Первым делом мы предсохраним первые d элементов в temp массиве temp = 1, 2 2. Сделаем очищение этих элементов с начала нашего оригинального массива (к примеру при помощи shift(часто реализовано во многих языках, только называется по другому)). arr = 3, 4, 5, 6, 7, 6, 7 3. Приатачим к оригинальному массиву наш temp массив: arr = 3, 4, 5, 6, 7, 1, 2 Time Complexity: O(n) Space Complexity: O(d) Cпособ решения 2: вращать друг за другом 1. Сохраним arr0 во временной переменной temp 2. Переместите arr1 в arr0 с последующими поступить также и наконец добавьте в конец temp То есть по тому же примеру у нас есть параметры: arr = 1, 2, 3, 4, 5, 6, 7, d = 2 Мы данный массив будем вращать 2 раза, первый раз получим следующий массив: 2, 3, 4, 5, 6, 7, 1 После второго же вращения получится: 3, 4, 5, 6, 7, 1, 2 Time Complexity: O(n * d) Space Complexity: O(1) Source Code вы можете увидеть на картинке ниже! Но есть более интересный способ решения, который мы рассмотрим в следующий раз.

🐍 Быстрая сортировка QuickSort — это алгоритм «разделяй и властвуй». Он выбирает элемент в качестве опорного элемента и разбивает заданный массив вокруг выбранного опорного элемента. Реализация на Python: def quicksort(l, r, nums): if len(nums) == 1: return nums if l < r: pi = partition (l, r, nums) quicksort(1, pi-1, nums) quicksort (pi+1, r, nums) return nums Существует много разных версий quickSort, которые по-разному выбирают точку опоры.

Как понять, какая IT-профессия вам подойдёт?   Бесплатный проект «IT-рентген» от Skillfactory поможет определить подходящую профессию даже гуманитарию без багажа знаний в сфере высоких технологий.   Начните с прохождения теста: он определит, кто вы в мире IT — дата-сайентист, тестировщик, аналитик или, быть может, разработчик.   А 13 апреля обязательно приходите на онлайн-встречу, на которой расскажут о трендах в IT-сфере, о наиболее простых точках входа и ошибках новичков.   На встрече вы получите доступ к материалам, которые заменят более 100 вебинаров и сэкономят порядка 50 часов на поиске информации о профессиях и лайфхаках.   Проходите тест и узнайте, кто вы в IT

💻 Основные структуры данных Из видео вы узнаете про самые используемые структуры данных: статический, динамический и ассоциативный (HashTable) массив. Видео довольно трудное для новичков, поэтому переходите к просмотру только в том случае, если вы знаете про hash-функции и сложность алгоритмов. А ещё автор говорит очень быстро, поэтому советуем немного размять мозги, чтобы всё освоить https://www.youtube.com/watch?v=K4sYJHuNgmE

Реализация кругового связного списка на Python

Структура данных - круговой связанный список Круговой связанный список — это вариант связанного списка, в котором первый элемент указывает на последний элемент, а последний элемент указывает на первый элемент. Как односвязный список, так и двусвязный список можно превратить в круговой связанный список. Стоит отметить, что в двусвязном списке следующий указатель последнего узла указывает на первый узел, а предыдущий указатель первого узла указывает на последний узел, делающий круговую в обоих направлениях. Основные операции: - display - отображение всего списка - insert - вставка элемента в список - delete(remove) - удаление узла из списка по ключу