Find Duplicate File in System — Content Hashing for Deduplication

Problem Statement#

Given a list of directory info strings in the format "root/d1/d2 f1.txt(content1) f2.txt(content2)", find all groups of duplicate files (files with the same content). A group of duplicate files includes at least two files with the same content. Return a list of groups, where each group contains the full paths of all duplicate files.

Constraints:

• 1 <= paths.length <= 2 * 10^4
• 1 <= paths[i].length <= 3000
• 1 <= sum(paths[i].length) <= 5 * 10^5
• paths[i] is a valid path.
• The file content is not empty.

Example 1:
Input:
  paths = ["root/a 1.txt(abcd) 2.txt(efgh)",
           "root/c 3.txt(abcd)",
           "root/c/d 4.txt(efgh)",
           "root 4.txt(efgh)"]
Output:
  [["root/a/2.txt","root/c/d/4.txt","root/4.txt"],
   ["root/a/1.txt","root/c/3.txt"]]

Example 2:
Input:  paths = ["root/a 1.txt(abcd)", "root/c 3.txt(efgh)"]
Output: []
Explanation: No content appears in more than one file.

Why This Problem Matters#

Find Duplicate File is a practical systems design problem in disguise. In the real world, deduplicating files by content (rather than name) is a standard technique used in distributed storage systems, backup tools, package managers, and plagiarism detectors. Google's distributed file system, for instance, uses content hashing to deduplicate identical blocks across different files.

The core pattern — use file content as a HashMap key, group file paths as values — teaches the "group by key" paradigm, which is one of the most fundamental operations in data processing. SQL's GROUP BY, Hadoop's MapReduce, and Spark's groupByKey all implement this exact abstraction at scale.

Interviewers at Google use this problem specifically because it requires string parsing as a prerequisite to the algorithmic insight. Candidates who can parse the input format cleanly and then apply the grouping pattern efficiently demonstrate both practical coding ability and conceptual understanding. Struggling with the parsing is a red flag; solving it cleanly and moving on to the grouping logic shows experience.

The follow-up questions are particularly revealing: What if file contents are too large to use as keys directly? (Use a hash of the content — content-addressable storage.) What if the directory tree is very deep and wide? (Process lazily with a generator.) These follow-ups distinguish candidates who understand the real-world motivation from those who have just memorized the algorithmic pattern.

The Core Insight#

The problem reduces to: given a list of (content, path) pairs, group paths by content and return groups with more than one path.

The algorithm:

1. For each path string, split on spaces to get [root, file1, file2, ...].
2. For each file entry (e.g., "1.txt(abcd)"), split on ( to get the filename and content separately.
3. Construct the full path: root + "/" + filename.
4. Add the full path to a content-keyed HashMap: content_map[content].append(full_path).
5. After processing all paths, return all groups with 2 or more entries.

The string parsing is the main implementation challenge. Python's split('(') and slicing off the trailing ) are the most concise tools. The algorithmic insight — use content as the key — is straightforward once the parsing is done.

An important real-world extension: if file contents can be gigabytes, you would compute a cryptographic hash (SHA-256) of the content and use that as the key. The hash is a fixed-size summary of the content that is collision-resistant in practice. This is the content-addressable storage principle used by Git, IPFS, and most modern distributed storage systems.

Visual Dry Run#

Input:

paths = [
  "root/a 1.txt(abcd) 2.txt(efgh)",
  "root/c 3.txt(abcd)",
  "root/c/d 4.txt(efgh)"
]

Step 1 — Parse "root/a 1.txt(abcd) 2.txt(efgh)":

• Root: root/a
• File 1: name=1.txt, content=abcd → full path=root/a/1.txt
• File 2: name=2.txt, content=efgh → full path=root/a/2.txt

Content map after step 1: {abcd: ["root/a/1.txt"], efgh: ["root/a/2.txt"]}

Step 2 — Parse "root/c 3.txt(abcd)":

• Root: root/c
• File: name=3.txt, content=abcd → full path=root/c/3.txt

Content map: {abcd: ["root/a/1.txt", "root/c/3.txt"], efgh: ["root/a/2.txt"]}

Step 3 — Parse "root/c/d 4.txt(efgh)":

• Root: root/c/d
• File: name=4.txt, content=efgh → full path=root/c/d/4.txt

Content map: {abcd: ["root/a/1.txt", "root/c/3.txt"], efgh: ["root/a/2.txt", "root/c/d/4.txt"]}

Step 4 — Filter groups with ≥ 2 entries:

• abcd group: ["root/a/1.txt", "root/c/3.txt"] → keep
• efgh group: ["root/a/2.txt", "root/c/d/4.txt"] → keep

Result: [["root/a/1.txt","root/c/3.txt"], ["root/a/2.txt","root/c/d/4.txt"]]

Solution (Optimal)#

from collections import defaultdict
 
def findDuplicate(paths: list[str]) -> list[list[str]]:
    # Map from content string to list of full file paths
    content_map = defaultdict(list)
 
    for path in paths:
        parts = path.split()
        root = parts[0]  # Directory path
 
        for file_entry in parts[1:]:
            # Parse "filename(content)" format
            paren_idx = file_entry.index('(')
            filename = file_entry[:paren_idx]
            content = file_entry[paren_idx + 1:-1]  # Strip the trailing ')'
 
            full_path = f"{root}/{filename}"
            content_map[content].append(full_path)
 
    # Return only groups with 2 or more files
    return [group for group in content_map.values() if len(group) >= 2]

var findDuplicate = function(paths) {
    // Map from content to list of full file paths
    const contentMap = new Map();
 
    for (const path of paths) {
        const parts = path.split(' ');
        const root = parts[0];
 
        for (let i = 1; i < parts.length; i++) {
            const parenIdx = parts[i].indexOf('(');
            const filename = parts[i].substring(0, parenIdx);
            const content = parts[i].substring(parenIdx + 1, parts[i].length - 1);
 
            const fullPath = `${root}/${filename}`;
            if (!contentMap.has(content)) contentMap.set(content, []);
            contentMap.get(content).push(fullPath);
        }
    }
 
    // Return groups with 2 or more files
    return [...contentMap.values()].filter(group => group.length >= 2);
};

Complexity Analysis

The total input size drives both time and space. Each character is processed once for parsing and once for storage. The filtering step at the end is O(number of unique contents), which is bounded by N.

Common Mistakes#

• Using split('(') and forgetting to strip the trailing ). The content in "file.txt(abcd)" after split('(') is ["file.txt", "abcd)"]. The trailing ) must be removed: content[:-1] or content.rstrip(')').
• Not using defaultdict (or equivalent) and crashing on missing keys. When inserting the first file with a given content, the key does not exist yet. Either use defaultdict(list) or check for key existence before appending.
• Using the filename instead of the full path. The full path must include the directory root. filename alone (1.txt) is not unique — different directories can have identically named files.
• Treating all files with the same content as duplicates even when there is only one file. Groups with exactly one file are not duplicates. Filter to groups with len >= 2.
• Building the path incorrectly. The root is separated from the filename by "/", not " ". f"{root}/{filename}" — do not use space.

Follow-up Questions#

What if file sizes are very large and you cannot use content as a map key? Compute a cryptographic hash (e.g., SHA-256) of the content and use the hash as the key. Hash collisions are astronomically unlikely. This is how content-addressable storage (Git, IPFS, deduplication storage) works in practice.

What if you want to handle symbolic links (multiple paths pointing to the same inode)? Track inodes in addition to content. Two files sharing an inode are the same file — they should be grouped separately from content-identical but different-inode files.

How would you optimize for a real filesystem where reading content is expensive? Use a two-level deduplication: first group by file size (cheap), then compute hashes only within groups of the same size. This avoids hashing files that cannot possibly be duplicates.

What if the directory tree is extremely large and you cannot load all paths at once? Process paths lazily with a generator. For each path, parse and add to the running content map. The algorithm is already streaming-compatible.

How would you delete duplicate files while keeping one copy from each group? Sort each group by path (or by modification date) and keep the first; delete the rest. Wrap deletions in a dry-run mode first to let the user preview what would be deleted.

Key Takeaways#

• LC 609 Find Duplicate File reduces to a "group paths by content" HashMap problem.
• Parse each path string with split() on whitespace, then split each entry on ( to separate filename and content.
• Use defaultdict(list) (Python) or Map with a get-or-create helper (JavaScript) to avoid missing-key errors.
• Always store the FULL path (root + "/" + filename), never just the filename — files in different directories can share names.
• Filter the final groups to those with len >= 2; single-file groups are not duplicates.
• Time and space are both O(N) where N is the total input size.
• For real systems with large files, hash the content (SHA-256) and use the hash as the key — this is content-addressable storage, used by Git, IPFS, and dedup backups.

Related Problems#

• LC 609 — Find Duplicate File in System: This problem.
• LC 49 — Group Anagrams: Same "group by key" pattern — group strings by their sorted form.
• LC 1570 — Dot Product of Two Sparse Vectors: Grouping and matching non-zero components — similar key-based matching.
• LC 205 — Isomorphic Strings: Content-based structural comparison — related to content identity.
• LC 771 — Jewels and Stones: Simpler "group by membership" lookup.
• LC 957 — Prison Cells After N Days: State-based cycle detection — finding repeated system states, similar to finding repeated content.