Сертификат | Школа Cronis

Модуль 1

Двоичная система счисления

Системы счисления
Из десятичной в двоичную и обратно
Принцип работы процессора
Двоичное представление отрицательных чисел
Сложение и умножение двоичных чисел
Вычитание двоичных чисел
Двоичное представление плавающей точки
Решение задач

Битовые операции

Размерности величин
Адресация памяти
Big & Little Endian
Примитивные битовые операции
Классические битовые операции
Сжатие параметров
Битовый вектор
Реализация битового вектора
Решение задач

Стек и очередь

Причины создания стека
Аппаратный стек x86
Аппаратный стек
Алгоритм работы процессора с данными
Визуализация потока данных в компьютере
Размещение стека в памяти
Работа с аппаратным стеком
Что принес стек в программирование
Переполнение стека
Трассировка кода
Раскручивание и скручивание
Стек и типы данных
Пример работы кадров стека
Программный стек
Очереди
Решение задач

Кодировки и строки

ASCII
Работа с ASCII-строками
Кодовые страницы
OEM кодовые страницы
Mojibake
ANSI и Microsoft
Проблема иероглифов
Single-byte Character Set
Double-Byte Character Set
Unicode
Basic Multilingual Plane
Хранение символов из кодовых страниц
Кодировки: USC-2, UFT-8, UTF-16, UTF-32
Суррогатные пары
Причина использования UTF-16 в языках программирования
Типы строк: C-String, P-String, Immutable String
Проблема конкатенации строк
Проблема получения подстроки
StringBuilder
Решение задач

Рекурсия

Определение рекурсии в реальном мире
Виды рекурсивных функций
Первая рекурсивная функция
Скелет простейшей рекурсивной функции
Правило шести
7 правил написания рекурсивных функций
Критичность размера меньшей задачи
Упрощение рекурсивного кода
Трассировка рекурсивных функций
Замечания к правилам написания рекурсивной функции
Функция с двумя рекурсивными вызовами
Построение дерева рекурсивных вызовов
Рекурсия в цикле
Решение задач

Оценка сложности алгоритмов. Big O

Причины изучения оценки сложности
Математическая функция
Оценка сложности
Случаи сложности
Сравнение сложностей
Сравнение математических функций
Нотация Big O
Решение задач

Оценка типичных сложностей

Оценка типичных сложностей
Сложение и умножение
Сложность log N
Строки и оценка сложности
Сложность рекурсивных функций
Амортизационный анализ
Сложность по памяти
Решение задач

Основы теории вероятностей и логики

Множества
Комбинаторика
Базовые понятия вероятностей
Произведение событий
Сумма событий
Закон распределения
Математическое ожидание
Метод дедукции
Оптимизация худшего случая
Решение задач

Модуль 2

Массив и связанный список

Виды и особенности массивов
Связанный список
Операции над связанным списком
Реализация однонаправленного связанного списка
Реализация двунаправленного связанного списка
Реализация поиска
Реализация вставки
Реализация удаления из односвязного списка
Реализация удаления из двусвязного списка
Подход Runner
Решение задач

Хеш-функция

Ассоциативный массив
Хеш-функция
Метод деления по модулю
Метод умножения
Хеш объектов и чисел
Попытка создания хеш-таблицы
Проблемы хеш-функций
Отрицательный хеш
Проблема хешей и индексов
Правила вычисления хеша и индекса

Хеш-таблица

Виды хеш-таблиц
Метод цепочек
Коэффициент заполнения
Реализация метода цепочек
Оценка сложности метода цепочек
Линейный поиск
Реализация линейного поиска
Квадратичный поиск
Реализация квадратичного поиска
Двойное хеширование
Реализация двойного хеширования
Сложность открытой адресации
Сравнение производительности хеш таблиц
Универсальное хеширование

Поиск с возвратом. Динамическое программирование

Возврат составного значения из рекурсии
Поиск с возвратом
Задача полного перебора
Процессор, рекурсия и стек
Риски рекурсивных решений
Рекурсия в итерацию
Динамическое программирование
Оптимальный рюкзак
Использовать или нет рекурсию
Головная и хвостовая рекурсия
Решение задач

Модуль 3

Бинарное дерево поиска

Проблема поиска и сортировки
Бинарное дерево и бинарное дерево поиска
Вставка и поиск узла
Обход бинарного дерева поиска
Удаление узла
Реализация вставки и поиска узла
Реализация обхода бинарного дерева поиска
Реализация удаления узла
Решение задач

АВЛ-дерево

Определение АВЛ-дерева
Условный алгоритм вставки в АВЛ-дерево
Поиск места для вставки нового узла
Балансировка. Высота дерева
Поиск несбалансированного поддерева
Баланс фактор
Повороты дерева
Количество балансировок после вставки нового узла
Удаление из АВЛ-дерева
Реализация АВЛ-дерева
Решение задач

Красно-черное дерево

Определение красно-черного дерева
Виды узлов
Определения для красно-черного дерева
Правила работы
Причина работы
Вставка
Удаление
Реализация
Решение задач

Полное бинарное дерево, куча, префиксное дерево

Определение полного бинарного дерева
Определение бинарной кучи
Поиск в куче
Вставка в кучу
Амортизация при вставке в кучу
Извлечение корня кучи
Создание кучи из набора данных
Хранение кучи в памяти
Реализация кучи
Реализация кучи в Java
Префиксное дерево
Вставка в префиксное дерево
Поиск в префиксном дереве
Удаление из префиксного дерева
Реализация префиксного дерева
Решение задач

Базовые сортировки

Параметры сложности сортировки
Сортировка пузырьком
Сортировка выбором
Сортировка вставками
Сравнение квадратичных сортировок
Сортировка слиянием
Сортировка кучей
Поразрядная сортировка
Решение задач

Быстрая сортировка Хоара

Распутанный массив
Задача расспутывания массива
Местоположение опорного элемента
Варианты расстояний между указателями
Сокращение функции partition
Визуализация алгоритма Хоара
Быстрая сортировка алгоритмом Хоара
Сложность алгоритма Хоара
Решение задач

Быстрая сортировка Ломуто. Внешняя Сортировка. Двоичный поиск

Алгоритм Ломуто
Реализация алгоритма Ломуто
Сложность алгоритма Ломуто
Ускорение быстрой сортировки
Быстрая сортировка против всех
Внешняя сортировка
Реализация внешней сортировки
Двоичный поиск
Решение задач

Графы

Определения и виды графов
Представления графа
Реализация графа
Поиск в глубину
Реализация поиска в глубину
Поиск путей в графе
Поиск циклов в графе
Топологическая сортировка
Сложность поиска в глубину
Поиск в ширину
Реализация поиска в ширину
Поиск кратчайшего пути на основе поиска в ширину
Реализация поиска кратчайшего пути на основе поиска в ширину
Двунаправленный поиск в ширину
Реализация двунаправленного поиска в ширину
Сложность одна и двунаправленного поиска в ширину
Поиск циклов на основе поиска в ширину
Алгоритм Дейкстры
Реализация алгоритма Дейкстры
Решение задач

Модуль 4

Процесс интервью

Как проходит интервью
Почему даже лучших кандидатов могут отвергнуть
Умение решать проблемы важно
Знание computer science необходимо
Визуализация мыслей позволяет сосредоточиться на главном
Как отбираются вопросы для интервью

Детали проведения интервью

Amazon
Apple
Facebook
Google
Microsoft

Прежде, чем пройти интервью

Где взять опыт
Написание резюме
Алгоритм подготовки к интервью

Общие вопросы на интервью

Какие Ваши слабости?
“Итак, расскажите о себе”
Как и какие вопросы задавать интервьюеру
Правильное описание проектов, где Вы участвовали
Как отвечать на общие вопросы
Думайте, как могут интерпретировать Ваши слова