Очень долгое время я не мог понять: когда я буду писать алгоритмы и структуры в продакшн коде также, как я это делал на олимпиаде? Время шло, а ничего сложнее бинарного поиска и расстояния Левенштейна не нужно было (все работало и так быстро, а структуры и алгоритмы были бы в ущерб модулярности).

Конечно, очень часто нам не нужно думать об эффективных алгоритмах, когда всю тяжелую работу выполняют база данных, веб-сервер и операционная система. А твой код лишь рисует веб-странички или кнопочки в приложении на айфон.

Но именно в этих сложных системах (ОС, базы данных, веб-сервер, компиляторы, др) и используются все те основы, что мы с вами читаем с книжек типа CLRS.

Полный ответ об алгоритмах из книжек был дан на stackexchange и потом был репостнут в блогах и позже на HN. Сегодня я решил перевести ответ об ОС Линукс со своими комментариями (отсебятина) и ссылками на ресурсы на русском языке.

Так давайте поговорим об ОС Линукс, оказывается там можно встретить все, что учит любой школьник до 9 класса (а может и раньше):

• Связанные списки, двусвязаные списки и lock-free версии
• B+ сбалансированное дерево, как мы помним они еще используются в файловой системе
• Двусвязаные списки отсортированные по приоритетам (их используют mutex локи)
• Красно-черные сбалансированные деревья используются очень много где
• Дерево интервалов (НЕ дерево отрезков как в e-maxx, а дерево интервалов, где в каждой вершине сбалансированного бинарного дерева лежит два числа: от и до)
• Radix tree (более знакомый нам как Бор)
• Куча с приоритетами используется в cgroups: ограничение ресурсов доступных процессу. Модная нынче контейнеризация (LXC использует cgroups, а модный Docker использует LXC), также не удивлюсь, если линуксовская версия runexe использует cgroups.
• Хэширование по Кнуту: раз и два
• Хэш-таблицы используются для inodes — структура хранящая мета-даныне о файлах на файловой системе
• Битовые массивы (прям как Си++шный bitarray)
• Бинарный поиск, бинарный поиск в B-дереве
• Поиск в глубину и ширину
• КМП и Бойер-Мур
• Сортировка слиянием иcпользуется для системы сборки мусора

Также советуется к прочтению оригинальный пост, там еще больше примеров с ссылками на статьи на английском языке.

И в добавку примеры использования динамического программирования: link