Coding & DSA: the practice test

The one-pass idiom: for each element, ask 'have I already seen my complement?' via a hash map of value to index, then insert the current value. Checking before inserting elegantly handles duplicates and forbids using the same element twice. The sorted-list variant costs O(n log n) and loses original indices; prefix sums answer subarray questions, not pair questions. Interviewers use this warm-up to check the reflex that powers half of array problems: trade memory for a lookup so the inner loop disappears.

Each structure covers the other's weakness. A hash map finds a key instantly but has no notion of order, so it cannot say who is least-recent. A doubly linked list maintains recency order and can unlink any node or drop the tail in O(1), but finding a node by key means walking it. Map-of-key-to-node plus list-of-nodes gives both: get looks up the node and moves it to the head; put inserts at head and evicts the tail on overflow. 'Doubly' matters: removal from the middle needs the previous pointer without a scan. This composite is the canonical example of combining structures to meet dual O(1) requirements.