Constraints

• 0 <= len(entries) <= 100000
• 0 <= prefix_bytes <= 4096
• 1 <= chunk_size <= 4096
• The total number of bytes across readable regular files is at most 10^7
• For valid readable file records, 'content' is a bytes object and 'path' values are unique

Examples

Solution

def solution(entries, prefix_bytes, chunk_size):
    from collections import defaultdict
    import hashlib

    if prefix_bytes < 0 or chunk_size <= 0:
        raise ValueError('prefix_bytes must be >= 0 and chunk_size must be > 0')

    def digest_bytes(data):
        hasher = hashlib.sha256()
        view = memoryview(data)
        for i in range(0, len(data), chunk_size):
            hasher.update(view[i:i + chunk_size])
        return hasher.hexdigest()

    size_groups = defaultdict(list)

    for entry in entries:
        if not isinstance(entry, dict):
            continue
        if entry.get('type') != 'file' or not entry.get('readable', False):
            continue

        path = entry.get('path')
        content = entry.get('content')
        if path is None or not isinstance(content, (bytes, bytearray)):
            continue

        if isinstance(content, bytearray):
            content = bytes(content)

        size_groups[len(content)].append((path, content))

    duplicates = []

    for files_same_size in size_groups.values():
        if len(files_same_size) < 2:
            continue

        prefix_groups = defaultdict(list)
        for path, content in files_same_size:
            prefix_groups[content[:prefix_bytes]].append((path, content))

        for files_same_prefix in prefix_groups.values():
            if len(files_same_prefix) < 2:
                continue

            hash_groups = defaultdict(list)
            for path, content in files_same_prefix:
                digest = digest_bytes(content)
                hash_groups[digest].append((path, content))

            for files_same_hash in hash_groups.values():
                if len(files_same_hash) < 2:
                    continue

                exact_groups = defaultdict(list)
                for path, content in files_same_hash:
                    exact_groups[content].append(path)

                for paths in exact_groups.values():
                    if len(paths) > 1:
                        paths.sort()
                        duplicates.append(paths)

    duplicates.sort(key=lambda group: group[0])
    return duplicates

Time complexity: O(n + B + n log n) worst-case, where n is the number of entries and B is the total number of bytes hashed across candidate files. Space complexity: O(n).

Hints

1. Files with different sizes can never be duplicates, so size is a very strong first filter.
2. Inside a candidate bucket, use a hash map from digest to paths so you avoid O(k^2) pairwise comparisons.