Tag Validator

Tag Validator

What is this problem about?

The Tag Validator coding problem is a rigorous string parsing challenge. You are given a string representing a snippet of code, and you need to determine if the tags used in it are valid. The rules involve checking for balanced tags (<TAG_NAME>content</TAG_NAME>), handling CDATA sections (<![CDATA[...]]>), ensuring tag names are uppercase and of limited length (1-9 characters), and making sure the entire string is wrapped in a single root tag.

Why is this asked in interviews?

Microsoft uses this "Hard" difficulty problem to evaluate a candidate's ability to handle complex state machines and string parsing logic. It tests your attention to detail regarding boundary conditions and your ability to use a stack for balance checking. It’s essentially a miniature version of a compiler's lexer or an XML/HTML parser, requiring precise character-by-character analysis.

Algorithmic pattern used

The primary algorithmic pattern is the Stack and String Parsing pattern.

1. Use a stack to keep track of open tags. When an opening tag is found, push its name onto the stack. When a closing tag is found, check if it matches the top of the stack and pop it.
2. Carefully parse the string index by index. If you encounter <![CDATA[, you must skip everything until you find the closing ]]>.
3. If you encounter a tag <...>, distinguish between a start tag and an end tag.
4. Throughout the process, check for rules like tag name length, case, and nesting.
5. A crucial rule: once the root tag is closed, no more characters (including tags) should appear outside of it.

Example explanation

Input: <DIV>This is <![CDATA[<div>]]> </DIV>

1. Start: <DIV>. Stack: ["DIV"].
2. Content: "This is ".
3. CDATA: <![CDATA[<div>]]>. The parser identifies the CDATA start, skips "<div>", and finds "]]>".
4. Content: " ".
5. End tag: </DIV>. Matches stack top "DIV". Pop. Stack: [].
6. End of string reached. Result: True. If we had <DIV>...</DIV><TAG>...</TAG>, it would be False because there is a tag outside the root <DIV>.

Common mistakes candidates make

The most common mistake is failing to correctly handle the "no content outside root tag" rule. Another frequent error is incorrect parsing of the CDATA section—for instance, thinking that a ]]> inside the CDATA content (if not escaped correctly) could end the section prematurely. Many candidates also forget to validate the tag name's characters (must be uppercase English letters).

Interview preparation tip

To tackle the Tag Validator interview question, practice building small parsers using the Stack interview pattern. It’s helpful to write helper functions for different parsing states (e.g., parseTagName, parseCdata). This keeps your main loop clean and makes it easier to debug the complex rules of the problem.