Transcription
YouTube завален тонами информации о том, что вам нужно выучить. Бесплатный курс на выбор по любому языку, список книг по теории, которые стоит прочитать, куча туториалов по любой технологии по принципу: "Бери и делай". Но среди огромной базы знаний, где есть абсолютно всё, практически никто не говорит о том, как этими знаниями воспользоваться. Как сделать так, чтобы теория перестала быть просто теорией и отдала плоды в виде ваших навыков мышления и карьеры?
Почему об этом не принято говорить? Потому что спрос рождает предложение. На урок по очередному языку придут тысячи желающих его освоить, потому что это легко. На урок по написанию алгоритмов придут десятки человек, потому что это сложно.
Да, у всех людей разная мотивация войти. Кто-то приходит сюда с детства ради идеи, чтобы воплощать свои задумки и мечты, становясь супергероем, которому подвластен цифровой мир. Кто-то приходит сюда, чтобы хорошо зарабатывать и кардинально изменить свою жизнь, а у кого-то это комбинация одного и второго. Но кто бы вы ни были, всех вас объединяет одно. Каждый из вас хочет, чтобы время, потраченное на изучение программирования, дало ему то, что он хочет.
Можно годами писать код, годами читать книги или годами крутить у себя в голове ту картину мира, в которой бы ты хотел быть. Но на вершину своей мечты всё равно заберётся тот, кто будет лучше других. Прикол в том, что так думают все. Нет смысла что-то делать, потому что всегда кто-то будет лучше меня. Это как гонка со своей тенью, которую невозможно обогнать, поэтому проще ничего не делать.
Карьерный рост и зарплата айтишников в сотни тысяч долларов в год, о которых мы изредко слышим, воспринимаются как звёзды в небе, о полёте на которые можно только мечтать. Но мечтать о достижении или достигать — это наш выбор. Работать в крупной технологической компании с перспективой большого роста означает соответствовать этой компании своим уровнем знаний и навыков.
Если мы посмотрим на то, что спрашивают в таких компаниях, как Google, Microsoft, Яндекс или компании уровнем ниже, Booking, TНКв, PayPal и другие, то мы не увидим там банальных вещей за разряды. Что делает эта функция в фреймворке? Там спрашивают алгоритмы. Алгоритм — это преобразование проблемы в код. Есть какая-то человеческая проблема из реальной жизни, описанная словами, и есть решение в виде кода, которое вам нужно написать, чтобы компьютер смог эту задачу выполнить, да ещё и за оптимальное время.
Работодателю крупной компании с высоконагруженными системами всё равно, сколько теорий вы знаете, если вы этой теорией воспользоваться не можете. Их задача — отобрать самых умных программистов из тех, кто есть. Но ум не равно количеству знаний. Ум — это способность мыслить и находить логически верные решения. Но проблема в том, что до алгоритма нельзя додуматься, если раньше ты его никогда не писал.
Если вам кажется, что знания алгоритмов и структур данных нигде не нужны, кроме собеседований, то спешу вас огорчить. В основе любого сложного высоконагруженного IT-продукта лежат исключительно алгоритмы и структуры данных. Нельзя быть хорошим программистом, если ты не можешь придумать решение, чтобы твой код работал быстро, мог масштабироваться и выдерживать большие нагрузки.
Самое сложное в изучении алгоритмов — это понять, в какой последовательности их изучать и где брать эти знания. В какой последовательности изучать и в каких вещах из реальной жизни это используется, мы сейчас подробно разберём. А по поводу того, где всё это можно изучить и сэкономить себе кучу времени, в своём Telegram-канале в закреплённом посте я написал о том, что набираю группу, с которой мы вместе с вами подробно будем шаг за шагом всё это изучать. Там же будет прикреплён файл со всеми темами, о которых мы сейчас будем говорить. Ссылка на Telegram-канал в описании, закреплённом комментарии.
Сейчас мы с вами совершим путешествие по двадцати шести темам, на которых построен весь Computer Science. Темы, которые спрашивают и которые нужно знать. По ним существуют тысячи задач, но спешу вас обрадовать. Вам не нужно все их решать. Задачи имеют свойство со временем повторяться, лишь слегка меняя свои условия. Главное — это понять принцип решения. И для этого достаточно будет прорешать всего 100 задач по всем этим темам, чтобы совершить в своём мышлении огромный рывок.
Перед тем, как мы составим пошаговый план по практике алгоритмов, нужно понимать, что двигаться к разбору подобных тем и решению задач по ним стоит только при условии, что вы уже знакомы с базовой частью любого языка программирования. И если вы специалист с опытом, то наверняка знакомы с ситуацией, когда знания есть, а карьерный рост застрял. Именно поэтому Яндекс Практикум Pro помогает прокачать свои скиллы и сделать из работы карьеру тем, кто уже в профессии, но хочет расти дальше.
На платформе Практикума Pro представлено более 100 курсов по IT и Digil направлениям, начиная от программирования, анализа данных и искусственного интеллекта, заканчивая дизайном, менеджментом и маркетингом. Все программы постоянно обновляются под требования рынка, чтобы уже сегодня вы изучали то, что появилось только вчера. А в лаборатории образовательных технологий Практикума PRO дополнительно анализируют, как учится профи, чтобы ещё быстрее привести вас к цели. Во время учёбы вы попрактикуетесь качать навыки с искусственным интеллектом, а не на отдельных курсах по нейронкам. Освойте Levelup инструменты и промжиниринг. Практикум Pro зашили туда экспертизу тех, кто сам создаёт искусственный интеллект. Преподаватели — не теоретики, а практики из Bеctech, которые сами падали и выходили из кризисов. Будете учиться у тех, чья работа меняет рынок и задаёт в нём тренды. Новые скиллы потестите на своих текущих рабочих задачах ещё во время обучения, где бы вы сейчас не работали. У Практикума сильная комьюнити выпускников. Познакомитесь, прокачаете навыки, найдёте коллег и поддержку. Обучение можно встроить даже в самый напряжённый график. А если календарь совсем забит, можно выбрать трек без дедлайнов. Почти у каждого курса есть бесплатный водный модуль. Для того, чтобы понять, подходит ли вам по уровню данный материал и нравится ли вам такой формат. Переходите по ссылке в описании или сканируйте QR-код на экране. Поехали.
Самую первую вещь, которую нужно знать до того, как приступить к практике по программированию — это понимать язык компьютера. Любые низкоуровневые манипуляции сводятся к чтению и манипуляции битами и байтами чисел, двоичной и шестнадцатеричной системе соответственно. Это одна из двух теоретических тем, которые здесь есть, но без которой понять следующую тему будет крайне затруднительно. Это битовые операции, которые сразу же помогут закрепить предыдущие знания и найти им реальное применение. Битовая операция — это must-have низкоуровневого программирования, такого как написание драйверов или программирование микроконтроллеров. Но есть и более высокоуровневые примеры, где эти знания используются постоянно. Например, флаги и права доступа, оптимизация арифметических операций или, например, вычисление контрольной суммы CRC в конце файлов и протоколов.
Далее мы продвигаемся к более понятным для современного программиста вещам. Это абстрактные структуры данных, коих существует огромное множество из-за скорости их работы и специфики хранения данных. И вот для того, чтобы понимать, насколько код, который вы пишете, будет выполняться быстро, нужно разобраться с оценкой сложности алгоритмов (Big O) и памяти. Та вещь, без которой изучать алгоритмы и структуру данных нет никакого смысла, ведь вы всё равно не поймёте, где их применять.
И вот для того, чтобы это понимание постепенно начало к нам приходить, мы знакомимся с первой самой базовой структурой данных — одномерными массивами. Массивы используются везде, и задач, которые решаются через массивы, огромное количество. К слову, это самый большой раздел в этом перечне тем. Но далеко не с каждой задачей массив справляется хорошо, и оценка по Big O его слабых и сильных сторон поможет понять, что из себя на самом деле представляет эта структура. Чтобы уметь решать задачи по массивам, мало просто уметь пользоваться перебором в цикле. Есть задачи, которые можно решить только обладая знаниями, техникой этого решения. Например, это задача на два указателя, которые позволяют ускорять код, отказаться от вложенных циклов и дополнительного выделения памяти. Используется это во множестве реальных задач, например, в финансовой сфере для поиска отрезков роста и спада или, например, для синхронизации логов по времени с разных серверов.
Следующая тема, которая является прямым продолжением одномерных массивов — это строки. Строки — это главный вид информации для человека, который по совместительству тоже является всего лишь одномерным массивом, но только элементы которого представлены по-разному в зависимости от стандарта и кодировки. Ключ к пониманию кодировок лежит в темах с системами исчисления и битовыми операциями, поэтому смело можно сказать, что полное понимание темы строк полностью опирается на все предыдущие темы, которые мы прошли. А сами задачи на поиск, проверку и изменение строк — это то, что используется абсолютно везде.
Скользящее окно, которое мы относим сюда же — это ещё одна техника решения задач. Она применяется не только на массивах, но на массивах отрабатывается лучше всего, так как работать зачастую приходится с подмассивами, как с небольшим окном, по которому мы плавно перемещаемся. Где это используется, например, для расчёта средней суммы всё в том же финансовом секторе или, например, для подсчёта количества запросов от пользователей за окно времени для установки лимитов или для обработки сетевых пакетов при передаче данных по сети.
Прямым продолжением одномерных массивов являются массивы двумерные или, говоря по-другому, матрицы. Алгоритмы на трансформацию матриц тоже требуют знания определённых техник. Массивы используются в таких вещах, как распознавание лиц в обработках изображений, например, в видеонаблюдении и даже для обработки МРТ в медицине. И ещё одна тема здесь же, которая завершает большой раздел с массивами — это интервалы. Это задача на поиск диапазонов, которые можно встретить, например, в календарных сервисах по планированию встреч, в системах бронирования при поиске свободных дат или в выборах при определении пересечении объектов. Как вы видите, раздел с массивами включает в себя сразу шесть тем и покрывает огромное количество задач, которые у вас могут спросить на собеседовании.
Тем не менее, массивы — это только начало пути по направлению к более сложным структурам данных. Но начнём мы с самой простой из сложных — со стека. Почему? Потому что стек в своей работе полностью опирается на массив и имеет очень простую логику работы, где последний пришёл — первый вышел. За счёт этой особенности стек позволяет решать особый вид задач, на который и не подумаешь, что они решаются через стек, если только не прорешать эти задачи заранее. Сфера использования — это парсеры, например, парсинг HTML-кода на проверку корректности вложенности тегов или вычисление арифметических выражений с приоритетом. Либо самое простое, с чем сталкивался каждый из вас — это навигация в браузере кнопками назад и вперёд.
Но если кто-то приходит последним и уходит первым, значит, кто-то должен приходить первым и иметь возможность первым же уходить. Так ведёт себя обычная человеческая очередь, логика которой реализована в одноимённой структуре данных — очередь. Хоть она и не работает за счёт массивов, но открывает путь к более сложным структурам данных, которые реализуются за счёт узлов. Как и следует из её названия, используется она там, где важен порядок в последовательности данных, например, асинхронной передаче данных по сети, запись файлов на диск или программное моделирование очереди обслуживания клиентов.
На эти две темы целиком и полностью упирается тема монотонных последовательностей. Это упорядоченный набор элементов возрастающей или убывающей последовательности для быстрого получения ближайшего меньшего или большего значения. Реализуется она, как правило, через стеки и очереди. Это часто используется в анализе данных, например, в анализе фондового рынка для нахождения ближайших высоких цен, в задачах мониторинга температуры и даже в задачах удаления шума из изображений.
Разобравшись с этими темами, мы можем продолжать двигаться в сторону усложнения структур данных. И доезжаем до темы, которая называется связанные списки. Сама по себе эта структура является основой для ещё более сложных структур и сильно напоминает собой очередь, но только в универсальном виде. Многим кажется структура простой, но задачи по ней бывают такие адские, до которых, чтобы додуматься, приходится ломать себе мозг. Сфера применения универсальная, начиная от сложных систем по типу компиляторов, заканчивая использованием её в алгоритмах кэширования.
Следующая структура данных является прямым продолжением всех наших тем, так как в своих базовых версиях опирается она как на массивы, так и на связные списки. Название этой структуры — хэш-таблица. Это вторая по популярности структура данных после массивов. Используется абсолютно везде, так как по ключу позволяет хранить данные любых типов. Эта структура сложна в разборе своей реализации, но относительно проста в теме решения по ней задач. И именно на этой теме мы заканчиваем разбор итеративных алгоритмов, понятных для мозга, и отправляемся с вами в мир магии рекурсии, где будет непонятно ничего.
Дело в том, что наш мозг не умеет мыслить рекурсивно, поэтому любую рекурсию нужно уметь переводить в линейно понятный для мозга вид. Это возможно только благодаря знаниям в работе стека, как структуры данных, так и аппаратного. Но для чего рекурсия вообще нужна? Нужна она для обработки множества древовидных структур данных. Используется всё в том же парсинге, например, парсинг JSON. Или самый простой пример из реальной жизни — это обход файловой системы по файлам и папкам. Либо ещё проще — обработка древовидных комментариев на сайте, с которыми сталкивался каждый из вас.
Вот, чтобы подготовиться к обходу более сложных древовидных структур, нам помогут задачи по следующей теме: поиск с возвратом, которая является более сложной, углублённой техникой простых рекурсивных задач. Эта техника помогает реализовать три важные вещи: это перебор всех возможных вариантов, совершение всех возможных перестановок и выполнение различных сочетаний. Пример использования — это генерация паролей, построение маршрутов, решение головоломок и так далее.
После того, как мы разберёмся с техниками рекурсивного обхода, мы можем переходить к ещё более сложным структурам данных — деревьям. Деревьев существует много, и каждая из них хороша в своём спектре задач. Стандартное двоичное дерево позволяет производить арифметические операции, используется в машинном обучении и некоторых алгоритмах сжатия данных, таких как Хаффмана. Двоичное дерево поиска — это всё то же двоичное дерево, но хранящее данные в упорядоченном виде, благодаря чему отлично подходит для быстрого поиска и является основой для более сложных деревьев, которые, например, используются в базах данных для хранения данных. Двоичная куча, несмотря на своё название, это тоже дерево. Но вот только в отличие от двоичного дерева поиска, оно не предназначено для поиска элементов, а предназначено для тех случаев, где нужно быстро получить приоритетный вариант. Например, планировщики задач операционной системы, где нужно выбрать задачу с наивысшим приоритетом. Или, например, приоритизация пакетов при передаче по сети, или мониторинг топа десяти популярных запросов на сайте или отслеживание ближайшего доступного времени в системах бронирования. Префиксные деревья тоже хороши в своём деле и отлично умеют хранить текстовые данные. Опираются они на работу хэш-таблицы и помогают реализовать такую вещь, как всплывающие подсказки текста, когда мы только начинаем набирать первые буквы. И задачи по этим деревьям отлично помогают на практике понять, как это работает.
Из поиска элементов по деревьям мы плавно переходим к поиску элементов в графе. Граф — это ещё одна структура данных, которая собрала в себе всё, что мы знали до этого. Она может быть реализована через массив, связанный список, хэш-таблицу и даже через битовые структуры данных. Задачи в графах делятся на два вида: поиск в глубину и поиск в ширину. Типичными задачами поиска в глубину являются, например, системы сборки, где нужно определить зависимость между пакетами или решение головоломок по типу кроссвордов и так далее. Задачами на поиск в ширину являются задачи для поиска кратчайшего пути из точки А в точку Б, например, в играх или навигаторе, или алгоритмы поиска рекомендаций друзей в социальных сетях. И даже в роботе-пылесосе используются такие алгоритмы для поиска оптимального маршрута.
На этом задачи на сложные структуры данных заканчиваются, и мы передвигаемся к теме, с которой, как правило, наоборот, изучение алгоритмов только начинается. Это тема сортировок. Но почему я её поставил практически в самый конец? Потому что проблема сортировок в том, что их очень много и у них у всех разная сложность, и они создают очень сильную путаницу в голове на начальном этапе. Чтобы сортировки вас не путали, лучше всего поставить их в самый конец и возвращаться к данным алгоритмам только тогда, когда это будет необходимо. Думаю, не нужно объяснять, что сортировки используются везде, где есть набор данных, например, в вашей папке с изображениями на рабочем столе, которые кнопками сверху можно сортировать по имени, дате и размеру.
На отсортированных массивах, а именно на массивах, разбираются подобные задачи, основывается следующая тема, которая называется двоичный поиск. Она слишком лёгкая, чтобы ставить её в самый конец, но она обладает всё теми же свойствами, которые не позволяют её лепить куда-то в начало. Задачу на двоичный поиск зачастую используют рекурсивный подход, а сам поиск с помощью данного алгоритма работает только в уже заранее отсортированном массиве. Поэтому довольно логично, что именно после сортировок данная тема идёт. Примеры задач из реальной жизни — это, например, минимальное время, за которое выполнится задача или минимальный бюджет, при котором сможет выполниться условия.
Последняя и самая хардкорная тема из всего, с чем вы можете столкнуться в классическом Computer Science — это динамическое программирование. Не потому, что там много кода, а потому, что додуматься до решения задачи через динамику, а самое главное понять, что через неё можно решить — это весьма нетривиальная задача. Алгоритмы по динамическому программированию делятся на мемоизацию и табуляцию. Это два способа оптимизации алгоритмов, которые делают их быстрее. Как правило, используются они для оптимизации рекурсивных задач. Мемоизация позволяет запоминать результаты вычислений. Табуляция позволяет сохранять результаты вычислений в таблицу. Это апогей, после которого любые задачи покажутся вам чем-то суперлёгким и незначительным. Но зато, пройдя весь этот путь, вы станете совершенно другим человеком и совершите огромный рывок в своём программистском мышлении, а ваш рост по карьерной лестнице 100% не заставит себя долго ждать.
Если ты не хочешь тратить время и разбираться с таким огромным объёмом информации сам, то можешь вступить в мой закрытый Telegram-канал, где мы за несколько месяцев пройдём все эти темы и прорешаем более 100 задач не просто на уровне кода, а визуализируя, как каждый алгоритм работает и выстраивая систему мышления, которая позволит тебе в будущем, когда ты столкнёшься с подобными задачами на собеседовании, додуматься до решения на основе того опыта и понимания, который у тебя уже будет. Узнать более подробно и записаться в группу можно в моём Telegram-канале. Вся информация будет в закреплённом посте. Все ссылки есть в описании и закреплённом комментарии. Удачного обучения и до скорого.