Find Duplicate File in System
MedPrompt
Given a list paths of directory info, including the directory path, and all the files with contents in this directory, return all the duplicate files in the file system in terms of their paths. You may return the answer in any order.
A group of duplicate files consists of at least two files that have the same content.
A single directory info string in the input list has the following format:
"root/d1/d2/.../dm f1.txt(f1_content) f2.txt(f2_content) ... fn.txt(fn_content)"
It means there are n files (f1.txt, f2.txt ... fn.txt) with content (f1_content, f2_content ... fn_content) respectively in the directory "root/d1/d2/.../dm". Note that n >= 1 and m >= 0. If m = 0, it means the directory is just the root directory.
The output is a list of groups of duplicate file paths. For each group, it contains all the file paths of the files that have the same content. A file path is a string that has the following format:
"directory_path/file_name.txt"
Example 1:
Input: paths = ["root/a 1.txt(abcd) 2.txt(efgh)","root/c 3.txt(abcd)","root/c/d 4.txt(efgh)","root 4.txt(efgh)"]
Output: [["root/a/2.txt","root/c/d/4.txt","root/4.txt"],["root/a/1.txt","root/c/3.txt"]]Example 2:
Input: paths = ["root/a 1.txt(abcd) 2.txt(efgh)","root/c 3.txt(abcd)","root/c/d 4.txt(efgh)"]
Output: [["root/a/2.txt","root/c/d/4.txt"],["root/a/1.txt","root/c/3.txt"]]
Constraints:
1 <= paths.length <= 2 * 1041 <= paths[i].length <= 30001 <= sum(paths[i].length) <= 5 * 105paths[i]consist of English letters, digits,'/','.','(',')', and' '.- You may assume no files or directories share the same name in the same directory.
- You may assume each given directory info represents a unique directory. A single blank space separates the directory path and file info.
Follow up:
- Imagine you are given a real file system, how will you search files? DFS or BFS?
- If the file content is very large (GB level), how will you modify your solution?
- If you can only read the file by 1kb each time, how will you modify your solution?
- What is the time complexity of your modified solution? What is the most time-consuming part and memory-consuming part of it? How to optimize?
- How to make sure the duplicated files you find are not false positive?
Approaches
2 approaches with complexity analysis and trade-offs.
This approach involves first parsing all the input strings to extract a list of all file paths and their corresponding contents. Then, it iterates through this list, comparing each file with every other file to find duplicates. Files with identical content are grouped together.
Algorithm
- Create a helper class or a simple data structure (like a Pair) to store
(filePath, content). - Create a list, say
allFiles, to hold these pairs. - Iterate through the input
pathsarray:- a. For each string, parse it to extract the directory path and file information.
- b. For each file, create a
(filePath, content)pair and add it toallFiles.
- Initialize an empty list
resultto store the groups of duplicate file paths. - Initialize a boolean array
visitedof the same size asallFiles, all set tofalse. - Iterate from
i = 0toallFiles.size() - 1:- a. If
visited[i]istrue, skip to the next iteration. - b. Create a new list
currentGroupand addallFiles.get(i).filePath. - c. Iterate from
j = i + 1toallFiles.size() - 1:- d. If
visited[j]isfalseand the content of fileimatches the content of filej:- i. Add
allFiles.get(j).filePathtocurrentGroup. - ii. Set
visited[j] = true.
- i. Add
- d. If
- e. If
currentGroup.size() > 1, addcurrentGrouptoresult.
- a. If
- Return
result.
Walkthrough
First, we need to process the input paths array. We'll iterate through each string, parse it to get the directory path and the individual file information. For each file, we extract its name and content, and construct the full file path. We store these (full_path, content) pairs in a list.
After creating this list of all files, we use a nested loop to compare every pair of files. A boolean array visited is used to avoid redundant comparisons and to ensure each file belongs to only one group.
The outer loop picks a file that hasn't been visited yet. The inner loop compares this file's content with all subsequent unvisited files. If a match is found, the matching file's path is added to the current group, and it's marked as visited.
If a group contains more than one file path at the end of the inner loop, it's considered a group of duplicates and is added to the final result list.
class Solution { class FileInfo { String path; String content; FileInfo(String p, String c) { this.path = p; this.content = c; } } public List<List<String>> findDuplicate(String[] paths) { List<FileInfo> allFiles = new ArrayList<>(); for (String pathInfo : paths) { String[] parts = pathInfo.split(" "); String dir = parts[0]; for (int i = 1; i < parts.length; i++) { String file = parts[i]; int contentStart = file.indexOf('('); String fileName = file.substring(0, contentStart); String content = file.substring(contentStart + 1, file.length() - 1); allFiles.add(new FileInfo(dir + "/" + fileName, content)); } } List<List<String>> result = new ArrayList<>(); boolean[] visited = new boolean[allFiles.size()]; for (int i = 0; i < allFiles.size(); i++) { if (visited[i]) { continue; } List<String> currentGroup = new ArrayList<>(); currentGroup.add(allFiles.get(i).path); for (int j = i + 1; j < allFiles.size(); j++) { if (!visited[j] && allFiles.get(i).content.equals(allFiles.get(j).content)) { currentGroup.add(allFiles.get(j).path); visited[j] = true; } } if (currentGroup.size() > 1) { result.add(currentGroup); } } return result; }}Complexity
Time
O(L + M^2 * C), where L is the total length of all input strings, M is the total number of files, and C is the maximum length of a file's content. The O(L) part is for parsing the input. The O(M^2 * C) part is for the nested loop comparing every pair of files.
Space
O(L), required to store the list of all file paths and their contents after parsing, where L is the total length of all input strings.
Trade-offs
Pros
Conceptually simple and straightforward to implement without complex data structures like hash maps.
Cons
Highly inefficient due to the nested loop structure, leading to a quadratic time complexity relative to the number of files.
Repeatedly compares file contents, which can be slow if contents are large.
Solutions
Solution
class Solution { public List < List < String >> findDuplicate ( String [] paths ) { Map < String , List < String >> d = new HashMap <>(); for ( String p : paths ) { String [] ps = p . split ( " " ); for ( int i = 1 ; i < ps . length ; ++ i ) { int j = ps [ i ]. indexOf ( '(' ); String content = ps [ i ]. substring ( j + 1 , ps [ i ]. length () - 1 ); String name = ps [ 0 ] + '/' + ps [ i ]. substring ( 0 , j ); d . computeIfAbsent ( content , k -> new ArrayList <>()). add ( name ); } } List < List < String >> ans = new ArrayList <>(); for ( var e : d . values ()) { if ( e . size () > 1 ) { ans . add ( e ); } } return ans ; } }Video walkthrough
Newsletter
One sharp idea, every week
System design and interview prep — short enough to finish.
No spam. Unsubscribe anytime.
Practice
Same difficulty — related problems to reinforce the pattern.