HardCoding

Tag Validator

Asked at

Microsoft

1Give yourself 5 minutes

2Answer out loud, not in your head

3Then compare with the answer below

Stuck? Show a way to structure it+

01Require the document to begin with an opening tag.
02Scan tags and CDATA blocks with index bounds checks.
03Push valid opening names and match every closing name to stack top.
04Reject trailing text after the root closes and accept only an empty final stack.

Reference answer

Tag Validator is a grammar-validation problem. Scan with an index and maintain a stack of open tag names. Opening and closing tag names must follow the stated format, typically one to nine uppercase letters; an opening tag pushes its name, while a closing tag must equal the stack top before popping. When a CDATA section begins, skip through the next exact ]]> delimiter, but allow it only inside an already open tag. Enforce a single root: the input must start with an opening tag, and once the stack becomes empty no further characters are legal. Carefully check delimiters and end indices before slicing. Each character is scanned a bounded number of times, giving O(n) time and O(n) stack space. Explain that ordinary text is valid only while inside an open root. Empty tags, mismatched close order, malformed names, and unclosed CDATA are decisive edge cases.

Then expect these follow-ups

Why is a stack necessary rather than a set?
Tests: nesting order
How would you report the first syntax error?
Tests: parser diagnostics

Hiring now

Get the Microsoft interview, not just the prep

landed applies to roles like these for you, on each company’s own site, with answers written for the role.

Get 5x interviews10 free auto-applies. No card.

Or practice this question first

Next question