FastPrep
Problem · Hash Table

Find Duplicate Files by Content

Learn this problem
● MediumDropbox logoDropboxFULLTIMEONSITE INTERVIEW

Problem statement

You have enumerated the files in a directory hierarchy. The parallel arrays paths and contents describe those files: contents[i] is the complete content of the file at paths[i].

Find every group of duplicate files. Two files are duplicates exactly when their complete content strings are equal.

Return only groups containing at least two paths. Sort the paths inside each group lexicographically, then sort the groups lexicographically by their first path. Files with unique content do not appear in the result.

Function

findDuplicateFiles(paths: String[], contents: String[]) → String[][]

Examples

Example 1

paths = ["/docs/a.txt","/docs/archive/b.txt","/images/c.png","/tmp/d.txt"]contents = ["draft","draft","pixels","draft"]return = [["/docs/a.txt","/docs/archive/b.txt","/tmp/d.txt"]]

The three text files contain the exact string draft. The image content is unique, so its path is omitted.

Example 2

paths = ["/b/y","/a/x","/d/r","/a/z","/c/q"]contents = ["blue","red","solo","blue","red"]return = [["/a/x","/c/q"],["/a/z","/b/y"]]

There are two duplicate groups. Sorting each group puts its paths in lexical order; comparing the first paths places the red group before the blue group.

Constraints

  • 1 <= paths.length <= 2 * 10^5
  • contents.length == paths.length
  • Every path is a unique non-empty absolute path.
  • Each content string has length at most 10^4 and may be empty.
  • The total number of characters across paths and contents is at most 2 * 10^6.
  • Content comparison is exact and case-sensitive.

More Dropbox problems

drafts saved locally
public String[][] findDuplicateFiles(String[] paths, String[] contents) {
    // Write your code here.
}
paths["/docs/a.txt","/docs/archive/b.txt","/images/c.png","/tmp/d.txt"]
contents["draft","draft","pixels","draft"]
expected[["/docs/a.txt", "/docs/archive/b.txt", "/tmp/d.txt"]]
checking account