Какова лучшая структура данных C++, которую можно использовать для хранения и управления коллекцией целых чисел?

это мой первый вопрос StackOverflow, поэтому, пожалуйста, дайте мне знать, если я не выполнил рекомендации сообщества по этому вопросу и должен ли я удалить его.

Я получил свой первый вопрос на собеседовании, и меня отвергли из-за моей реализации.

Вопрос в том:

Разработайте и реализуйте класс C++, который хранит коллекцию целых чисел. На стройке коллекция должна быть пустой. Один и тот же номер может храниться более одного раза.

Реализуйте следующие методы:

Вставьте (int x). Вставьте запись для значения "х".
Стереть (int x). Удалите одну запись со значением "x" (если она существует) из коллекции.
Стереть (int от, int до). Удалите все записи со значением в диапазоне [от, до).
Считать (int от, int до). Посчитайте, сколько записей имеют значение в диапазоне [от, до).

Я подумал, что хорошей реализацией будет использование связанных списков, так как он использует несмежную память, и удаление записей не потребует перетасовки большого количества данных (как в векторах или массивах). Тем не менее, я получил отзыв от компании, в котором говорилось, что моя реализация была O (n ^ 2) временной сложности и была очень неэффективной, поэтому я был отклонен. Я не хочу повторять ту же ошибку, если подобный вопрос появляется в другом интервью, поэтому я хотел бы знать, как лучше всего подойти к этому вопросу (друг предложил использовать карты, но он также не уверен).

Мой код:

void IntegerCollector::insert(int x)
{
    entries.push_back(x);
}

void IntegerCollector::erase(int x)
{
    list<int>::iterator position = find(entries.begin(), entries.end(), x);
    if (position != entries.end())
        entries.erase(position);
}

void IntegerCollector::erase(int from, int to)
{
    list<int>::iterator position = entries.begin();

    while (position != entries.end())
    {
        if (*position >= from && *position <= to)
            position = entries.erase(position);
        else
            position++;
    }
}

int IntegerCollector::count(int from, int to)
{
    list<int>::iterator position = entries.begin();
    int count = 0;

    while (position != entries.end())
    {
        if (*position >= from && *position <= to)
            count++;

        position++;
    }

    return count;
}

В отзывах говорилось, что они будут нанимать только кандидатов, способных реализовать решения со сложностью O (nlogn).

Ответ 1

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

Затем вы можете просто использовать std::map<int, size_t> качестве вспомогательной структуры, которая отображает каждое целое число (ключ) на количество раз, которое оно существует в вашей структуре данных (value = количество).

Вставка и стирание отдельных элементов - это просто увеличение и уменьшение (возможно, удаление в последнем случае) значений для данного ключа (оба O(log(distinct_values_in_container)) для поиска ключа).

Поскольку std::map упорядочен, вы можете использовать lower_bound и upper_bound для бинарного поиска, поэтому поиск ключей в [from, to) очень эффективен (поиск диапазона также O(log(distinct_values_in_container))). Стирать их или суммировать их счетчики легко (здесь время выполнения более сложное).

Если вы хотите получить дополнительный кредит, он заплатит, чтобы понять ограничения асимптотического времени выполнения. Рассмотрим эти моменты:

Что эти асимптотические среды выполнения означают на практике, во многом зависит от модели использования. Если дубликаты никогда не вставляются, мы находимся на O(n), но вы также можете получить произвольно хорошие времена (с точки зрения n= количество вставок), если есть много идентичных элементов (например, если у каждого ключа есть O(exp(n)) затем O(distinct_values_in_container) = O(log(n))). В крайнем случае, когда все задействованные целые числа одинаковы, все операции являются O(1).

Как собеседник, я бы также поговорил о том, значат ли эти асимптотические среды выполнения на практике. Может случиться так, что древовидная структура карты (которая является токсичной для кеша и предиктора ветвлений) проигрывает простому std::vector<std::pair<int, size_t>> (если стирание всегда массово) или даже std::vector<size_t> (если ключи "плотные") для данного приложения.

Я думаю, что ваша основная ошибка (и почему вы были отклонены) заключается в том, что вы не понимаете, что нет необходимости хранить каждое вставленное целое число отдельно. Вы, к сожалению, также, кажется, упустили возможность сохранить список отсортированным, но я не вижу, откуда O(n^2).

Ответ 2

Если бы вас нанимали на роль, которая не требовала какого-либо предыдущего опыта программирования, я бы не отказался от вас только на этом примере кода.

Использование std::list было интересным выбором и показало, что вы думали об этом. Тот факт, что вы использовали стандартный библиотечный контейнер C++ вместо того, чтобы пытаться построить его с более низкого уровня, для меня является признаком да-найма. При вашем подходе (1) быстро, но (2), (3) и (4) будет медленно. При отсутствии какой-либо другой информации вы должны упорядочить вещи так, чтобы чтение (включая запросы) данных выполнялось быстрее, чем запись. Ваш подход имеет это наоборот. Хотя иногда это то, что вам нужно - например, когда вы проводите измерения в реальном времени, вы хотите, чтобы этап сброса данных был максимально быстрым за счет чего-либо еще. Для этого приложения ваше решение будет трудно победить!

Бронирование, но ни в коем случае не красные линии:

Целое число не означает int. Если у вас не будет возможности прояснить ситуацию, постройте свой класс на

template<typename Y> std::map<Y, std::size_t>

где Y является целочисленным типом. Обратите внимание на использование std::size_t для счетчика. Он считает количество раз, когда конкретный Y присутствует.

Включите некоторые комментарии программы в следующий раз.

Не используйте using namespace std; , Хотя учебники делают для ясности, профессиональные программисты этого не делают.

Ответ 3

Вы должны использовать map<int,size_t> int для значения, size_t для count.

Если вам нужно реализовать код, вы должны выбрать сбалансированное двоичное дерево, чтобы получить сложность 'log N'.

Итак, у вас есть следующий узел:

struct Node
{
  int key;
  size_t count;
  Node *left, *right; 
  size_t leftNodesCount, rightNodesCount;
};

leftNodesCount и rightNodesCount должны указывать, насколько хорош баланс, поэтому любая вставка и удаление изменяет его вплоть до корня. сбалансированное дерево - это когда все дерево leftNodesCount и rightNodesCount практически равны (средняя разница не более 1, но вы можете установить допуск на более высокое значение, например 2 или 3)

Теперь вы должны реализовать методы Insert, Delete и Balance.

Чтобы сбалансировать сбалансированное дерево, вы должны повернуть несбалансированные узлы. Повернуть влево означает заменить узел на узел справа и добавить узел влево. Повернуть вправо - это та же операция в другом направлении.

Соучастие баланса также "log N". обратите внимание, что после вставок и удалений вы должны обращаться к балансу таким образом, чтобы сохранить соучастие дерева в "log N"