Katkat
Back

Find Duplicate Files with a Hand-Written Directory Traversal

SnapchatSoftware Engineer · Technical Screen
MediumSoftware EngineerTechnical ScreenSoftware Engineering Fundamentals

Last updated

This problem tests iterative directory traversal techniques, efficient file hashing strategies to handle large data, and the ability to manage edge cases like file system inconsistencies or symbolic links.

Problem: Duplicate File Finder

Given a root directory path, write a function that identifies all sets of duplicate files within that directory tree. A file is considered a duplicate if it has the exact same content as another file, regardless of its filename or location.

Requirements

  • Traversal: You must implement an iterative approach to traverse the directory tree (do not use recursive functions).
  • Efficiency: Since files can be very large (GBs), avoid loading entire files into memory. Use a strategy to minimize I/O, such as comparing file sizes first and only hashing files that share the same size.
  • Links: Ignore symbolic links to prevent infinite loops, but treat hard links appropriately based on file system identity (inode).
  • Output: Return a list of lists, where each inner list contains the paths of files that have identical content.

Function Signature

def find_duplicates(root_path: str) -> List[List[str]]:
    pass

Example

If the directory contains:

  • /dir1/a.txt (content: "hello")
  • /dir1/b.txt (content: "world")
  • /dir2/c.txt (content: "hello")

Output: [['/dir1/a.txt', '/dir2/c.txt']]

Considerations

  • How will you handle files that are modified while the scan is in progress?
  • What if two files have the same size and hash, but are still different? (Collision probability).
  • Your solution should handle deeply nested directory structures without hitting stack overflow limits.

Hints

Hint 1

Use a stack or queue data structure to perform a manual Depth-First or Breadth-First traversal of the file system.

Hint 2

Group files by size first using a hash map; only proceed to compute hashes for groups that contain two or more files.

Hint 3

To handle large files, read them in small, fixed-size chunks and update a cryptographic hash (like SHA-256) incrementally.

Follow-up questions

  • How would you modify your solution to handle a multi-petabyte file system where scanning the entire tree at once is not feasible?
  • If the file system reports that two files have the same inode, how should your logic handle them?
  • How would you handle a 'Race Condition' where a file is deleted or modified after you have recorded its size but before you read its content?