Design duplicate-file detection using size

You are given a large POSIX-like filesystem containing millions of files across nested directories. Design an algorithm to find groups of duplicate files when you are not allowed to read file contents; you may only use metadata such as file size, timestamps, permissions, and inode information. Describe how you will traverse the directory tree, avoid infinite loops with symlinks, account for hard links, and handle permission errors. Explain your data structures (e.g., mapping sizes to file lists), memory and I/O considerations for very large datasets, and how you would stream or partition the work. Define what 'duplicate' means under the no-content-read constraint, discuss potential false positives and their impact, and provide time and space complexity analyses.

Duplicate File Groups Using Size-Only Metadata

You are given a simulated POSIX-like filesystem and a starting directory root. Implement the core of a duplicate-file detector when file contents cannot be read.

Each entry in filesystem is stored by absolute path and is one of:

• ('dir', [child_name1, child_name2, ...], readable)
• ('file', size, inode, readable)
• ('symlink', target_path)

Traverse the tree starting from root and find duplicate files using only metadata.

Rules:

1. Never follow symlinks. This avoids infinite loops.
2. If a directory is unreadable, count one permission error and do not traverse inside it.
3. If a file is unreadable, count one permission error and skip it.
4. Hard links are represented by multiple file paths with the same inode. They refer to the same physical file, so they must be counted only once. Use the lexicographically smallest readable reachable path as that inode's representative.
5. Under the no-content-read constraint, two files are considered duplicates if they have different inodes but the same size.

Return a tuple (groups, permission_errors) where:

• groups is a list of duplicate groups.
• Each duplicate group is a lexicographically sorted list of representative file paths.
• Only include sizes that have at least 2 distinct representative files.
• Order groups by increasing file size.

This definition can produce false positives in real systems, but for this problem it is the required behavior.

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

Example 1

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)}, '/')
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.

Example 2

Input: ({'/': ('dir', ['a'], False), '/a': ('file', 10, 1, True)}, '/')
Output: ([], 1)

Explanation: The root directory itself is unreadable, so traversal stops immediately with one permission error.

Hints

1. Use an iterative DFS or BFS with a stack or queue so very deep directory trees do not cause recursion-depth problems.
2. First deduplicate by inode, then group the surviving representative paths by file size.