LeetCode - One-Year Challenge

1     LeetCode

Завершился челендж ежедневного решения задач на LeetCode на протяжении года (за исключением отпусков).

За год решил 707 задач. Из них: 261 - легкий уровень, 365 - средний уровень, 81 - сложный уровень.

В основном решал ежедневные задачи и среди “избранных” тем. Самые интересные темы: Trie, Dynamic Programming, Design.

Почти все задачи решены на языке C++.
Пробовал решать на Go. Go не подходит для алгоритмических задач, слишком ограничен. Язык C++ поддерживает намного больше концепций, позволяющих решить задачу более красиво и оптимальнее.

Решал задачи для подготовки к алгоритмическим секциям на интерью. Все секции успешно пройдены.
Больше не планирую заниматься решением задач на алгоритмы. Если хочется что-то порешать, то лучше попробовать CTF задачи. Это намного практичнее и разнообразнее.

Мой профиль: amyasnikov - LeetCode Profile

2     Для решения большинства задач достаточно знать

• Бинарный поиск
• Рекурсия
• Сортировка (быстрая, подсчетом)
• Динамическое программирование
• Жадные алгоритмы
• Поиск с возвратом
• Поиск в глубину
• Поиск в ширину
• Обход дерева (pre-order, in-order, post-order)
• Метод скользящего окна
• Хеш таблица
• Хеширование
• Двоичное дерево поиска
• Префиксное дерево
• Двусторонняя очередь
• Приоритетная очередь
• Монотонный стек
• Односвязный/двусвязный список
• Матрица смежности
• Непересекающиеся множества
• Особенности языка, на котором выполняется реализация

3     Как оптимизировать алгоритм на C++

• Использовать move семантику вместо копирования, если исходная переменная больше не нужна
• Использовать array вместе vector, если размер контейнера заранее известен и не будет изменен
• Использовать string_view вместо string, если исходная строка не будет изменена
• Использовать мемоизацию, если функция часто вызывается с одинаковыми параметрами
• Использовать vector<...> вместо unordered_map<...>, если индексы находятся в некотором диапазоне и плотное заполнение
• Использовать unordered_map вместо map, если упорядоченность не требуется
• Использовать deque вместо vector, если количество объектов в контейнере меняется с течением времени
• Использовать lower_bound для поиска в отсортированном контейнере
• Использовать set для имитации многократного бинарного поиска
• Использовать array<uint8_t, 26> для группировки символов без учета позиций
• Использовать кастомный функтор в map, unordered_map, sort, lower_bound, …
• Использовать массив индексов, отсортированных по значениям исходного контейнера, вместо сортировки контейнера,
  если контейнер нельзя модифицировать (и копию контейнера иметь невыгодно или нужно помнить исходную позицию элемента до сортировки)

4     Этапы решения задачи на leetcode

• Понимание условий задачи
  • Что подается на вход, что ожидается на выходе
• Обдумывание различных вариантов как решить задачу алгоритмически
  • Декомпозиция задачи на подзадачи
  • Оценка общей сложности (средняя/наихудшая)
• Выбор конкретного варианта с учетом возможностей/библиотек языка X
• Реализация задачи на языке X
• Тестирование
  • Запуск дефолтных тестов
  • Запуск кастомных тестов для учета граничных и вырожденных ситуаций
• Исправление багов
• Оптимизация реализации по памяти/производительности
• Сравнение с реализациями других участников и попытки улучшить свое решение