Введение 0:10 Михаил Густокашин представляет себя как преподаватель факультета компьютерных наук в Высшей школе экономики. Курс посвящён алгоритмам и структурам данных. Подчёркивается, что курс не связан с задачами собеседований в Яндексе.
Алгоритмические собеседования 0:40 При устройстве на работу проводятся несколько собеседований, включая секцию по алгоритмам. На алгоритмическом собеседовании проверяют умение писать работающий код, тестировать его и писать эффективный код.
Проверка навыков 3:16 На собеседовании дают задачу, похожую на олимпиадную, без дополнительных условий. Необходимо написать решение на бумаге без использования дополнительных средств.
Критерии для стажёров 4:26 Для стажёров без опыта работы требуется написать 10 тысяч строк работающего, эффективного и протестированного кода. Важно, чтобы код был разнообразным и содержал меньше копипаста.
Подготовка к собеседованиям 6:06 Решение алгоритмических задач помогает набить руку и улучшить навыки. Существуют сайты с задачами для подготовки к собеседованиям, где код автоматически проверяется.
Структура курса 8:37 Курс включает 8 лекций и 4 разбора каждой лекции. Практические занятия включают решение задач с автоматической проверкой. Курс предназначен для людей без опыта программирования или с минимальным опытом.
Содержание первой лекции 10:41 Первая лекция охватывает сложность алгоритмов, особые случаи и тестирование. Сложность алгоритмов определяется порядком количества действий, которые алгоритм выполняет.
Линейная сложность 11:05 Линейная сложность означает, что количество действий алгоритма линейно зависит от размера входных данных. Пример линейной сложности: цикл, который проходит по всем элементам последовательности, независимо от количества элементарных действий.
Оценка сложности алгоритмов 12:21 Сложность алгоритма с двумя вложенными циклами оценивается как O(n^2). Существуют другие методы оценки сложности, такие как функции theta и o-малые, но они сложнее в доказательстве. О-большая сложность означает, что алгоритм выполняет не более указанного количества действий.
Сравнение алгоритмов по асимптотической сложности 13:26 Асимптотическая сложность оценивается для больших значений параметра. Даже неэффективный алгоритм с O(n^100) может быть лучше, чем O(n^2) для больших n. Пространственная сложность учитывает количество дополнительной памяти, используемой алгоритмом.
Пример задачи на поиск самого частого символа 15:03 Задача: найти самый часто встречающийся символ в строке. Решение: перебрать все позиции строки внешним циклом и символы внутренним циклом, подсчитывая количество совпадений. Сложность алгоритма: O(n^2), где n — длина строки.
Реализация на Python 16:48 Пример реализации на Python с консольным вводом-выводом. Объяснение работы с строками и переменными в Python. Использование циклов для перебора позиций и символов.
Оптимизация алгоритма 20:37 Идея оптимизации: перебирать только уникальные символы, а не позиции. Новая сложность алгоритма: O(k), где k — количество уникальных символов в строке. Применение функции set для создания множества уникальных символов.
Применение оптимизации 23:28 Оптимизация ускоряет решение для длинных строк с повторами символов. Пример с «Войной и миром»: старый алгоритм занял бы слишком много времени. Даже после оптимизации решение может быть улучшено дальше.
Введение в словарь 24:57 Создаём словарь, где ключ — символ, а значение — количество его вхождений. Если символ встречается впервые, создаём элемент словаря с ключом и значением 0. При каждом вхождении символа увеличиваем его значение на 1.
Реализация кода 25:32 Перебираем символы из строки и увеличиваем значение ключа в словаре при совпадении. Если символ уже был в словаре, увеличиваем его значение. Находим максимум среди значений словаря для каждого ключа.
Анализ сложности алгоритма 28:54 Сложность алгоритма: O(n + k), где n — длина строки, k — количество символов в словаре. Поскольку k всегда меньше n, можно считать сложность O(n).
Сравнение с другими методами 29:36 Метод с множеством требует O(n * k) памяти. Метод со словарем требует O(n) памяти, так как строку можно не хранить.
Ошибки при работе с пустыми строками 30:45 Удаление строки из кода приводит к ошибке при работе с пустой строкой. Неинициализированная переменная вызывает ошибку времени выполнения.
Обработка пустых последовательностей 32:21 Пустые последовательности требуют специальной обработки. Для суммы последовательности выводим 0, если последовательность пуста. Для максимума последовательности выводим бесконечность, если последовательность пуста.
Тестирование алгоритмов 35:04 Тестируем алгоритм на примерах из условия задачи. Проверяем общие и особые случаи, включая краевые эффекты и пустые последовательности. Создаём дополнительные тесты для проверки работоспособности алгоритма.
Советы по тестированию 38:12 Решаем задачу в голове перед написанием кода. Сверяем результаты с примерами из условия задачи. Добавляем дополнительные примеры для проверки различных ситуаций. Запускаем программу и сравниваем результаты с ожидаемыми.
Краевые эффекты и тестирование 39:33 Краевые эффекты возникают, когда границы поиска перепутаны или используются неправильные элементы. Важно проверить код после написания, особенно на крайних случаях. Тесты следует продумать до начала написания кода, чтобы избежать забытых случаев.
Покрытие тестами 40:33 Необходимо покрыть тестами все ветвления и циклы. Тесты должны проверять поведение программы на пустых последовательностях и последовательностях из одного элемента.
Маленькие тесты 41:09 Один тест должен содержать одну ошибку, чтобы легко локализовать проблему. Большие тесты с множеством ошибок усложняют исправление.
Пример с квадратным уравнением 41:33 Задача: найти корни квадратного уравнения и вывести их в порядке возрастания. Ошибка в приоритете операций из-за отсутствия скобок. Забытый случай: дискриминант равен нулю, выводится один корень.
Дополнительные случаи 44:18 Проверка случая, когда дискриминант меньше нуля. Обработка случая, когда один из коэффициентов равен нулю. Вывод «бесконечное количество решений» при всех нулевых коэффициентах.
Порядок корней 47:44 Ошибка в порядке вывода корней при отрицательных коэффициентах. Добавление теста на отрицательный коэффициент для корректного вывода.
Пошаговая отладка 49:27 Использование пошаговой отладки для выявления ошибок. Выполнение программы по строкам для точного понимания процесса. Избегание размышлений о коде вместо его выполнения.
Проверка алгоритма 52:56 Проверка корректности алгоритма через псевдокод. Выполнение каждой операции в голове для понимания работы алгоритма.
Оптимизация времени исполнения и памяти 53:40 На практике чаще оптимизируют время исполнения, а не память. Если алгоритмы имеют одинаковое время исполнения, выбирают тот, который потребляет меньше памяти. Существуют редкие задачи, где память играет решающую роль.
Создание множества и его порядок 54:20 Создание множества линейно, но порядок элементов в нём случайный. Отсутствие порядка в множестве влияет только на вывод символов, но не на их частоту. Перебор элементов множества в случайном порядке корректен.
Анализ памяти в решениях 55:50 В первом решении нужно хранить всю строку, даже если символы поступают по одному. Во втором решении приходится хранить строку и множество. В третьем решении строка не хранится, что экономит память.
Собеседования и стандартные функции 57:05 На алгоритмическом собеседовании могут попросить реализовать функции вручную. На собеседовании по языку уместно использовать знания языка. Важно понимать, куда вы идёте, чтобы правильно подготовиться.
Сложность алгоритмов 58:27 Сложность функции, принимающей вектор на 100 тысяч чисел, будет O(100000). Формально это константа, но задача очень большая. Обсуждение сложности рекурсивных алгоритмов будет в следующей лекции.
Использование библиотек 1:00:27 В реальных проектах лучше использовать библиотеки, но понимать их внутреннюю работу. Общее представление о работе библиотечных функций полезно.
Обработка исключений 1:01:38 Обработка исключений не нужна в алгоритмических задачах. На алгоритмической секции обработка исключений не потребуется.
Поиск ошибок в коде 1:03:06 Метод пристального взгляда: выполнение кода по строчкам для поиска ошибок. Стресс-тестирование: создание примитивного решения и сравнение его с сложным решением на случайных тестах. Если ответы не совпадают, найден тест, на котором решение работает неправильно.
