Remove Sub-Folders from the Filesystem

Remove Sub-Folders from the Filesystem

What is this problem about?

The Remove Sub-Folders from the Filesystem interview question gives you a list of folder paths in a filesystem and asks you to return only the folders that are not sub-folders of any other folder in the list. A folder /a/b is a sub-folder of /a. The result should contain only top-level folders — those not contained within any other folder in the input.

Why is this asked in interviews?

This problem is asked at Microsoft, Meta, Snowflake, Verkada, Amazon, and Google because it tests string prefix matching and efficient folder hierarchy reasoning. The naive O(n^2) approach checks every pair, but sorting the paths lexicographically enables an O(n log n) solution where each path is compared only to the previous accepted path. It also has a Trie-based solution, which tests deep data structure knowledge.

Algorithmic pattern used

The primary pattern is sort and greedy prefix checking. Sort all folders lexicographically. Then iterate: keep the first folder unconditionally. For each subsequent folder, check if it starts with the last kept folder as a prefix followed by /. If yes, it's a sub-folder — skip it. Otherwise, add it to the result and update the last-kept reference. The / check prevents false matches (e.g., /a/b should not be falsely flagged as a sub-folder of /ab).

Example explanation

Folders: ["/a", "/a/b", "/c/d", "/c/d/e", "/c/f"]

Sorted: ["/a", "/a/b", "/c/d", "/c/d/e", "/c/f"]

• /a: keep (first). Last = /a.
• /a/b: starts with /a/ → sub-folder → skip.
• /c/d: does NOT start with /a/ → keep. Last = /c/d.
• /c/d/e: starts with /c/d/ → skip.
• /c/f: does NOT start with /c/d/ → keep.

Result: ["/a", "/c/d", "/c/f"].

Common mistakes candidates make

• Checking prefix without the trailing /, leading to false positives (e.g., /ab falsely matched against /a).
• Sorting numerically or in a custom order instead of plain lexicographic order.
• Using the Trie approach but building it incorrectly by splitting on / and forgetting empty strings from leading slashes.
• Not handling the case where two identical paths appear in the input.

Interview preparation tip

For the Remove Sub-Folders from the Filesystem coding problem, the string sorting and Trie interview pattern both apply. The sorting approach is simpler to implement quickly. The trailing / in the prefix check is the most important detail — get this right by testing the /a vs /ab edge case. Interviewers at Snowflake and Verkada may ask for both approaches — have the Trie solution ready as a follow-up. Practice splitting folder paths by / for the Trie approach.