Group duplicate files by content
Problem Description
You are provided with a list of files within a filesystem. For each file, you have access to its full path (as a string), its size in bytes (as an integer), and its contents (conceptually, meaning you can read or stream the file's data when necessary).
Two files are considered duplicates if their byte-for-byte contents are identical, irrespective of their names or directory locations.
Task: Your goal is to identify and return groups of duplicate files. Each group should consist of the full paths of files that share identical content. Groups containing only a single file (i.e., unique files) should be omitted from the final output.
Constraints and Expectations
- The system may contain millions of files.
- Reading the full contents of a file is an expensive operation.
- The solution should aim to minimize the number of unnecessary content reads and hashing operations.
Follow-up Questions
- Describe an optimized approach that avoids hashing every file, especially if a large majority of files are unique.
- How would you effectively handle extremely large files (e.g., files exceeding gigabytes in size) without loading their entire contents into memory?
- If hash collisions become a practical concern, what strategy would you employ to definitively confirm that files are true duplicates?
Example
Given the following input files (path, size, content):
/a/x.txt, 4 bytes, content: "ABCD"/b/y.txt, 4 bytes, content: "ABCD"/c/z.txt, 4 bytes, content: "WXYZ"/d/w.txt, 7 bytes, content: "1234567"
The expected output is:
["/a/x.txt", "/b/y.txt"]
AI interview prep
Core dilemma
Balancing the need for accurate duplicate detection with the extreme cost of I/O operations (file reads) and computational overhead (hashing) across a massive dataset of files, while minimizing memory footprint.
3 tradeoffs and 3 stress tests locked
Interview prep
Unlock the interviewer X-Ray rubric, tradeoff matrix, stress tests, clarifying questions, and key concepts.
Group duplicate files by content
Problem Description
You are provided with a list of files within a filesystem. For each file, you have access to its full path (as a string), its size in bytes (as an integer), and its contents (conceptually, meaning you can read or stream the file's data when necessary).
Two files are considered duplicates if their byte-for-byte contents are identical, irrespective of their names or directory locations.
Task: Your goal is to identify and return groups of duplicate files. Each group should consist of the full paths of files that share identical content. Groups containing only a single file (i.e., unique files) should be omitted from the final output.
Constraints and Expectations
- The system may contain millions of files.
- Reading the full contents of a file is an expensive operation.
- The solution should aim to minimize the number of unnecessary content reads and hashing operations.
Follow-up Questions
- Describe an optimized approach that avoids hashing every file, especially if a large majority of files are unique.
- How would you effectively handle extremely large files (e.g., files exceeding gigabytes in size) without loading their entire contents into memory?
- If hash collisions become a practical concern, what strategy would you employ to definitively confirm that files are true duplicates?
Example
Given the following input files (path, size, content):
/a/x.txt, 4 bytes, content: "ABCD"/b/y.txt, 4 bytes, content: "ABCD"/c/z.txt, 4 bytes, content: "WXYZ"/d/w.txt, 7 bytes, content: "1234567"
The expected output is:
["/a/x.txt", "/b/y.txt"]