Validate Nesting in a Rich-Text Comment

Updated · By

Scan the comment for tags from left to right. Push each opening tag with its index onto a stack. A closing tag must match the tag on top; if the stack is empty or holds a different tag, the closing tag's index is the error. A tag still open at the end fails at the earliest unclosed one. O(n) time.

mediumPattern: StackFrom Devana's Meta question set

Problem

Comments support formatting tags for bold, italic, links and mentions, and the tags can nest. Before rendering, you have to check that they are properly nested and, when they are not, report where the structure first breaks so the editor can highlight it.

Write validate_markup(comment), returning (True, None) when the markup is valid and (False, index) otherwise, where index is the 0-based position at which the offending tag begins.

def validate_markup(comment: str) -> tuple[bool, int | None]:

This is one of Devana's own questions, written in the style of Meta's interviews. It is not a question leaked from Meta, and Devana is not affiliated with Meta.

Constraints

  • The tags are <b>, <i>, <a> and <mention>, with closing forms such as </b>. Anything else, including a lone <, is plain text.
  • A closing tag must match the innermost open tag, not merely some open tag.
  • A closing tag that does not match fails at its own index. A tag that is never closed fails at the index of the earliest tag left open.
  • Text with no tags is valid.

Examples

Example 1

Input:  "<b>hello <i>there</i></b>"
Output: (True, None)

Italic opens and closes inside bold.

Example 2

Input:  "<b>hello <i>there</b></i>"
Output: (False, 17)

At index 17, </b> arrives while <i> is the innermost open tag. Both tags are closed eventually, but they interleave instead of nesting.

Hints

Open one at a time, and try the problem again after each.

Hint 1

The tag that has to close next is always the one opened most recently and not yet closed. Which data structure gives you the most recent item?

Hint 2

Push the tag name together with its index, so you can report where an unclosed tag started.

Hint 3

When the scan ends, the stack may not be empty. Which of the leftover tags is the first place the structure breaks?

Approach: from brute force to optimal

Brute force: remove innermost pairs until nothing changes

Find an opening tag immediately followed by its matching closing tag, delete both, and repeat. Valid markup reduces to plain text. It works, but every pass rescans the string, and recovering the original error position is awkward.

Complexity: O(n²) time in the worst case

One pass with a stack

Find the tags with a regular expression. An opening tag pushes (name, index). A closing tag pops if the top has the same name; otherwise it is the error. At the end, a non-empty stack means the bottom entry, the earliest tag still open, is the error.

Counting opens and closes per tag is not enough: <b><i></b></i> balances every count and is still wrong. Only the order of the stack catches it.

Complexity: O(n) time, O(d) space for nesting depth d

How to say it in the interview

State the invariant before the code: "a closing tag must match the most recently opened tag that is still open, so I keep open tags on a stack." Then say both error positions out loud, because the two kinds of failure report different indexes and interviewers check that you noticed.

Solution

Python

import re

TAG = re.compile(r"<(/?)(b|i|a|mention)>")

def validate_markup(comment):
    open_tags = []                          # (name, index), innermost last
    for m in TAG.finditer(comment):
        closing, name = m.group(1) == "/", m.group(2)
        if not closing:
            open_tags.append((name, m.start()))
        elif open_tags and open_tags[-1][0] == name:
            open_tags.pop()
        else:
            return (False, m.start())       # closes something that is not innermost
    if open_tags:
        return (False, open_tags[0][1])     # the earliest tag never closed
    return (True, None)

JavaScript

const TAG = /<(\/?)(b|i|a|mention)>/g;

function validateMarkup(comment) {
  const openTags = []; // [name, index], innermost last
  for (const m of comment.matchAll(TAG)) {
    const closing = m[1] === "/";
    const name = m[2];
    if (!closing) {
      openTags.push([name, m.index]);
    } else if (openTags.length > 0 && openTags[openTags.length - 1][0] === name) {
      openTags.pop();
    } else {
      return [false, m.index]; // closes something that is not innermost
    }
  }
  if (openTags.length > 0) return [false, openTags[0][1]]; // the earliest tag never closed
  return [true, null];
}

Both versions are tested against the same cases, including every example on this page.

  • The regular expression recognizes only the four tags, so a < b in plain text is never mistaken for markup.
  • <a> here has no attributes. Real links carry an href, which needs a pattern that allows attributes on opening tags.
  • matchAll requires the global flag and works on a copy of the regular expression, so sharing TAG between calls is safe.

Follow-up questions

How do you handle self-closing tags like an inline image?

Treat them as complete on their own: recognize them in the tokenizer and never push them. They can then appear anywhere, including between an opening and a closing tag.

How would you auto-repair rather than reject?

On a mismatched close, close the tags above the match and reopen them after it, which is roughly what browsers do; at the end, close everything still open. Show the repair to the user rather than applying it silently.

What if user text legitimately contains angle brackets?

Escape user text before it is stored, so only the editor can produce real tags, and validate the stored form. A <b> typed by the user then arrives as &lt;b&gt; and is not a tag.

How do you report every error, not just the first?

Record each error and recover instead of returning: skip a stray close, and on a mismatch pop down to the matching tag if one exists. The first error is still the most reliable, since later ones can be consequences of it.

Common mistakes

  • Counting opens and closes per tag, which accepts interleaved tags.
  • Accepting a closing tag that matches some open tag deeper in the stack.
  • Forgetting to check the stack at the end, so <b>unclosed passes.
  • Treating every < as the start of a tag.

Practice it in a mock interview

Reading a solution and explaining one under questioning are different skills. The button below starts this problem as a voice mock interview with Josh, Devana's AI interviewer, with an editor that runs your code.

Practice this problem in a mock interview

Practice this problem out loud

Josh, Devana's AI interviewer, runs this exact problem as a voice mock interview, asks follow-ups like the ones above, and scores you out of 100. The Free plan has 3 interviews a month, no card needed.

Practice this problem in a mock interview