Pin Down a Vague HTML Parser Prompt, Build the Element Tree, and Query It with DFS

You are asked to write an HTML parser. The prompt is deliberately vague: it does not define the input, the output, or which edge cases matter. Part of the exercise is turning it into a precise contract: ask for concrete examples early, then write down the input, the output and the edge cases before you start coding. Once the contract is settled, implement a parser that captures how the elements of the document nest, and use the parsed structure to answer a question about the document. ### Constraints and Clarifications - Which question about the document the interviewer asked is not known. For practice, assume that once you ask, the interviewer wants this query: given a tag name, return the text content of every element with that tag, in document order, where an element's text content is all the text inside it, concatenated. - Assume the input is one HTML string that fits in memory. ### Clarifying Questions - Can you show a concrete input and the exact output you expect for it? - Is the input guaranteed to be well formed, with every opened element closed in the right order, or must the parser recover from missing or mismatched end tags? - Which constructs can appear: attributes (quoted, unquoted or without a value), self-closing tags, void elements such as `br` and `img` that never have an end tag, comments, a doctype, character entities such as `&amp;`? - Are tag names case-insensitive, and should whitespace between tags be kept? - Can `script` or `style` elements appear, whose content must not be parsed as markup? ### Part 1 — Parse the input into a tree Implement a parser that turns the input string into a tree: one node per element, holding its tag name, its attributes and its children in document order, with text stored in leaf nodes. Apply the edge-case policy you agreed on. A typical input: ```html <div class="card"><p>Hello <b>world</b></p><br><p>Fish &amp; chips</p></div> ``` ```hint What is still open At any point in the input, think about which elements have been opened but not yet closed, and in which order they must close. ``` ```hint Not every tag closes Decide how a void element, a self-closing tag and an end tag with no matching start tag each change the set of open elements. ``` #### What This Part Should Cover - A node model for elements, attributes and text - A single left-to-right pass that attaches every node to the correct parent - The agreed handling of void elements, self-closing tags, comments, entities and malformed nesting - Running time that is linear in the input length ### Part 2 — Answer the query with a depth-first traversal Using the tree from Part 1, implement the practice query. For the input above, the query for `p` returns `["Hello world", "Fish & chips"]`, and the query for `b` returns `["world"]`. ```hint Order and depth Make sure children are visited in document order, and consider how deep the nesting can get before choosing between recursion and an explicit stack. ``` #### What This Part Should Cover - A depth-first traversal that visits nodes in document order - Collecting the text of a subtree, including text inside nested elements - Recursion depth on deeply nested input, and the cost of a query when matching elements nest inside each other ### What a Strong Answer Covers - Concrete examples and a written contract (input, output, edge cases) before any code - A tree model that matches the nesting of the document, built in one pass - Deliberate, stated choices for malformed input, void elements and entities rather than accidents of the implementation - A correct, order-preserving traversal with stated complexity - Tests or a walkthrough on the agreed examples, including the edge cases ### Follow-up Questions - How would you support simple CSS-style selectors, such as `div p` or `p.note`, on the same tree? - The input is a multi-gigabyte HTML file and you only need the text of the `p` elements. How would you avoid building the whole tree? - Real HTML lets authors omit some end tags; for example, a new `p` closes an open `p`. How would your parser handle that? - How would you test the parser?