Design an Iterative Path Tree and Clarify File Lookup Semantics

# Design an Iterative Path Tree and Clarify File Lookup Semantics An interviewer gives you a collection of unique absolute paths and asks you to build a directory tree, then find complete file paths by traversing that tree. Directory names can repeat under different parents, and individual paths may be very long. Your first design stores an entire accumulated path in every node. The interviewer asks you to replace it with nodes that store one path component and to traverse with an explicit stack rather than recursion. The captured example contains this input: ```text directories = [ "/a", "/a/b", "/a/c/file1.txt", "/a/c/d", "/e", "/e/c", "/e/f/file2.txt" ] ``` The displayed path listing includes `/a/b/c`, which is absent from the input, and omits `/a/c/d`, which is present. The source also does not say how a node is identified as a file, whether the search has a target, or what order results require. Explain how you would represent and build the component tree, reconstruct complete paths, and traverse it iteratively. Before claiming an exact set of file results, identify the missing contract details and the inconsistent example that the interviewer must resolve. ### Clarifying Questions to Ask - Does every input path name a file, or can an input path name a directory? - If files and directories share the same string form, what metadata marks a file? - Are we returning all files, looking for a particular file name, or applying another predicate? - Should implicit parent nodes be returned, or only paths explicitly supplied in the input? - Is any output order required? - Is `/a/b/c` a correction to `/a/c/d`, or is the displayed listing erroneous? - Are paths canonical, and how should repeated separators, trailing separators, `.` or `..` be handled? ### What a Strong Answer Covers - Splits each canonical path into components and stores each component once beneath its parent. - Uses a child map keyed by component name so repeated names under different parents remain distinct. - Marks whether a node corresponds to an explicitly supplied path without treating that marker as proof that the node is a file. - Reconstructs a complete path from traversal state or parent links instead of copying the accumulated path into every node. - Uses an explicit stack and handles deep trees without call-stack growth. - States that exact file results and ordering depend on the missing file predicate, metadata, and corrected example. - Describes time and space in terms of the total number of path components and returned path characters. ### Follow-up Questions 1. What are the memory tradeoffs between parent links and carrying a component list in each stack frame? 2. How would you add and remove paths after the initial build? 3. How would you distinguish a directory explicitly present in the input from an implicit parent? 4. How would the design change if multiple threads update and search the tree?