# Design a Linked Queue with Deletion Follow-Ups Design a queue with `O(1)` enqueue and dequeue using a hand-built linked structure rather than a native queue or collection. Then discuss how to extend it with `delete(x)` and `removeAllDuplicates()`, identifying the observable semantics that must be clarified before either follow-up is implemented. ### Constraints & Assumptions - The base queue owns head and tail pointers and may be empty. - Enqueue and dequeue must remain `O(1)`. - The source does not say whether `delete(x)` removes one or all matches, or whether duplicate removal keeps one copy or removes every repeated value. ### Clarifying Questions to Ask - What should dequeue return or do when the queue is empty? - Should `delete(x)` remove the first match, the last match, or every match? - Does `removeAllDuplicates()` retain one occurrence of each value or remove values that appear more than once entirely? ```hint Protect the tail invariant Any traversal that unlinks nodes must update both head and tail when it removes the first or last node. ``` ### What a Strong Answer Covers - Node, head, and tail invariants for constant-time base operations. - Separate algorithms for the plausible deletion and duplicate-removal contracts. - Empty, singleton, repeated-value, head, tail, and all-removed cases. - Complexity with and without an auxiliary membership or frequency structure. ### Follow-up Questions 1. How would the design change if native hash-based collections became available? 2. Can arbitrary delete-by-value remain worst-case `O(1)` without maintaining additional indexes?