How do I practice coding and algorithm questions?

Use PracHub's coding console to write, test, and debug your solutions in Python or JavaScript. View hints, test against sample inputs, and compare with official solutions.

What difficulty level is this coding question?

This is a medium difficulty Coding & Algorithms question, commonly asked during Technical Screen rounds at Abnormal Security.

What role is this question designed for?

This question is commonly asked for Software Engineer candidates at Abnormal Security during technical interviews.

Design a duplicate-file removal algorithm | Abnormal Security Coding Question

Quick Overview

Design a duplicate-file removal algorithm evaluates algorithm design, data structures, correctness, complexity, edge cases, and implementation details in a realistic interview setting. A strong answer states assumptions, handles edge cases, explains trade-offs, and shows how to validate the result clearly.

Design a duplicate-file removal algorithm

Company: Abnormal Security

Role: Software Engineer

Category: Coding & Algorithms

Difficulty: medium

Interview Round: Technical Screen

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.

Quick Answer: Design a duplicate-file removal algorithm evaluates algorithm design, data structures, correctness, complexity, edge cases, and implementation details in a realistic interview setting. A strong answer states assumptions, handles edge cases, explains trade-offs, and shows how to validate the result clearly.

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

Input: ([],)

Expected Output: []

Explanation: No files means there is nothing to delete.

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

Expected Output: []

Explanation: A single file has no duplicate.

Hints

For each exact content value, track the canonical path seen so far.
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

Input: ([],)

Expected Output: []

Explanation: No runs means there are no records.

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

Expected Output: []

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

Hints

Use a min-heap to k-way merge the already sorted runs.
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

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

Expected Output: []

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

Input: ([], [])

Expected Output: []

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

Hints

Build counts for scanned paths and delete paths before validating content-based safety.
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

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

Expected Output: ['reverse_order_names', 'two_equal_files']

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

Input: ([],)

Expected Output: []

Explanation: No candidates means full coverage is impossible.

Hints

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

Quick Overview