Katkat
Back

Deduplicate a File Exactly When Distinct Lines Exceed Memory

VantaSoftware Engineer · Onsite
MediumSoftware EngineerOnsiteSoftware Engineering Fundamentals

Last updated

Design exact external-memory global line deduplication with sorting or partitioning, full equality checks, and optional first-occurrence order preservation.

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?

Hints

Hint 1

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.

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?