Тренировки по алгоритмам 7.0

10 задач по рекомендованным ниже темам для оценки уровня ваших знаний. Задачи не идут в зачёт и не влияют на итоговый рейтинг.

Жадный алгоритм — это алгоритм, который выбирает оптимальное действие на каждом шаге. Но такой подход не всегда даёт лучший результат, например, когда нам нужно оптимально наполнить коробку предметами известного веса.

Эта задача называется «задача о рюкзаке», и она решается методами динамического программирования.

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

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

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

На лекции мы рассмотрим применения битовых операций для исправления ошибок, которые постоянно возникают при передаче и хранении данных от таких неожиданных причин, как, например, космическое излучение. А также познакомимся с популярным методом сжатия данных, который используется в zip-архивах и многих других обстоятельствах.

В прямом эфире расскажем про:

• — особенности трудоустройства в Яндекс
• — основные этапы отбора на стажировку и в штат
• — навыки, необходимые для стажера/джуна и мидл‑специалиста
• — а также поможем прокачать ваше резюме

Разбор резюме

Если вы хотите, чтобы ваше резюме анонимно разобрали в прямом эфире, заполните форму до 21 апреля 10:00 мск. С помощью рандомайзера выберем несколько резюме для разбора

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

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

Рекомендованные темы для подготовки:

• Тренировки 6.0. Лекция 4: Деревья, представления и обходы
• Тренировки 3.0. Обход графов в глубину