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

Question

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

Я получил свой первый вопрос об интервью и получил отказ, потому чтомоей реализации.

Вопрос:

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

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

1. Вставка (int x).Вставьте запись для значения «х».

2. Стереть (int x).Удалите одну запись со значением «x» (если она существует) из коллекции.

3. Стереть (int от, int до).Удалите все записи со значением в диапазоне [от, до).

4. Количество (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).

Answer 1

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

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

, поэтому у вас есть следующий узел:

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

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

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

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

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

Answer 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;.Хотя учебники делают для ясности, профессиональные программисты этого не делают.

Answer 3

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

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

Вставка и стирание отдельных элементов просто увеличивает и уменьшает (возможно, удаляет в последнем случае) значения для данного ключа (оба 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).