Hardware interview practice
Build an insertion-ordered O(1) set
Implement a set that preserves insertion order while supporting average O(1) insert, remove, and contains. Iteration must return surviving elements in their original insertion order.
Reviewed example
Work through one case
Input
insert(A), insert(B), insert(C), remove(B), insert(B)Expected output
iteration order = [A, C, B]Removing B unlinks its original node, and reinserting it creates a new most-recent insertion at the tail.
What to cover
Requirements
- Use a hash map for membership and direct node lookup.
- Use a doubly linked list so removing a middle element does not reorder the survivors.
- Ignore duplicate insertion and define reinsertion after removal as a new insertion at the end.
- Keep the map keys and list nodes in one-to-one correspondence.