Design a duplicate-file removal algorithm

Your filesystem contains millions of photos. Duplicates are strictly byte-identical files (no ML/CV similarity). Design an algorithm to detect and delete duplicates efficiently on a single machine. Specify: how you compute and store per-file signatures (e.g., full hash vs size+partial+full, streaming I/O); how the in-memory key–value store maps signatures to canonical file paths; how you handle hash collisions and verification before deletion; how you treat files with identical names but different content, permissions, or timestamps; big-O time and space complexity and I/O considerations; and provide pseudocode for a function that returns the set of file paths safe to delete.

What a Strong Answer Covers

• A clear algorithm with the right data structures and enough pseudocode or code-level detail to implement it.
• A correctness argument that explains why the algorithm covers all required cases.
• Time and space complexity, plus at least one alternative approach when relevant.
• Focused tests for normal cases, edge cases, and failure modes.

Follow-up Questions

• How would the approach change if the input were streaming or too large for memory?
• What invariants would you assert in production code?
• Which tests would catch off-by-one, duplicate, or tie-breaking bugs?

Part 1: Single-Machine Verified Duplicate-File Removal

You are given an in-memory scan of files on one machine. Each file record is [path, content, permissions, timestamp], where content represents the exact bytes of the file as a string. Two files are duplicates only if content is exactly equal. Identical names, permissions, and timestamps do not make files duplicates and should not affect duplicate detection. For each group of byte-identical files, keep the lexicographically smallest path as the canonical file and return every other path that is safe to delete. Return the delete paths sorted lexicographically. A correct solution must verify exact content, so files that could share a weak size or prefix signature but differ in bytes must not be deleted.

Constraints

• 0 <= len(files) <= 100000
• Each path is unique.
• path, content, permissions, and timestamp are strings.
• content may be an empty string, representing a zero-byte file.
• Duplicate detection is based only on exact content equality.
• Target complexity: O(total_bytes + n log n) time including output sorting.

Examples

Example 1

Input: ([],)
Output: []

Explanation: No files means there is nothing to delete.

Example 2

Input: ([['/a.jpg', 'abc', 'rw', '10']],)
Output: []

Explanation: A single file has no duplicate.

Hints

1. For each exact content value, track the canonical path seen so far.
2. If a later duplicate has a smaller path than the current canonical path, the old canonical becomes deletable.

Part 2: External-Merge Duplicate Detection for Too-Large Input

A first pass over a very large filesystem has produced multiple sorted runs on disk. Each run contains records [size, digest, path, content], where all fields are strings, size is the decimal string form of len(content), and digest is a deterministic full-file digest. Each individual run is sorted by numeric size, then digest, then path. Your task is to merge the runs as a stream and identify safe-to-delete duplicate paths. Files with the same exact content are assumed to have the same size and digest, but different contents may still share a digest due to collision, so exact content verification is required inside each equal (size, digest) group. For each exact-content group, keep the lexicographically smallest path and delete the others. Return sorted delete paths.

Constraints

• 0 <= number of runs <= 10000
• 0 <= total number of records <= 100000
• Each run is sorted by numeric size, then digest, then path.
• Each path is unique.
• If two files have identical content, their size and digest fields are identical.
• Different contents may have the same digest, so exact content comparison is still required.

Examples

Example 1

Input: ([],)
Output: []

Explanation: No runs means there are no records.

Example 2

Input: ([[], [['3', 'h1', '/a', 'abc']]],)
Output: []

Explanation: Empty runs are ignored, and the single file has no duplicate.

Hints

1. Use a min-heap to k-way merge the already sorted runs.
2. You only need to keep the current equal (size, digest) group in memory before verifying exact contents.

Part 3: Validate Production Invariants for a Duplicate-Deletion Plan

Before deleting files in production, a duplicate-removal system should assert safety invariants. You are given scanned files and a proposed deletion list. Each file record is [path, content]. Return the invariant violation codes, in the fixed order listed below. The invariants are: file paths in the scan must be unique; delete_paths must not contain duplicates; every delete path must exist in the scan; every deleted file must have at least one non-deleted file with identical content; and for any duplicate content group, the lexicographically smallest path must not be deleted if any file from that group is deleted.

Constraints

• 0 <= len(files) <= 100000
• 0 <= len(delete_paths) <= 100000
• path and content are strings.
• content may be an empty string.
• When duplicate file paths exist, report DUPLICATE_FILE_PATH; other checks should still be computed using the first occurrence of each path.

Examples

Example 1

Input: ([['/b', 'cat'], ['/a', 'cat'], ['/u', 'dog']], ['/b'])
Output: []

Explanation: /b has a kept identical copy at /a, and the canonical /a is not deleted.

Example 2

Input: ([], [])
Output: []

Explanation: An empty scan with an empty deletion plan violates no invariant.

Hints

1. Build counts for scanned paths and delete paths before validating content-based safety.
2. For each content group, compare the delete set against the kept paths and the lexicographically smallest canonical path.

Part 4: Select Tests Covering Deduplication Bug Categories

You are designing a focused test suite for a duplicate-file remover. Each candidate test scenario has a name and a comma-separated list of bug categories it can catch. The only required categories are off_by_one, duplicate, and tie_breaking. Select the smallest number of test scenarios whose union covers all three categories. If multiple selections use the same number of tests, return the lexicographically smallest sorted list of selected names. If the categories cannot all be covered, return an empty list.

Constraints

• 0 <= len(candidates) <= 100000
• Each candidate name is unique.
• tags may contain off_by_one, duplicate, tie_breaking, unknown tags, spaces, or be empty.
• Unknown tags should be ignored.
• The returned list must be sorted lexicographically.

Examples

Example 1

Input: ([['two_equal_files', 'off_by_one,duplicate'], ['reverse_order_names', 'tie_breaking'], ['single_file', 'off_by_one']],)
Output: ['reverse_order_names', 'two_equal_files']

Explanation: The first and second tests together cover all three required categories.

Example 2

Input: ([],)
Output: []

Explanation: No candidates means full coverage is impossible.

Hints

1. There are only three required categories, so represent coverage as a 3-bit mask.
2. Dynamic programming over masks can track the best chosen name list for each coverage state.

Solution

Solution Alignment

The prompt asks for an implementation-level answer. The safest way to present it is to define the state, maintain clear invariants, then walk through complexity and tests.

Problem Restatement

Your filesystem contains millions of photos. Duplicates are strictly byte-identical files (no ML/CV similarity). Design an algorithm to detect and delete duplicates efficiently on a single machine. Specify: how you compute and store per-file signatures (e.g., full hash vs size+partial+full, streaming I/O); how the in-memory key–value store maps signatures to canonical file paths; how you handle hash collisions and verification before deletion; how you treat files with identical names but different content, permissions, or timestamps; big-O time and space complexity and I/O considerations; and provide pseudocode for a function that returns the set of file paths safe to delete.

Recommended Approach

Model the states explicitly and use BFS for unweighted shortest paths, Dijkstra for weighted non-negative paths, or topological DP for DAGs. Track visited states at the right granularity so cycles do not cause repeated work.

Correctness

The implementation should maintain an invariant after each loop or operation that directly matches the problem statement. At termination, that invariant implies the returned value has considered every valid candidate exactly once, or has preserved the required data-structure state after every API call.

Complexity

BFS is O(V + E) time and O(V) space for a standard graph. Expanded-state problems multiply those bounds by the number of state dimensions.

Edge Cases and Tests

Disconnected graph, source equals target, cycles, duplicate edges, unreachable target, and whether the answer counts nodes, edges, moves, or transfers.