Telegram-канал cpluspluc - C++ Academy: Unsorted - каталог телеграмм

C++ Academy

27 Apr 2025 13:04

🖥 Задача для собеседования: "Быстрая очередь с удалением элемента за O(1)"

🔖 Условие:

Реализуйте структуру данных — очередь (`queue`), поддерживающую три операции:

- enqueue(x) — добавить элемент в конец очереди (должно работать за O(1));
- dequeue() — удалить элемент из начала очереди и вернуть его (должно работать за O(1));
- remove(x) — удалить первое вхождение элемента x из очереди за O(1).

Ограничения:
- Элементы могут повторяться.
- Если элемент отсутствует, remove(x) не делает ничего.
- Операции должны оставаться эффективными на больших объемах данных (миллионы элементов).
- Можно использовать стандартные структуры данных STL (`list`, unordered_map, unordered_set и т.д.).

▪️ Дополнительные вопросы к кандидату:

- Как обеспечить O(1) удаление произвольного элемента из очереди?
- Как избежать утечек памяти или "битых" итераторов после удаления элементов?
- Что будет, если очередь будет содержать множество одинаковых элементов?
- Как бы вы изменили решение, если бы нужно было удалять все вхождения элемента, а не только первое?

---

▪️ Разбор возможного решения:

Основная архитектура:

- Используем std::list<int> data для хранения реальной очереди.
- Почему list? Потому что позволяет за O(1) удалять элементы по итератору.
- Используем std::unordered_map<int, std::list<std::list<int>::iterator>> index.
- Для каждого значения храним список итераторов на его вхождения в data.

Операции:

- enqueue(x):
- Добавляем x в конец data.
- Сохраняем итератор на него в index[x].
- Все действия — за O(1).

- dequeue():
- Удаляем элемент из начала data.
- Находим соответствующий итератор в index, удаляем его.
- Если в списке итераторов для этого значения больше нет элементов, удаляем ключ из index.

- remove(x):
- Если в index[x] есть итераторы:
- Берем первый итератор.
- Удаляем его из data и из списка итераторов.
- Если список стал пустым — удаляем запись x из index.
- Все действия — за O(1).

---

▪️ Возможные подводные камни:

- ❗ Не проверять, пустой ли index[x], перед удалением итератора.
- ❗ Не удалять ключи из unordered_map, что приводит к накоплению "пустых" списков в памяти.
- ❗ Использовать vector вместо list — тогда удаление из середины будет занимать O(n).

---

▪️ Мини-пример интерфейса класса:


#include <list>
#include <unordered_map>

class FastQueue {
private:
    std::list<int> data;
    std::unordered_map<int, std::list<std::list<int>::iterator>> index;

public:
    void enqueue(int x) {
        auto it = data.insert(data.end(), x);
        index[x].push_back(it);
    }

    int dequeue() {
        if (data.empty()) throw std::out_of_range("Queue is empty");
        int val = data.front();
        auto it = index[val].front();
        index[val].pop_front();
        if (index[val].empty()) {
            index.erase(val);
        }
        data.pop_front();
        return val;
    }

    void remove(int x) {
        if (index.count(x) == 0) return;
        auto it = index[x].front();
        data.erase(it);
        index[x].pop_front();
        if (index[x].empty()) {
            index.erase(x);
        }
    }
};

▪️ Дополнительные вопросы на усложнение:

- Что если нужно сделать removeAll(x) — удаление всех вхождений элемента?
- Как изменится решение, если в очереди будут сложные объекты вместо int?
- Как минимизировать использование памяти, если очередь очень большая?
- Как обеспечить безопасность потоков (thread-safety) для многопоточного варианта очереди?

@cpluspluc