Katkat
Back

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

AnthropicSoftware Engineer · Onsite
MediumSoftware EngineerOnsiteSoftware Engineering Fundamentals

Last updated

Walk a directory tree and report every group of files with identical contents, printing nothing when there are no duplicates. It tests staged filtering by size and hashes, streaming reads of large files, link and error handling, and reasoning about whether the job is CPU-bound or I/O-bound.

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.

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?

Hints

Hint 1

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 2

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.

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?