1,000+ ASIC Interview Questions: SystemVerilog, UVM & RTL

DescriptionQ691

Page ↗

Q691FWASIC interview problem

Build an insertion-ordered O(1) set

TechniquesPythonHash mapDoubly linked listOrdered set

DifficultyHard

TopicData Structures

LanguagePython

Requirements4 checkpoints

Problem

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.

Example input and output

Use this case to check your interpretation

Input

insert(A), insert(B), insert(C), remove(B), insert(B)

Output

iteration order = [A, C, B]

Explanation

Removing B unlinks its original node, and reinserting it creates a new most-recent insertion at the tail.

Requirements (4)

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.