tgoop.com/cpluspluc/1047
Last Update:
Реализуйте структуру данных — очередь (`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