609. Find Duplicate File in System
Asked at Anthropic
Difficulty
Medium
Time
O(T)
Space
O(T)
Pattern
Array
Companies
1
Problem
You are given a list of strings. Each string describes one directory: the directory path, then one or more files inside it, each with its content.
A single string looks like "root/a 1.txt(abcd) 2.txt(efgh)". The first token is the directory path. Every token after that is a file name followed by its content in parentheses. So this directory holds 1.txt with content abcd and 2.txt with content efgh.
Two files are duplicates when their contents are exactly the same, even if they live in different directories. Return a list of groups. Each group is a list of full file paths (directory_path/file_name) that share the same content. Only include groups with two or more files. The order of the groups and the order inside a group do not matter.
Parsing one directory entry
Constraints
- ●
1 <= paths.length <= 2 * 10^4 - ●
1 <= paths[i].length <= 3000 - ●
1 <= sum(paths[i].length) <= 5 * 10^5 - ●
paths[i] contains only English letters, digits, '/', '.', '(', ')' and ' ' - ●
No two files or directories share a name inside the same directory - ●
Each entry describes a unique directory, and a single space separates the directory path from the file info
Examples
paths = ["root/a 1.txt(abcd) 2.txt(efgh)","root/c 3.txt(abcd)","root/c/d 4.txt(efgh)","root 4.txt(efgh)"][["root/a/2.txt","root/c/d/4.txt","root/4.txt"],["root/a/1.txt","root/c/3.txt"]]paths = ["root/a 1.txt(abcd) 2.txt(efgh)","root/c 3.txt(abcd)","root/c/d 4.txt(efgh)"][["root/a/2.txt","root/c/d/4.txt"],["root/a/1.txt","root/c/3.txt"]]Asked At
1 companies| Company | Difficulty | |
|---|---|---|
| Anthropic | Medium | View all Anthropic questions → |
How to Think About It
Brute force: compare every pair of files character by character — O(n^2) and infeasible.
Hash file contents: read each file, parse the path and content, and use a hash map keyed by content string.
Group files by content hash — files with identical content map to the same bucket.
Return only buckets with more than one file path.
Optimal: single pass O(total characters) time, O(total characters) space for the hash map.
Optimal Approach
Parse each input string to extract the file path and its content. Use a hash map where the key is the file content and the value is a list of file paths that share that content. After processing all entries, collect all map values that contain more than one path — those are the duplicate groups. The algorithm runs in O(total characters) time and space.
Group files by content
What Trips People Up in Real Interviews
Clarify whether file paths are absolute or relative and how spaces in paths are handled.
Confirm that the content string itself does not contain the delimiter ":" — it is guaranteed.
Edge case: no duplicates exist — return an empty list.
Watch for very large content strings — hashing each one is unavoidable but be mindful of memory.
Discuss whether we need to handle symlinks or cyclic references (usually no).
Solution Code
O(T) timedef findDuplicate(paths):
from collections import defaultdict
content_map = defaultdict(list)
for entry in paths:
parts = entry.split(' ')
root = parts[0]
for file_info in parts[1:]:
name, content = file_info.split('(')
content = content[:-1]
content_map[content].append(root + '/' + name)
return [group for group in content_map.values() if len(group) > 1]Frequently Asked Questions
What is the Find Duplicate File in System problem?
Given a list of directory info including file path and file contents, find all groups of duplicate files in the file system and return their paths. Two files are duplicates if they have the same content. The input is an array of strings where each string follows the format "root/d1/d2/.../dm f.txt:(content)" representing the path and content of a file.
How do you solve Find Duplicate File in System?
The optimal approach runs in O(T) time and O(T) space. Scroll up to "Optimal Approach" for the step-by-step walkthrough, diagrams, and code in Python, C++ and Java.
What companies ask Find Duplicate File in System?
Find Duplicate File in System is asked at Anthropic. It is a medium difficulty problem.
What are common mistakes on Find Duplicate File in System?
- Clarify whether file paths are absolute or relative and how spaces in paths are handled.
- Confirm that the content string itself does not contain the delimiter ":" — it is guaranteed.
- Edge case: no duplicates exist — return an empty list.
- Watch for very large content strings — hashing each one is unavoidable but be mindful of memory.
- Discuss whether we need to handle symlinks or cyclic references (usually no).