Cracking The Coding Interview Together – Problem 9.4: Duplicate URLs

Welcome back to "The Dev Learnings". Imagine walking into a system design interview, and the interviewer drops a massive dataset on your lap: 10 billion URLs. Your task is to detect the duplicate documents, where duplication means the URLs are precisely, byte-for-byte identical. At first glance, it sounds simple. Just throw it into a database with a unique constraint, right? But as you start calculating the memory footprint, reality sets in. Ten billion strings will overwhelm a single machine's RAM and disk I/O in seconds. Today, we are going to explore how senior engineers scale data processing pipelines to tackle problems that break traditional memory boundaries. By the end of this article, you will know how to design a fault-tolerant, scalable solution using both single-machine heuristics and distributed systems patterns.

Problem Statement

We are given a massive file or stream containing approximately 10 billion URLs. Our operational goal is to identify and output all duplicate URLs (or a list of unique URLs depending on the downstream consumer) efficiently. We must respect strict hardware constraints—specifically, dealing with a scale that far exceeds standard RAM limits.

Analyze the Problem Together

Let's break down the math and constraints. Suppose each URL averages 60 bytes. Ten billion URLs require roughly 600 gigabytes of raw storage. Even if we had a machine with 128GB of RAM, we cannot load this dataset into memory naively. A naive approach using a standard hash set in-memory will immediately trigger an OutOfMemoryError. If we use a relational database with a disk-backed index, the random I/O bottlenecks during insertions for 10 billion items will bring our processing time to days, if not weeks.

The "Aha!" conflict here is balancing space complexity against time complexity. How do we reduce the memory footprint while maintaining high accuracy? We have two primary architectural directions: approximation using probabilistic data structures (if false positives are acceptable) or exact counting using external sorting, hashing, and MapReduce paradigms.

Questions for the Interviewer

Before jumping into code, a senior engineer always clarifies the ambiguity of scale and business requirements:

• "Do we need 100% exact deduplication, or is a probabilistic approach with a bounded false-positive rate acceptable?"
• "Is this a one-time batch processing job, or a real-time streaming pipeline where URLs arrive continuously?"
• "What is our infrastructure budget? Can we distribute this across a cluster of machines, or are we constrained to a single beefy server with limited disk space?"
• "What is the average length and character encoding of the URLs?"

Think About the Solution

For an exact deduplication pipeline at this scale, we turn to the Divide-and-Conquer / External Sorting pattern, commonly implemented via MapReduce. The high-level architecture looks like this:

1. Partitioning: We stream the 10 billion URLs through a hash function (e.g., MurmurHash or SHA-256) and route them to $N$ distinct files or worker nodes based on hash(url) % N. This ensures identical URLs always land in the same partition.
2. Local Processing: Each partition (now small enough to fit comfortably on disk or into a worker's memory) is loaded, sorted, or processed using a local hash set to find duplicates.
3. Aggregation: We combine the results or stream them out to our sink.

Write Code and Explain

Below is a production-ready Java implementation demonstrating how we can simulate external file partitioning and chunk-based processing for massive datasets. While we cannot process 10 billion records locally in a snippet, this code illustrates the exact streaming partition logic you would scale out in a distributed environment.

import java.io.*;
import java.util.*;

public class URLDeduplicator {

    // Simulates partitioning a massive file into N smaller chunk files
    public static void partitionFile(String inputFilePath, int numPartitions, String outputDir) throws IOException {
        BufferedReader reader = new BufferedReader(new FileReader(inputFilePath));
        BufferedWriter[] writers = new BufferedWriter[numPartitions];
        
        File dir = new File(outputDir);
        if (!dir.exists()) dir.mkdirs();

        for (int i = 0; i < numPartitions; i++) {
            writers[i] = new BufferedWriter(new FileWriter(outputDir + "/partition_" + i + ".txt"));
        }

        String url;
        while ((url = reader.readLine()) != null) {
            int partitionIndex = Math.abs(url.hashCode()) % numPartitions;
            writers[partitionIndex].write(url);
            writers[partitionIndex].newLine();
        }

        reader.close();
        for (int i = 0; i < numPartitions; i++) {
            writers[i].close();
        }
    }

    // Processes a single partition to find duplicates using a local HashSet
    public static Set<String> findDuplicatesInPartition(String partitionFilePath) throws IOException {
        Set<String> seen = new HashSet<>();
        Set<String> duplicates = new HashSet<>();
        
        BufferedReader reader = new BufferedReader(new FileReader(partitionFilePath));
        String url;
        while ((url = reader.readLine()) != null) {
            if (!seen.add(url)) {
                duplicates.add(url);
            }
        }
        reader.close();
        return duplicates;
    }
}

Step-by-Step Walkthrough:

• partitionFile reads the input stream line by line, maintaining a low memory footprint ($O(1)$ memory relative to the total file size). It uses modulo hashing to distribute identical URLs into the exact same bucket.
• findDuplicatesInPartition processes each manageable chunk independently, leveraging standard hash sets safely within the memory limits of a single worker thread.

Time & Space Complexity

• Time Complexity: $O(N)$, where $N$ is the total number of URLs. Reading the file, hashing, and writing to partitions takes linear time. Sorting or checking duplicates within partitions also operates linearly relative to partition size.
• Space Complexity: $O(M)$ on a per-partition basis, where $M$ is the maximum number of URLs in a single partition. By increasing our number of partitions ($N$), we can arbitrarily shrink $M$ to fit within available RAM.

Why This Problem Matters (The Senior Perspective)

This problem is a foundational archetype for big data engineering. It bridges the gap between basic data structures and distributed computing frameworks like Apache Hadoop MapReduce or Apache Spark. In production environments, mastering stream partitioning prevents memory bottlenecks, network saturation, and cascading failures in distributed clusters. Whether you are building a web crawler, a log ingestion pipeline, or an analytics engine, the ability to safely chunk and process billions of records is a non-negotiable skill.

Final Thoughts

Solving big data problems isn't about having infinite hardware; it's about applying clever algorithmic constraints to manage resources effectively. Take some time to think about how you would implement this using a Bloom Filter if the requirement shifted to checking membership with a 1% false-positive tolerance. Happy coding, and see you in the next breakdown!