Files With the Same Content

Medium

You are given a file system dump listing. Each line describes one folder: first its path, then its files separated by spaces, each written as name(content). For example, the line "home/docs a.txt(hello) b.txt(world)" means the folder home/docs holds a file a.txt with the text hello and a file b.txt with the text world. The full path of a file is the folder path, then /, then the file name, for example home/docs/a.txt. Find every group of two or more files with identical content and return the groups as lists of full paths. The order of the groups and of the paths inside each group does not matter.

Example 1

listing=["home/docs a.txt(hello) b.txt(world)", "home/pics c.txt(hello)", "home d.txt(bye)"] → [['home/docs/a.txt', 'home/pics/c.txt']]

Only home/docs/a.txt and home/pics/c.txt share the same content, hello. The other files are unique.

Example 2

listing=["disk x.txt(42) y.txt(42) z.txt(42)", "disk/tmp w.txt(7)"] → [['disk/x.txt', 'disk/y.txt', 'disk/z.txt']]

Three files in the same folder have equal content and form one group.

Example 3

listing=["root a.txt(one)", "root/b c.txt(two)"] → []

Constraints

1 ≤ len(listing) ≤ 2 · 10⁴
1 ≤ len(listing[i]) ≤ 3000, the total length of all lines is at most 5 · 10⁵
A folder path is made of names of English letters and digits joined by /; a file name uses English letters, digits and dots; content is a non-empty string of English letters and digits
Each folder has at least one file, and file names within a folder are distinct
Each folder is described at most once

Have you seen this problem in a real interview?

Solved by0

Tried by0

Submissions0

Acceptance—

Topics

Array Hash Table String