File-System Tree from a Record Stream Where Children Can Arrive Before Parents

Build an in-memory file system from a stream of input records. Each record describes one file or directory and names its parent, so together the records define a tree. Parse the records, design the nodes that store the tree with its parent/child relationships, and make it work when the records arrive as a stream in which a child can appear before its parent. You are given sample input but no harness: write the code that feeds the input to your class, and write and run your own test cases. The record format was not reported; the format below is an assumption that makes the parts concrete. ```text records (one per line: id,parent_id,name,kind; the root has an empty parent_id and name) 3,2,report.pdf,file 2,1,docs,dir 4,2,draft.txt,file 1,,,dir 6,5,cat.png,file 5,1,photos,dir tree after all records (children listed by name) / docs/ draft.txt report.pdf photos/ cat.png ``` `report.pdf` (id 3) arrives before its parent `docs` (id 2), `docs` arrives before the root, and `cat.png` (id 6) arrives before `photos` (id 5). ### Constraints and Clarifications - The report does not say which queries the structure must answer. To make it testable, assume it must return a node's full path (`/docs/report.pdf` for id 3) and print the tree as shown above. ### Clarifying Questions - What exactly is in a record, which fields can be missing or malformed, and are ids guaranteed to be unique? - Is the input finite, so everything can be resolved at the end, or an unbounded stream that must answer queries while records are still arriving? - What should happen to a record whose parent never arrives, to a second root, to a cycle, or to a record whose parent is a file? - Can two entries in the same directory share a name, and in what order should children be listed? ### Part 1 — Parse records and model the tree Parse each line into a typed record and design the node structure that stores the tree, with links from each parent to its children and from each child to its parent. For this part, assume every parent's record comes before its children's. ```hint Ids versus objects Decide what you index nodes by while building, and what each node must hold so that walking down to children and walking up to the root are both cheap. ``` #### What This Part Should Cover - Record parsing and validation kept separate from tree building - A node design with parent and child links plus an index by id - Path construction and deterministic printing ### Part 2 — Children before parents in a stream Now records arrive one at a time and in any order: a child can arrive before its parent. Create the child when it arrives, and attach it to its parent once the parent shows up. ```hint Somewhere to wait A child that arrives early has to be remembered against something that does not exist yet. Decide what that something is, and when you check for anything left unresolved. ``` #### Clarifying Questions for this Part - Must queries work while some nodes are still waiting for their parents, and what should they return for such a node? #### What This Part Should Cover - A mechanism that holds early children and attaches them, with their subtrees, when the parent arrives, in time linear in the number of records - Detection of orphans, duplicate ids, cycles, extra roots and file parents, and when each is reported - Behavior of queries while the tree is still incomplete ### Part 3 — Wire it up and test it Write the driver that reads the sample input, feeds it to your class and prints the result, then write test cases and run them yourself. ```hint Test the order, not just the content The same records in a different order must produce the same tree. Think about which orderings are most likely to break your code. ``` #### What This Part Should Cover - A small driver that streams records into the class and reports errors with line numbers - Tests for in-order and shuffled input and for each malformed case - Output that makes a failing test easy to diagnose ### What a Strong Answer Covers - Pins down the record format, ordering guarantees and error policy before coding - A clear node model with an id index, parent and child links, and constant-time attachment - Correct handling of children that arrive before their parents, without losing any subtree - Explicit, reported handling of orphans, duplicates, cycles and invalid parents - Self-written integration code and tests, including permutations of the input order ### Follow-up Questions - The stream never ends. How do you decide that a waiting child is an orphan rather than early, and how much memory can waiting children take? - Records can now also move a node to another parent or delete it. What changes in your structure, and how do you stop a move from creating a cycle? - One directory has a very large number of children and is listed often. How do you store children so that listing in name order and looking up a child by name both stay fast? - How would you persist the tree so that a restart does not require replaying the whole stream?