Внутреннее устройство stl-контейнеров и алгоритмическая сложность

Абстрактные типы данных (abstract data types):
1) Стек
2) Очередь
3) Очередь с приоритетом (priority queue, https://acm.khpnets.info/)
4) Массив
5) Динамический массив
6) Связный список
7) Ассоциативный массив

Хабр:

1) Многообразие связных списков https://habr.com/ru/articles/814955/

Структуры данных (data structures):
1) Кольцевой буфер
2) Calendar queue
3) Двусторонняя очередь (deque)
4) Куча
5) B-tree
6) Двоичное дерево

7) Двоичное дерево поиска

8) Двоичная куча (английская полнее https://en.wikipedia.org/wiki/Binary_heap,
иитмо https://neerc.ifmo.ru/, визуализация https://www.cs.usfca.edu/~galles/visualization/Heap.html)

9) Биномиальная куча
10) Фибоначчиевая куча
11) Префиксное дерево (cтатья на английском полнее https://en.wikipedia.org/wiki/Trie)

12) Сжатое префиксное дерево (cтатья на английском полнее https://en.wikipedia.org/wiki/Radix_tree)
13) Hash table
14) Фильтр Блума 

(!)Устройство бинарных деревьев поиска:
- вики:

1) Двоичное дерево поиска

2) B-дерево

- обзорные статьи:

1) https://tproger.ru/translations/binary-search-tree-for-beginners/
2) Бинарные деревья поиска и рекурсия – это просто https://habr.com/ru/post/267855/

3) Структуры данных: бинарные деревья. Часть 1 https://habr.com/ru/post/65617/

- реализация:

1) Дерево поиска, наивная реализация

2) Основы B-деревьев (внутреннее устройство БД) 

http://onreader.mdl.ru/DatabaseInternals/content/Ch02.html

3) Лекции 13-14: деревья поиска, почти сбалансированные деревья.

Красно-черные деревья и реализация множества на их основе http://mech.math.msu.su/~vvb/2course/Borisenko/lecTree.html

Префиксное дерево:
1) Префиксное дерево (cтатья на английском полнее https://en.wikipedia.org/wiki/Trie)
2) Сжатое префиксное дерево (cтатья на английском полнее https://en.wikipedia.org/wiki/Radix_tree)
3) Чем хороши префиксные деревья? https://otus.ru/nest/post/676/
4) Trie, или нагруженное дерево https://habr.com/ru/post/111874/
5) Сжатые префиксные деревья https://habr.com/ru/post/151421/
6) K-d дерево
7) Анатомия KD-Деревьев https://habr.com/ru/post/312882/
8) К-d деревья и перечисление точек в произвольном прямоугольнике (статика)
9) http://www.ray-tracing.ru/articles181.html
10) KD-деревья и R-деревья https://fat-crocodile.livejournal.com/156564.html

Реализация динамического массива на си c автоматическим расширением размера выделенной памяти в случае необходимости:
1) Аналог std::vector из C++11 на чистом C89 и как я его писал https://habr.com/ru/post/324210/
2) https://prog-cpp.ru/c-alloc/

Реализации односвязного списка на си:
1) https://prog-cpp.ru/data-ols/
2) http://acm.mipt.ru/twiki/bin/view/Cintro/SimpleList

Реализация очереди с приоритетами на базе двоичной кучи, реализованной через статический массив:
1) Двоичная куча (английская полнее https://en.wikipedia.org/wiki/Binary_heap,
иитмо https://neerc.ifmo.ru/)
2) https://ru.stackoverflow.com/
3) https://www.geeksforgeeks.org/building-heap-from-array/

Источники:
1) Qt Container Classes (wiki) https://doc.qt.io/qt-5/containers.html
2) Библиотека стандартных шаблонов (STL) (вики)
3) http://stepanovpapers.com/STL/DOC.PDF
4) Степанов, Ли - Руководство по стандартной библиотеке шаблонов (STL)
https://rsdn.org/article/cpp/stl.xml (немного косячный перевод)
5) http://www.martinbroadhurst.com/stl/

Реализация связного списка на C++ с шаблонами (аналога std::list):
1) Односвязный список на C++ http://itnotesblog.ru/note.php?id=178
2) STL для новичков. Реализация класса-контейнера https://habr.com/ru/post/187010/

Очередь с приоритетами на C++ с шаблонами:
1) адаптер std::priority_queue https://en.cppreference.com/w/cpp/container/priority_queue
2) https://www.bestprog.net/ru/2019/09/29/c-an-example-implementation-of-a-priority-queue-for-a-template-class-implementation-as-a-dynamic-array-ru/
3) https://ru.wikibooks.org

Алгоритмы сортировки:

1) Пузырьковая сортировка и все-все-все https://habr.com/ru/articles/204600/

Книги по STL:
1) Леен Аммерааль - STL для программистов на C++ https://vk.com/wall-18822808_8289

2) Скотт Мэйерс - Эффективный STL https://yadi.sk/i/miCReUNP3j7ECQ
3) Бьярн Страуструп - Язык программирования C++ https://yadi.sk/i/OaOuAQWWeEm9GQ
4) Джосьютис - Стандартная библиотека C++ https://yadi.sk/i/frVPf5aREhHqQA

Книги по алгоритмам:
1) Кормен, Лейзертон, Риверст, Штайн - Алгоритмы
2) Кнут Д. - Тома 1, 2, 3
3) Вирт Н. - Алгоритмы (pascal, modula-2)

Примеры реализаций алгоритмов на c, c++:
1) Язык Си в примерах (викиучебник)
2) Реализация алгоритмов (викиучебник)
3) http://acm.mipt.ru/twiki/bin/view/Algorithms/WebHome
4) http://algolist.manual.ru/
5) https://habr.com/ru/post/146793/

Вопросы:

1) типы указателей в c++11 (unique_ptr, shared_ptr, weak_ptr):

- Без new: Указатели будут удалены из C++ https://habr.com/ru/post/352570/

- Smart pointers для начинающих https://habr.com/ru/post/140222/

- weak_ptr:

-- https://docs.microsoft.com/ru-ru/cpp/cpp/how-to-create-and-use-weak-ptr-instances

-- https://en.cppreference.com/w/cpp/memory/weak_ptr

-- https://ravesli.com/urok-195-std-weak_ptr-tsiklicheskaya-zavisimost-s-std-shared_ptr/

2) какая алгоритмическая сложность у map, у unordered_map: 

- map (C++)

- Потокобезопасный std::map с производительностью lock-free map https://habr.com/ru/post/328374/

3) чему равна высота сбалансированного дерева поиска в 1000000 элементов?

4) в чем проявляется сбалансированность дерева поиска?

5) какие структуры данных дают поиск за логарифмическое время? (map)

6) зачем нужен map, если unordered_map всегда выдает более быстрый результат?

7) какие структуры данных выдают результат за линейное время? (vector)

Вопросы с собеседований:

1) Популярные вопросы на собеседовании по C++ и ответы на них https://habr.com/ru/post/117996/

2) Дебри графики или как пройти собеседование на программиста компьютерной графики в GameDev https://habr.com/ru/post/561372/

Теория:

1) https://informatics.mccme.ru/

2) http://codeforces.com/

3) https://e-maxx.ru/algo/

ШАД:

1) Прием https://yandexdataschool.ru/enroll

2) Решения вступительных испытаний в ШАД https://efiminem.github.io/supershad/

3) Полный разбор экзамена ШАД-2019 https://habr.com/ru/post/487680/

4) Поступление в ШАД глазами куратора и студента https://academy.yandex.ru/posts/postuplenie-v-shad-glazami-kuratora-i-studenta

5) Ритуал поступления https://academy.yandex.ru/posts/beri-i-delay-sovety-blogera-kotoryy-smog-postupit-v-shad

6) День открытых дверей ШАД 2021

7) Разбор задач для поступления в ШАД https://yandexdataschool.ru/stepbystep

8) https://yandexdataschool.ru/static/files/shad_program.pdf

yandex:

1) https://contest.yandex.ru/contest/8458/enter/

2) Как проходят алгоритмические секции на собеседованиях в Яндекс https://habr.com/ru/company/yandex/blog/449890/

3) https://yandex.ru/jobs/pages/ya-interview

4) https://yandex.ru/recruitment-guide/backend-developers

5) https://yandex.ru/recruitment-guide/analysts

6) https://yandex.ru/recruitment-guide/devops

спортивное программирование:

1) Спортивное программирование — социальный лифт в IT. Как его использовать школьнику, родителям школьника и разработчику? https://habr.com/ru/company/it_people/blog/583280/

2) Спортивное программирование https://astanahub.com/blog/sportivnoe-programmirovanie1617782868?locale=ru

3) Олимпиадное программирование https://tproger.ru/tag/competitive-programming/

4) https://tproger.ru/articles/tips-for-sport-programming/

5) https://inde.io/article/28106-yasno-ponyatno-kto-takoy-sportivnyy-programmist-i-kak-im-stat

6) Спортивное программирование https://stepik.org/course/53634/promo

7) Быстрый старт в спортивное программирование (МФТИ)

8) Про олимпиадное программирование

9) Олимпиады по программированию/

10) ACM

11) https://ru.wikipedia.org/wiki/Topcoder

12) https://en.wikipedia.org/wiki/Codeforces

13) https://ru.wikipedia.org/wiki/Google_Code_Jam

14) https://ru.wikipedia.org/wiki/Facebook_Hacker_Cup

15) https://ru.wikipedia.org/wiki/Russian_Code_Cup

16) Математическая модель

17) A+B

Собеседование в it:

1) Как пройти собеседование в IT-компанию https://vc.ru/hr/263806-kak-proyti-sobesedovanie-v-it-kompaniyu

2) Подготовка к собеседованиям в IT-гиганты: как я преодолела проклятье алгоритмического собеседования https://habr.com/ru/post/499394/

3) Как я оклад 2х хотел https://habr.com/ru/post/657619/

4) Моя история прохождения интервью в IB IT (Java разработчик, investment bank) в Лондоне с примерами типичных заданий https://habr.com/ru/articles/430788/

leetcode:

1) easy https://leetcode.com/problemset/all/?difficulty=EASY&page=1

2) Есть ли польза от решения алгоритмических задач на LeetCode? https://habr.com/ru/articles/709550/

3) Нужно читать академические статьи в Computer Science https://habr.com/ru/companies/skillfactory/articles/710822/

Реализация упорядоченного множества на c и c++:

1) Упорядоченное множество

2) Дерево поиска, наивная реализация

3) Алгоритмы и структуры данных для начинающих: двоичное дерево поиска https://tproger.ru/translations/binary-search-tree-for-beginners/

4) Структуры данных: бинарные деревья https://habr.com/ru/articles/65617/