← 返回 databricks 的题目列表Snapshot Set Iterator
类型：online_judge
Problem: Snapshot Set Iterator
Design a SnapshotSet that supports snapshot iterators.
The set should support the following operations:
add(x): add element x to the set. If x already exists, the state does not change.
remove(x): remove element x from the set. If x does not exist, the state does not change.
contains(x): return whether x is currently in the set.
iterator(): create an iterator. The iterator must traverse the elements that existed at the moment it was created. Any add/remove operations after the iterator is created must not affect its traversal result.
The iterator should support:
has_next(): whether there is another element.
next(): return the next element; if no element remains, return END.
For judging purposes:
Elements are strings without spaces.
Iteration order is the order in which an element first appeared in the SnapshotSet.
If an element is removed and later re-added, it keeps its original first-appearance order.
Input Format
The first line contains an integer Q, the number of operations.
Each of the next Q lines is one of:
ADD x
REMOVE x
CONTAINS x
ITER
HAS_NEXT iterator_id
NEXT iterator_id
Notes:
ITER creates a new iterator and prints its id. Ids start from 0.
HAS_NEXT id prints true or false.
NEXT id prints the next element, or END if there is none.
ADD and REMOVE produce no output.
Constraints
1 <= Q <= 2 * 10^5
The number of distinct string elements is at most 2 * 10^5.
The total length of all strings is at most 10^6.
All iterator_ids are valid.
Example
Input
10
ADD a
ADD b
ITER
ADD c
REMOVE a
NEXT 0
NEXT 0
NEXT 0
CONTAINS a
CONTAINS c
Output
0
a
b
END
false
true
Explanation
Iterator 0 is created when the set is {a, b}. Later, c is added and a is removed, but iterator 0 must still traverse only {a, b}.
Example
Input
10
ADD a
ADD b
ITER
ADD c
REMOVE a
NEXT 0
NEXT 0
NEXT 0
CONTAINS a
CONTAINS c
Output
0
a
b
END
false
true