Remove Sub-Folders from the Filesystem
01 · Problem
You are given an array folder of distinct absolute folder paths. Each path starts with / and is made of one or more segments of lowercase letters separated by /, such as "/a/bc/d".
A folder is a sub-folder of another listed folder p if its path starts with p followed by a /. Note that "/a/bc" is not a sub-folder of "/a/b": the match must end on a segment boundary.
Remove every folder that is a sub-folder of some other folder in the list and return the remaining folders sorted in ascending lexicographic order.
02 · Examples
folder = ["/lib","/lib/js","/src/app","/src/app/ui","/src/db"]
["/lib","/src/app","/src/db"]
"/lib/js" lives inside "/lib" and "/src/app/ui" lives inside "/src/app", so both are removed.
folder = ["/var","/var/log/nginx","/var/log/app/old"]
["/var"]
Both deeper folders sit somewhere under "/var", even though "/var/log" itself is not listed.
folder = ["/usr/bin","/usr/binx","/usr/lib"]
["/usr/bin","/usr/binx","/usr/lib"]
"/usr/binx" starts with the characters "/usr/bin" but not at a segment boundary, so nothing is removed.
03 · Constraints
- 011 <= folder.length <= 4 * 104
- 022 <= folder[i].length <= 100
- 03folder[i] contains only lowercase English letters and '/', starts with '/', and has no empty segments or trailing '/'
- 04All entries of folder are unique
04 · Optimal complexity
- Time
- O(n * L * log n)
- Space
- O(n * L)
Practice it alone or rehearse it as an interview.
Practice Mode gives you an editor and test runs, nothing else. AI Interview Mode puts a voice interviewer on the other side, adds a clock, and ends with a scored summary of the round.