Deduplicate a File Exactly When Distinct Lines Exceed Memory

Design an exact command-line global-uniqueness tool for a file whose distinct lines do not fit in an in-memory hash table. Explain how you would use external storage and how the output-order requirement changes the design. ### Constraints Treat complete line equality as the duplicate criterion. Clarify whether the output must preserve first-occurrence order or may be sorted. The available memory, temporary storage, maximum line size, and restart requirements are unspecified. Do not substitute a probabilistic duplicate filter for exact output without permission. ### Clarifying Questions - Must the first occurrence appear in its original position relative to other retained lines? - Is external sorting available, and how much temporary disk space is allowed? - Can an individual line exceed memory, and what failure or restart guarantees are required? ```hint Retain original positions when order matters An external sort can group equal lines, but a second ordering step may be needed to restore first-occurrence order. ``` ### What a Strong Answer Covers - An exact external-memory deduplication plan. - Collision handling, duplicate equality, disk and memory costs, and output ordering. - Failure behavior and the limits of probabilistic structures. ### Follow-up Questions - What if one hash partition is still too large for memory? - Why can a Bloom filter alone incorrectly discard a unique line?