Алгоритмы и структуры данных школа анализа данных яндекса

Обновлено: 05.07.2024

Кстати, похожие задачи будут в этом году на вступительном экзамене в ШАД, где для людей с опытом в ИТ мы придумали новый трек, который поможет им улучшить свои знания математики.

1. В ряд выложены пять красных, пять синих и пять зеленых шаров. С какой вероятностью никакие два синих шара не лежат рядом?

Например, так: сначала расположим красные и зелёные шары (надо выбрать из десяти пять мест, в которых будут красные), после чего пять синих шаров надо положить не более, чем по одному, в одиннадцать промежутков между красными и зелёными шарами, а также слева и справа (то есть выбрать пять мест из одиннадцати).

Задачи по алгоритмам очень хороши тем, что они проверяют не только умение понятно описать некую процедуру, но и объяснить, почему она работает.

Если граф — дерево, то бракованное реле находится перед первой (от источника тока) не горящей лампочкой. Если есть циклы, то можно выключить все рёбра и запустить аналог поиска в глубину.

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

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

четное число, гласная буква;
нечетное число, что угодно.

И не подходят карточки вида:

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

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

6. Квадратная матрица такова, что след tr(AX) = 0 для любой матрицы X того же размера, имеющей нулевой след (след матрицы — сумма элементов на главной диагонали).

Докажите, что матрица является скалярной (т. е. имеет вид λE для некоторого λ, где E — единичная матрица).

Таким образом, встретив подобную задачу, стоит сначала взять какие-нибудь конкретные (и желательно очень простые) матрицы X с нулевым следом и попробовать понять, что же нам дает условие tr(AX) = 0. В качестве таких матриц удобно взять матричные единицы (и матрицы, у которых на диагонали все нули, кроме двух элементов, равных 1 и (-1).

Собственно говоря, на этом задача и закончится: из условий tr(AX) = 0, которые вы распишете для таких матриц, сразу будет следовать ответ.

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

Лекции читает Максим Александрович Бабенко, заместитель директора отделения computer science, ассистент кафедры математической логики и теории алгоритмов механико-математического факультета МГУ им. М. В. Ломоносова, кандидат физико-математических наук.

Полный курс в виде папки на Яндекс.Диске

Лекция 1. Сложность и модели вычислений. Анализ учетных стоимостей (начало)

Основные ресурсы: память и время. О-символика. Примеры моделей вычисления: машина Тьюринга, RAM-машина. Сложность в среднем и худшем случаях. Пример: задача сортировки. Сортировка выбором. Теоретико-информационная нижняя оценка сложности. Разрешающие деревья. Нижняя оценка сложности в модели разрешающих деревьев. Массивы переменного размера: аддитивная и мультипликативная схемы реаллокации. Анализ мультипликативной схемы для массива переменного размера с помощью банковского метода.

Лекция 2. Анализ учетных стоимостей (окончание)

Анализ учетных стоимостей операций: функция потенциала, истинные и учетные стоимости. Стеки и очереди. Реализация на основе массива переменного размера и на основе связанного списка. Моделирование очереди с помощью двух стеков. Задача о поддержании динамического максимума в стеке и очереди. Изменяемые (mutable) и неизменяемые (immutable) структуры данных. Структуры данных с хранением истории (persistent). Immutable-стек и immutable-очередь. Проблема множественного будущего при анализе учетных стоимостей в persistent-структурах.

Лекция 3. Функции быстрой сортировки и сортировки слиянием

Лекция 4. Порядковые статистики. Кучи (начало)

Нахождение порядковых статистик с помощью рандомизированной модификации алгоритма Quick-Sort. Линейность матожидания времени работы. Приближенные медианы. Выбор k-й порядковой статистики за линейное в худшем случае. Деревья со свойствами кучи. Почти полные бинарные деревья: нумерация вершин, навигация. Двоичная куча. Операция просеивания вниз и вверх. Реализация операций вставки, удаления и поиска минимума. Преобразование произвольного массива ключей в кучу (операция Make-Heap), линейность времени работы. Алгоритм сортировки Heap-Sort.

Лекция 5. Кучи (начало). Хэширование (начало)

k-ичные кучи, зависимость сложности операций от выбора k. Биномиальные (binomial), левацкие (leftlist) и косые (skew) кучи.

Лекция 6. Хэширование

Хеш-функции. Коллизии. Разрешение коллизий методом цепочек, методом последовательных проб и методом двойного хеширования. Гипотеза простого равномерного хеширования, оценка средней длины цепочки. Универсальные семейства хеш-функций, оценка средней длины цепочки. Построение универсального семейства для целочисленных ключей. Совершенные хеш-функции. Построение совершенной хеш-функции с помощью универсального семейства. Интерфейс множества с ошибками. Фильтр Блюма (Bloom filter). Оценка вероятности ложноположительного срабатывания. Интерфейс словаря с ошибками. Модификация фильтра Блюма (bloomier filter).

Лекция 7. Деревья поиска (начало)

Определение дерева поиска. Вставка и удаление элементов. Inorder-обход дерева. Красно черные деревья: определение и основные свойства. Реализация операций вставки для красно-черного дерева. Splay-деревья. Операция splay: zig, zig-zig и zig-zag шаги. Реализация операций вставки, удаления, слияния и разделения для splay-деревьев.

Лекция 8. Деревья поиска (окончание). Декартовы деревья

Декартовы деревья (дучи). Единственность декартова дерева для заданного набора различных ключей и приоритетов. Логарифмическая оценка матожидания высоты дучи.Операции слияния и разделения для дуч. Операции вставки и удаления элементов для дуч. Построение декартового дерева за линейное время при условии предварительной сортировки ключей.

Лекция 9. B-деревья. Система непересекающихся множеств

B+ деревья: определения и основные свойства. Операции поиска, вставки и удаления для B+ деревьев. Системы непересекающихся множеств. Реализация с использованием леса. Ранги вершин, эвристика ранга. Логарифмическая оценка ранга через количество элементов. Рандомизированная ранговая эвристика. Эвристика сжатия путей. Оценка учетной стоимости операций (без доказательства).

Лекция 10. Задачи RMQ и LCA

Лекция 11. Задачи геометрического поиска

Location problem, stabbing problem. Деревья интервалов. Сведение системы интервалов к двумерной задаче. Задача поиска точек в коридоре. Priority search tree. Задача поиска точек в прямоугольнике. Дерево отрезков по координате X, упорядоченные по Y списки точек в каждой вершине. Сложность O(n log n) для построения и O(log^2 n) для запроса. Уменьшение времени поиска до O(log n). Задача одновременного поиска в наборе упорядоченных списков. Fractional cascading.

Лекция 12. Динамическая связность в графах

Задача о динамической связности: вставки и удаления ребер, запросы о связности. Частный случай задачи для случая лесов. Деревья эйлеровых обходов: слияние и разделение. Использование амортизации и набора остовных лесов для решения со сложностью O(log^2 n).

Анюта Наумова

Академия Яндекса запись закреплена

Вспоминаем одну из самых популярных лекций Школы бэкенд-разработки — посвященную алгоритмам. И делимся внушительным списком полезных ссылок по теме

Илья Волков, старший разработчик в Яндекс.Учебнике, обзорно расскажет про структуры данных, понятия вычислительной и амортизированной сложности.
Показать полностью. На примере простого списка задач и его эволюции с постепенными улучшениями мы рассмотрим подходы к задачам написания серверной части веб-приложений. Поговорим про подходы и обычные приёмы оптимизации задач и кода. В заключительной части лекции обсудим процесс прохождения технических собеседований в IT-компаниях.

Что изучить дополнительно?

— Пример сервиса с более-менее простым набором задач для знакомства с новыми языками: exercism.io

Было бы ещё интересно почитать от вас лекции по рекурсивным грамматикам, контекстно-зависимым грамматикам.

Академия Яндекса запись закреплена

Как писать и оптимизировать алгоритмы с нуля?

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

Вот как стоит действовать, когда вы получили задачу:

То есть — разделить её на как можно более маленькие подзадачи. Во-первых, потому что так вы структурируете будущий алгоритм, во-вторых — потому что с маленькими кусочками проще работать.

Хотя бы как-то структурировав задачу, вы начнёте понимать, как она должна решаться.

3. Найти повторяющуюся или лишнюю работу

5. Вернуться в начало и повторять пункты 1-4

Михаил Горюнов

А если на пункте 5 не можешь убедить себя, что все плохо, а только сосед может? Зачем придумали код ревью?

Академия Яндекса запись закреплена

Расчёска, пузырёк, слияние и вставка — составили памятку для тех, кто хочет наконец разобраться в алгоритмах сортировок.

Сохраняйте — пригодится, чтобы освежить в памяти

Даниил Маркевич

Небольшое замечание: heapsort может использовать O(1) памяти вместо O(n), если создавать кучу in-place.

Данила Мантуров

Академия Яндекса запись закреплена

Материалов по алгоритмам много не бывает, поэтому мы вместе с экспертами Яндекса продолжаем делиться полезными ссылками, которые помогут вам прокачаться в этой теме

Академия Яндекса запись закреплена

Что надо уметь на секции по алгоритмам в Яндексе — максимально коротко

Итак, в реальной работе и на собеседовании разработчик должен уметь:

— реализовывать простые алгоритмы быстро и без багов;

— аккуратно обрабатывать краевые случаи либо писать код так, чтобы эти краевые случаи не возникали;

— уметь пользоваться базовыми конструкциями языка программирования (например, ассоциативными массивами);

— придумывать достаточно хорошие решения; пусть не идеальные, но подходящие для текущих ограничений.

Однако если вы планируете устраиваться в большую IT-компанию, вам точно стоит прочитать материалы, которые подготовил Алексей Шаграев — руководитель службы свеже-социального поиска Яндекса. Это две статьи на Хабре (одна из них совсем свежая) и два видео. Они развивают мысли, заложенные в списке выше, и подкрепляют их реальными примерами:

Кстати, сейчас все секции проходят удалённо, по видеосвязи.

Академия Яндекса запись закреплена

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

Академия Яндекса запись закреплена

Чтобы доказать, что в процессе развития сервисов алгоритмические задачи возникают постоянно, руководитель службы свеже-социального поиска Алексей Шаграев собрал на Хабре четыре реальных примера.
Показать полностью. Два из них относятся к бэкенду, один — к фронтенду и ещё один — к аналитике. Дело в том, что популярна промежуточная точка зрения: да, алгоритмы стоит спрашивать, но только у бэкендеров. Это не так. Вот краткий пересказ двух примеров из четырёх:

Таких параметров в адресе может быть множество. У разработчиков интерфейса одного из сервисов Яндекса возникла задача — представлять набор параметров в виде массива, чтобы с ними было удобнее работать. Казалось бы, что тут сложного — преобразовать строку в массив. Но важно учесть, что параметр может встретиться в адресе несколько раз, а его значение бывает пустым. Навыки, необходимые для составления такого кода, мы и проверяем на собеседовании. Почему важно сходу написать правильный код? Потому что это очень мелкая задача: у вас не будет времени на поиск багов в каждом таком примере, если вы хотите быть продуктивны.

Школа анализа данных – двухгодичная программа обучения от Яндекса. Основной упор в ней делается на данные и методы работы с ними. В небольшом обзоре мы разберём плюсы и минусы учёбы в ШАД.

Как поступить?

Итак, ШАД – полноценное обучение на протяжении двух лет, с нагрузкой по 30 часов в неделю. Обучение бесплатное, но сначала требуется пройти онлайн-тестирование, затем экзамен и собеседование в филиалах ШАД.

Как и в университете, здесь есть возможность платного поступления, но для этого нужно хорошо показать себя на собеседовании. Стоит учёба 150 000 рублей в семестр. Если закончить семестр на хорошо и отлично, цена уменьшится наполовину. А если два раза подряд закончить хорошистом или отличником, обучение станет бесплатным.

Онлайн-тестирование – обычное заполнение анкеты с тестовыми вариантами задач. После него есть два варианта: для москвичей следует прибыть в отделение ШАД и сдать экзамен по математике, алгоритмам, а затем по программированию и основам анализа данных. Заочники или учащиеся в региональных отделениях сдают онлайн-экзамен.

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

Все задачи выбираются в рамках общей программы (в документе даже указаны все необходимые книги для подготовки). Кстати, у нас есть статья, полностью посвящённая подготовке к поступлению в ШАД.

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

Кому это нужно?

Во-первых, выпускники получают диплом о профессиональной переподготовке. Во-вторых, любовь к Data Science и желание глубоко-глубоко нырнуть в эту отрасль. При этом, если вас интересует чистая научная теория, то место найдётся – регулярные семинары и различные исследовательские проекты.

В целом, целевую аудиторию можно описать так: хочется попасть в сферу Data Science, сделать это максимально эффективно и интересно. К тому же, обучение проходит по вечерам.

ШАД: Плюсы обучения

ШАД: Минусы обучения

Вечерняя программа. Если ваша жизнь уже загружена, то добавлять к ней вечерние курсы – стрелять себе в ногу. При этом, обучение действительно интенсивное и требует внимательности.
Серьёзная нагрузка. Так как здесь учат анализировать, то мозги будут работать на полную катушку. А то потребуется их перегружать их. Следует заранее прокачать выносливость и… умение отдыхать.

Читайте также: