Find Duplicate Files by Content in a Directory Tree and Explain CPU vs I/O Costs

Write a program that takes the path of a root directory, walks the entire tree beneath it, and finds every group of regular files whose contents are byte-for-byte identical, regardless of their names or where they sit in the tree. Print one line per duplicate group, listing the paths in that group. A file that has no identical twin is never printed, and if the tree contains no duplicates at all the program must print nothing: no header, no blank line, no "no duplicates found" message. You may write it in any mainstream language. No test cases are provided: you are expected to build your own small test directories, run your program against them, and sort out any local environment problems yourself. Be ready to explain which parts of the program are limited by CPU and which by disk I/O, and how that affects the design. ```hint Rule files out cheaply Before reading any file contents, think about which piece of file metadata already proves that two files cannot be identical. ``` ```hint Know where the time goes Consider how the cost profile differs between a tree of a million tiny files and a tree of a few multi-gigabyte files, and which resource each one saturates. ``` ### Constraints and Clarifications - Only regular files are compared; directories and special files (devices, sockets, pipes) are not. - Two files are duplicates only if their full contents are identical; names, timestamps and permissions do not matter. - Files can be much larger than available memory, and the tree can contain a very large number of files. ### Clarifying Questions - Should symbolic links be followed, and could following them create cycles in the walk? - Are two hard links to the same underlying file considered duplicates, or the same file? - Should empty files be reported as duplicates of each other? - What should happen when a file or directory cannot be read, or changes while the scan is running? - Is a matching cryptographic hash enough to call two files identical, or must a byte-by-byte comparison confirm it? - Does the order of groups, or of paths within a group, matter to whoever consumes the output? ### What a Strong Answer Covers - A staged filtering strategy that avoids reading or hashing files that cannot possibly have a duplicate - Chunked, streaming reads so memory use stays bounded no matter how large a file is - Exactly correct output in the no-duplicates case and for singleton files, as the problem statement requires - Explicit decisions on symbolic links, hard links, empty files, unreadable files and files that change during the scan - A concrete CPU versus I/O analysis, and a concurrency approach that matches whichever resource is the bottleneck - Self-written tests that exercise the edge cases, since none are supplied ### Follow-up Questions - The tree lives on a network file system where every byte read is slow and billed. How do you minimize the bytes you read? - How would you split this job across many machines to scan a petabyte-scale storage system? - The tree changes continuously. How would you keep the duplicate groups up to date without rescanning everything? - You are now asked to reclaim space by replacing duplicates with links to a single copy. How do you make that safe if the process crashes halfway through?