Quick Overview

This question evaluates a candidate's competency in file system traversal, robust I/O handling including symbolic links and cycles, content-based deduplication, and algorithmic efficiency within the Coding & Algorithms domain.

Design file deduplication across nested directories

Company: Anthropic

Role: Software Engineer

Category: Coding & Algorithms

Difficulty: medium

Interview Round: Technical Screen

Design and implement a file deduplication tool that, given a root directory, identifies groups of duplicate files. Requirements: traverse nested directories safely; handle symbolic links and potential cycles; minimize I/O with a multi-stage strategy (e.g., compare file sizes, then partial hashes, then full hashes); support very large files; and output duplicate groups with file paths. Explain your data structures, step-by-step algorithm, time and space complexity, and key test cases.

Quick Answer: This question evaluates a candidate's competency in file system traversal, robust I/O handling including symbolic links and cycles, content-based deduplication, and algorithmic efficiency within the Coding & Algorithms domain.

You are given a simulated file system graph and a root path. Implement a file deduplication tool that traverses everything reachable from the root, follows symbolic links safely, avoids infinite loops caused by cycles, and returns groups of duplicate files. The file system is represented by a dictionary `fs` where each key is a path string and each value is one of these node types: - Directory: `{'type': 'dir', 'children': [child_path1, child_path2, ...]}` - File: `{'type': 'file', 'content': '...'}` - Symbolic link: `{'type': 'symlink', 'target': some_path}` Rules: 1. Start traversal from `root`. 2. Follow symlinks, but safely handle cycles such as a symlink pointing back to an ancestor. 3. Ignore broken symlinks whose target does not exist. 4. Process each real directory and real file at most once after resolving symlinks. 5. Two files are duplicates if their full contents are exactly equal. 6. To mimic a real deduplication tool, use a multi-stage strategy: - compare file sizes first, - then compare a small partial signature, - then compare full hashes and exact content. 7. Return duplicate groups as sorted lists of canonical file paths (the resolved non-symlink file paths). Each group must contain at least 2 paths. 8. Sort the final list of groups by the first path in each group. A strong interview answer should also be able to explain the data structures used, the traversal strategy, why cycle handling is necessary, and the time/space complexity.

Constraints

  • 1 <= len(fs) <= 10^5
  • The file system graph may contain cycles due to symbolic links or repeated child references
  • File contents are strings
  • The total length of all reachable file contents is at most 10^6 characters
  • Broken symlinks may appear and should be ignored

Examples

Input: ({'/': {'type': 'dir', 'children': ['/docs', '/img', '/readme.txt']}, '/docs': {'type': 'dir', 'children': ['/docs/a.txt', '/docs/b.txt']}, '/img': {'type': 'dir', 'children': ['/img/pic.bin']}, '/readme.txt': {'type': 'file', 'content': 'hello'}, '/docs/a.txt': {'type': 'file', 'content': 'alpha'}, '/docs/b.txt': {'type': 'file', 'content': 'hello'}, '/img/pic.bin': {'type': 'file', 'content': 'xyz'}}, '/')

Expected Output: [['/docs/b.txt', '/readme.txt']]

Explanation: Only '/docs/b.txt' and '/readme.txt' have identical content.

Input: ({'/': {'type': 'dir', 'children': ['/A', '/B']}, '/A': {'type': 'dir', 'children': ['/A/f1.txt', '/A/to_root']}, '/B': {'type': 'dir', 'children': ['/B/f2.txt', '/B/link_to_A']}, '/A/f1.txt': {'type': 'file', 'content': 'same-data'}, '/B/f2.txt': {'type': 'file', 'content': 'same-data'}, '/A/to_root': {'type': 'symlink', 'target': '/'}, '/B/link_to_A': {'type': 'symlink', 'target': '/A'}}, '/')

Expected Output: [['/A/f1.txt', '/B/f2.txt']]

Explanation: The symlinks create cycles back to already visited directories, but the traversal remains safe. The two real files are duplicates.

Hints

  1. Treat the structure as a graph, not a tree. Keep visited sets for resolved directories and resolved files so symlink cycles do not cause infinite traversal.
  2. Do not fully compare every file against every other file. First group by size, then by a cheap prefix/suffix signature, and only then compute a full hash for the remaining candidates.

Loading coding console...