Так уж случилось, что у меня нет IT-образования и все фундаментальные знания по алгоритмам и структурам данных получены мною самостоятельно.
Ну и естественно, как и многие самоучки, я всегда больше налегал на практическое использование полученных знаний.
На собеседовании в одной крупной компании, мне очень чётко указали на пробелы в моих знаниях. Да и собеседование такого уровня, я проходил впервые, что и было очень полезным опытом.
Само собеседование состояло из большого количества этапов:
Этап 1. Первичное собеседование с кандидатом. Обычный телефонный разговор с сотрудником отдела HR. Немного типовых технических вопросов, чтобы отсеять особо неадекватных кандидатов.
Этап 2. Скайп собеседование с техническим специалистом. Длительность около часа, в течении которого мы поговорили про паттерны и ООП в общих чертах. Затем порешали простые алгоритмические задачи в онлайн-редакторе и там же писали немного простых SQL запросов.
Этап 3. Очная ставка. Т.к. офисы всех крупных компаний у нас в основном в мегаполисах, один из них и пришлось посетить лично. Компания крупная, поэтому авиаперелёт и проживание были оплачены и от меня из трат были только билеты на автобус и метро.
И вот именно этот этап был самым сложным и интересным - пятичасовое собеседование, четыре часа из которых - это технические беседы по алгоритмам, архитектуре, БД, решение алгоритмических задач на маркерной доске, написание запросов там же. Вообщем маркерной доски было много ;-) Ну и час общих бесед с HR, что я также воспринял как собеседование.
Как результат - на работу меня не взяли: не хватает скорости решения задач и были баги.
Вообщем подвела меня именно секция алгоритмов.
Пробелы обозначены - будем их ликвидировать.
Попробую, начиная с этого поста, читать больше теории и рассказывать о полученных знаниях простыми словами. Ну если получится конечно.
И начну с любопытной информации, полученной именно на том большом собеседовании: упорядочивание по накопительному индексу.
Ну и вкратце про то, как он работает.
К примеру, мы начинаем работу с последовательностью, которая состоит из натуральных чисел (числа от 1 до бесконечности, целые, неотрицательные).
Данные поступают к нам из источника последовательно и мы хотим получать их последовательно, в том же порядке, в котором и получаем. Индекс массива для первого поступившего числа - 0, для второго - индекс первого+значение первого числа, для третьего - индекс второго+значение второго числа.
Пример, для закрепления:
Входные числа - 3 1 7 5 N
Представление в виде массива
[
0 => 3
3 => 1
4 => 7
11 => 5
16 => N
]

Результат:
Мы храним числа, именно в том порядке в каком их получили.
Массив является упорядоченным.
Доступ к любому элементу массива может быть обеспечен со сложностью N
Где это может пригодиться? Теоретически, так мы можем отлично справится с задачей вывода случайного элемента массива с учётом его веса, со сложностью алгоритма не превышающей O(log(N)) и со сложность вставки O(1).
Ну это теоретически, а как это применять практически?

Тут заканчивается теория и начинается практика. Пример использования в практике:

Мы разрабатываем свою баннерокрутилку на сайт и перед нами стоит задача, показывать какие то баннеры чаще чем другие. Самое быстрое и простое решение в данном случае - использование системы весов. И вот тут наш алгоритм и пригождается. Я буду упрощать пример, просто, чтобы донести смысл:
Мы получаем из внешней системы хранения (к примеру БД) неупорядоченный набор баннеров с весом каждого и складываем в массив M используя накопительный индекс.
Индекс последнего элемента + его вес в нашей баннерной системе - это суммарный вес всех баннеров в системе - S.
Получив случайное число R в диапазоне 0…(S-1), мы, радуясь что массив у нас упорядочен, проходим методом половинного деления по нашему массиву, пока не найдем нужный нам элемент, соответствующий условию:
R>=(Индекс текущего элемента) и R<(Индекс текущего элемента+вес текущего элемента)
В случае с реляционной базой данных, в случае, если мы также используем при хранении накопительный индекс, мы получив случайно число, в диапазоне 0…(S-1) также можем получить нужный нам баннер запросом:
select `banner_image` from `banners` where `banner_index`>=R and R<(`banner_index`+`banner_weight`)
Видимый недостаток для данного вида хранения в БД - сложность изменения веса элементов. При удалении/изменении веса любого из баннеров - нам нужно пересчитать накопительный индекс для всех последующих элементов.

Фух, высказался. Вывода не будет.