Design duplicate-file detection using size
Company: Applied Intuition
Role: Software Engineer
Category: Coding & Algorithms
Difficulty: medium
Interview Round: Technical Screen
Quick Answer: This question evaluates a candidate's understanding of filesystem metadata, scalable traversal algorithms, handling symlink and hard link edge cases, and memory/I/O trade-offs when grouping files by attributes such as size.
Constraints
- 1 <= len(filesystem) <= 200000
- 0 <= file size <= 10^12
- All paths are unique absolute paths, and `root` exists in `filesystem`
- If two readable reachable file nodes share the same inode, they represent the same physical file and have the same size
Examples
Input: ({'/': ('dir', ['docs', 'pics', 'shortcut', 'secret'], True), '/docs': ('dir', ['a.txt', 'b.txt', 'same.txt'], True), '/docs/a.txt': ('file', 100, 1, True), '/docs/b.txt': ('file', 100, 2, True), '/docs/same.txt': ('file', 100, 1, True), '/pics': ('dir', ['img1.jpg', 'img2.jpg'], True), '/pics/img1.jpg': ('file', 200, 3, True), '/pics/img2.jpg': ('file', 200, 4, False), '/shortcut': ('symlink', '/'), '/secret': ('dir', ['hidden.txt'], False), '/secret/hidden.txt': ('file', 100, 5, True)}, '/')
Expected Output: ([['/docs/a.txt', '/docs/b.txt']], 2)
Explanation: `/shortcut` is ignored because it is a symlink. `/secret` is unreadable, so it adds one permission error and is not traversed. `/pics/img2.jpg` is an unreadable file, adding another error. `/docs/a.txt` and `/docs/same.txt` share inode 1, so only `/docs/a.txt` is kept as the representative hard link. The only duplicate-by-size group is size 100 with two distinct inodes.
Input: ({'/': ('dir', ['a'], False), '/a': ('file', 10, 1, True)}, '/')
Expected Output: ([], 1)
Explanation: The root directory itself is unreadable, so traversal stops immediately with one permission error.
Hints
- Use an iterative DFS or BFS with a stack or queue so very deep directory trees do not cause recursion-depth problems.
- First deduplicate by inode, then group the surviving representative paths by file size.