Rule-based HTML compilation

Given an HTML with messed up tag nesting, output the correct and unambiguous version of the HTML.

Problem Statement

Given an array of JSON rules telling you different significance types (rules) for different parts of a correspondingly given text, write a JS function that styles the text with span tags with class attributes to reflect those rules. The rules can refer to overlapping parts of the text.

For example:

You may have the misspelled lol-speak sentence "I can has cheezburgers iz nice!" This string has a misspelled word and two possible sentences with bad grammar. When you request from a spell-checking service to examine this string, it returns you the result:

[ {
    type: 1,
    index: 10,
    length: 12
    type: 2,
    index: 0,
    length: 22
    type: 2,
    index: 10,
    length: 21

... where "type: 1" means "misspelling" and "type: 2" means "grammar error". Don't worry about how the spell-checker was implemented. Your pseudo-algorithm should correctly render the text with added HTML tags that have corresponding class attributes that lets a UI designer style those regions of text. For the above example, the correct output is:

<span class="rule-2">I can has <span class="rule-1">cheezburgers</span></span><span class="rule-2"> iz nice!</span>

Important: Take special care that you're rendering balanced HTML. An example of an incorrectly rendered output is literally placing the open and close tags where the indexes in JSON were indicated - the following is too easy, and wrong:

I can has cheezburgers iz nice!


The design of your correct algorithm should be explained. Although code would be a plus, it's not required in this case. But the right idea for the solution is what you're graded on.


Maarten from Google asked me this question for 45 minutes during my official 5 hour interview

Recommended reading

Amin Ariana
April 2011