Введение и цель курса 1:31 Михаил Густокашин преподает алгоритмы и структуры данных в ВШЭ. Курс посвящен алгоритмическому собеседованию в Яндексе. Цель курса - помочь подготовиться к собеседованию и улучшить навыки программирования.
Важность работающего и эффективного кода 2:26 Умение писать работающий код - ключевой навык. Важно тестировать код и делать его эффективным. В Яндексе требуется эффективный код для обработки больших объемов данных.
Тренировки и задачи 3:16 Тренировки будут включать маленькие алгоритмические задачи. Код должен быть рабочим, протестированным и эффективным. Время работы кода будет измеряться, и задачи не засчитаны, если не укладываются в лимиты.
Разнообразие кода и задачи 5:06 Важно писать разнообразный код, а не однотипный. Алгоритмические задачи помогают набить руку и улучшить навыки. Тренировки включают задачи, похожие на те, что бывают на алгоритмических собеседованиях.
Сервисы для тренировки 6:06 Используются сервисы для тренировки, такие как Яндекс.Код и ЛитКод. Эти сервисы помогают улучшить навыки и подготовиться к собеседованиям. Курс учит подходить к решению задач, а не гарантирует успех на собеседовании.
Темы курса 7:35 Курс включает четыре темы: сложность, тестирование, линейный поиск, множества и словари, бинарный поиск. Эти темы часто встречаются на собеседованиях и в реальной жизни. Каждая тема будет изучена подробно и с практикой.
Контесты и рейтинг 10:14 После каждой лекции будет доступен контест. Задачи считаются зачтенными, если прошли все тесты и уложились в лимиты. Рейтинг формируется по количеству решенных задач, а не по времени или качеству кода.
Бонусы и мотивация 12:19 Курс дает знания и умения, полезные для прохождения собеседований и улучшения навыков программирования. Не стоит переживать, если не удалось решить задачи быстро. Тренировка и практика помогут улучшить навыки и достичь успеха.
Алгоритмическое собеседование 13:26 Будет проведен эфир с алгоритмическим собеседованием в Яндексе. Участники увидят процесс собеседования в прямом эфире. Для топ-200 участников будет организована персональная тренировка.
Персональная тренировка 13:56 Участники будут изучать алгоритмы и готовиться к собеседованиям. Тренировка поможет не только решать задачи, но и правильно вести себя на собеседовании. Пробное алгоритмическое собеседование можно будет зачесть как настоящее.
Честность и результаты 14:53 Призывы к честности при решении задач. Нечестные участники будут забанены. Знания и умения останутся с участниками, даже если они не попадут в топ-200.
Введение в сложность алгоритмов 16:12 Лекции будут посвящены сложности алгоритмов и их тестированию. Будут рассмотрены большие данные и эффективные алгоритмы. Введение в RAM-машину и её упрощенную модель.
RAM-машина 17:12 RAM-машина упрощена для практических целей. Доступ к памяти произвольный, операции с памятью и процессором выполняются за одну операцию. Переходы и вызовы функций также считаются одной операцией.
Условности и критерии оценки 18:04 Условности в RAM-машине для упрощения оценки сложности. Реальная сложность программы оценивается по другим критериям. RAM-машина похожа на выполнение программ на компьютере, но с упрощениями.
Введение в сложность алгоритма 19:13 Сложность алгоритма определяется количеством действий в зависимости от размера входных данных. Пример: сортировка массива пузырьком требует n^2 действий. Это простое определение сложности.
Аннотации и оценка сложности 20:08 Используется аннотация для структурирования информации. Оценка функции сверху: алгоритм работает за O n^2. Количество операций в RAM-машине можно вычислить явно, но это не всегда важно.
Применение теории на практике 21:06 Оценка сложности помогает понять, во сколько раз замедлится программа при увеличении данных. Пример: программа, работающая за линейное время, замедлится в 10 раз при увеличении данных в 10 раз. Важно понимать, во сколько раз замедлится программа, а не конкретные константы.
Пример с таблицей умножения 25:03 Программа для сложения таблицы умножения работает за O n^2. Пример с более сложным кодом: сложность остается O n^2, несмотря на дополнительные действия. Константы не важны, важно только, во сколько раз замедлится программа при увеличении данных.
Введение в сложность алгоритмов 27:33 В реальной жизни графики времени работы программы не всегда линейны. Пример программы на Python, проверяющей наличие циклов в графе. Создание массива и чтение данных через стандартные потоки ввода-вывода.
Универсальность ввода-вывода 28:30 Ввод данных через стандартные потоки позволяет поддерживать разные языки программирования. Это может быть неудобно, но позволяет использовать любимые языки. Создание массива и чтение числа с консоли не зависят от размера входных данных.
Чтение матрицы смежности 29:25 Чтение матрицы смежности графа требует n^2 операций. Чтение строки длиной n занимает n^2 действий. Вложенные циклы и элементарные операции увеличивают сложность до n^3.
Разные сложности частей программы 31:17 Программа имеет четыре разные сложности: n^1, n^2, n^3 и n^4. При росте данных разные части программы замедляются по-разному. Чтение данных и создание массива имеют большую константу, что замедляет работу.
Оценка сложности алгоритма 33:13 При больших значениях n, даже простые операции могут занимать много времени. Алгоритм оценивается по самой медленной части, которая становится доминирующей при больших значениях. Важно учитывать сложность алгоритма для его худшей части.
Пример задачи с разной сложностью 35:08 Задача: найти самый частый символ в строке с большим алфавитом. Наивное решение: перебирать все символы и считать их количество. Более умное решение: использовать множество всех символов строки для ускорения.
Ускорение алгоритма 38:31 Перебор всех символов можно ускорить, используя множество всех символов строки. Это уменьшает сложность алгоритма до n^m, где m - размер алфавита. Современные языки программирования позволяют ускорить процесс до нескольких секунд.
Введение в анализ текста 40:17 Обсуждение длины строки и размера алфавита. Пример с текстом "Война и мир", где размер алфавита оценивается в 100 символов. Ускорение анализа текста за счет использования множества символов.
Создание словаря для подсчета символов 41:11 Создание словаря для подсчета количества вхождений каждого символа. Пример кода на Python для подсчета символов и нахождения самого частого символа. Объяснение логики работы с символами и словарем.
Оптимизация кода 44:15 Обсуждение возможности вынести подсчет символов из цикла. Сравнение эффективности различных подходов к оптимизации. Важность учета времени и памяти при анализе алгоритмов.
Оценка сложности и памяти 46:37 Обсуждение сложности алгоритма и его симтотики. Важность учета потребления памяти при анализе алгоритмов. Пример сравнения алгоритмов по времени работы и потреблению памяти.
Заключение 50:08 Обсуждение различных подходов к реализации алгоритма. Пример реализации алгоритма с использованием строки по байтам. Подведение итогов и важность учета всех аспектов при анализе алгоритмов.
Преобразование строки в множество 50:21 Для преобразования строки в множество требуется вся строка. Множество занимает порядка k элементов, где k всегда меньше или равно n. Потребление памяти: n + k, где n - длина строки, k - размер множества.
Обработка строки посимвольно 51:20 В некоторых случаях строку можно обрабатывать посимвольно. Это полезно, когда данные поступают по сети или в буфер. Алгоритм позволяет обрабатывать данные на месте, не сохраняя всю строку в памяти.
Преимущества по памяти и сложности 52:20 Алгоритм эффективен по времени и памяти. Он не сложнее предыдущих алгоритмов и может быть реализован с комментариями и нормальными названиями переменных. Хороший алгоритм не всегда сложнее, чем неэффективный.
Сумма последовательности 54:03 Задача о сумме последовательности решается без запоминания всей последовательности. Достаточно помнить накопленную сумму. Алгоритм обрабатывает пустой массив и выводит ноль.
Поиск максимального числа 55:54 Задача о поиске максимального числа в последовательности. Алгоритм должен учитывать возможность отрицательных чисел. Решение: инициализировать максимум первым числом и заменять его при необходимости.
Обработка частных случаев 57:54 В задачах с ограничениями, такими как положительные числа, не нужно проверять корректность данных. Программа должна работать корректно только в допустимых условиях. Примеры частных случаев будут тестироваться.
Проверка кода 59:35 Проверьте тесты из условия задачи. Убедитесь, что код работает на примерах. Выводите только то, что требуется в формате ввода и вывода.
Общий и особые случаи 1:00:20 Проверьте общий случай, чтобы убедиться, что программа работает. Проверьте особые случаи, такие как первый и последний элементы последовательности. Учитывайте возможные ошибки, такие как плюс-минус один элемент.
Тестирование на особые случаи 1:01:20 Проверьте, как программа работает с одинаковыми элементами и пустой последовательностью. Учитывайте случаи, когда все числа отрицательные. Убедитесь, что программа работает за линейное время.
План тестирования 1:03:08 Составьте план тестирования, учитывая все возможные случаи. Проверьте, что программа работает на всех допустимых данных. Учитывайте ошибки на плюс-минус один элемент и пустые последовательности.
Порядок действий 1:04:30 Сначала решите примеры на бумажке, чтобы убедиться в понимании задачи. Составьте несколько примеров для лучшего понимания задачи. Проверьте обработку пустой последовательности и последовательности из одного элемента.
Покрытие тестами 1:06:08 Проверьте краевые эффекты, такие как первый и последний элементы. Убедитесь, что все ветки кода покрыты тестами. Используйте маленькие тесты для быстрого нахождения ошибок.
Маленькие тесты 1:07:07 Маленькие тесты помогают быстро найти ошибку. Один тест должен проверять одну ошибку. Цель тестов – облегчить поиск места, где программа сломалась.
Тестирование программ 1:07:49 Создавайте тесты, где одна ошибка проявляется четко. Разделяйте тесты на случаи с одним элементом и всеми отрицательными числами. Это помогает быстрее найти и исправить ошибки.
Стресс-тестирование 1:08:48 В реальной разработке стресс-тестирование называется нагрузочным тестированием. Важно рассчитывать время работы алгоритма до его написания. На интерпретируемых языках можно рассчитывать на несколько десятков миллионов операций в секунду.
Генерация тестов 1:10:32 Генерируйте короткие тесты и запускайте их в вечном цикле. Если ошибка есть, она проявится на маленьком тесте. Длинные последовательности могут не дать результата.
Пример с сортировкой 1:11:32 В Python есть стандартная функция сортировки, которая помогает отловить ошибки. Используйте стандартную функцию для сравнения с вашим кодом. Если тест не проходит, отлаживайте по шагам.
Заключение 1:14:38 Эффективные решения часто бывают красивыми и понятными. Пишите код, который можно читать и исправлять. Понимание работы стандартных функций помогает в написании кода. Не всегда нужно самое эффективное решение, иногда достаточно простого и работающего. Тестирование кода должно быть приоритетом, чтобы избежать багов в промышленном коде.
Оценка сложности программ 1:19:13 Оценка сложности программ и алгоритмов - сложная тема, требующая докторских диссертаций. В лекции будут рассмотрены примеры оценки сложности для сложных случаев. Книги, такие как "Алгоритмы: построение и анализ", содержат главы о сложности алгоритмов.
Влияние оптимизации на производительность 1:20:08 Оптимизация кода влияет на константу, но не на симптоматику алгоритма. В высоконагруженных сервисах важно знать, как язык оптимизирует код. В учебных задачах важен не только худший случай, но и средняя скорость работы алгоритма.
Пример задачи с поиском самого частого символа 1:22:03 В худшем случае все буквы в тексте будут разными, что приведет к квадратичной сложности. В реальной жизни важна средняя скорость работы алгоритма. В задаче с текстом важно учитывать размер алфавита, который часто меньше длины текста.
Распределение рейтинга и задачи 1:23:28 Цель - найти человека, который решит все 40 задач. Важно решать как можно больше задач, но не переживать из-за рейтинга. Главное - это знания и сохранение здоровья и хорошего настроения.
Дедлайны и тестирование 1:24:43 Дедлайны для задач наступают за час до разбора. В тестирующей системе можно увидеть, на каком тесте программа дала неправильный ответ. Для помощи в поиске ошибок создан бот, который выдает тесты и правильные ответы.
Методы оценки сложности 1:27:03 В практике чаще всего используется оценка сложности по большому. Важно понимать, во сколько раз замедляется программа при увеличении параметров. В первом примере сложность оценивается в квадрат, что объясняется упрощенно.
Оценка сложности кода 1:27:55 Оценка сложности кода зависит от количества посылок и штрафов. Условия тестирования для разных языков программирования в основном одинаковые. Python удобен для написания кода, но требует эффективности, в то время как C++ позволяет писать неэффективно, но неприятно.
Преимущества и недостатки языков 1:28:50 Python позволяет писать быстро и красиво, но требует эффективности. C++ позволяет писать неэффективно, но всегда неприятно. Другие языки программирования находятся между этими двумя крайностями.
Тестирование и оценка времени выполнения 1:29:50 Программа, работающая дольше одной секунды, считается завершенной. Превышение времени выполнения не всегда означает, что программа работала неправильно. Задачи по определению сложности кода помогают набить опыт.
Использование библиотек и сложность алгоритмов 1:30:47 В Яндекс.Контесте можно использовать стандартные библиотеки. Обращение к элементу словаря в Python имеет линейную сложность. Оценка сложности алгоритмов учитывает время на выделение памяти.
Вопросы и поддержка в чате 1:34:45 В чате в Telegram можно получить помощь от сотрудников Яндекса и других участников. Важно формулировать вопросы четко и содержательно. Комьюнити в чате помогает быстро получать ответы и решать проблемы.
