HTML Entity Parser

HTML Entity Parser

What is this problem about?

The HTML Entity Parser interview question asks you to implement a software component that replaces specific HTML special entities with their corresponding characters. The entities to handle are:

• " $o$ "
• ' $o$ '
• & $o$ &
• > $o$ >
• < $o$ <
• ⁄ $o$ / The parser should process the string from left to right and perform the replacements.

Why is this asked in interviews?

This "Medium" difficulty problem is common at Meta and Oracle to test a candidate's string parsing and pattern matching skills. It evaluates how you handle overlapping or nested patterns and whether you can choose an efficient replacement strategy. It’s a practical task that mirrors the logic used in web browsers and templating engines to sanitize or display user-generated content.

Algorithmic pattern used

The problem uses a Hash Table for mapping and String Simulation.

1. Store the entity-to-character mapping in a Hash Map.
2. Iterate through the string. When you encounter an ampersand (&), look ahead to see if the following characters match any of the keys in your map.
3. If a match is found, append the corresponding character to the result and skip the length of the entity.
4. If no match is found, append the character as is. Important: You must be careful with the order of replacements if using built-in replace functions (specifically & should often be replaced last to avoid double-parsing), though a single-pass character scan avoids this issue naturally.

Example explanation

Input: "& is an HTML entity but &ambit; is not."

1. Encounter &. Match found in map. Replace with &.
2. Encounter &ambit;. No match found in map (even though it starts with &). Append &ambit; as is. Result: "& is an HTML entity but &ambit; is not."

Common mistakes candidates make

• Double Replacement: Replacing & first, which might turn > into >, which then gets replaced again by >. The problem usually requires a single pass.
• Inefficient Search: Using string.replace() multiple times for each entity, which results in multiple scans of the entire string ($O(K imes N)$).
• Look-ahead Errors: Failing to check the boundaries of the string when looking for the closing semicolon (;) of an entity.

Interview preparation tip

Practice "One-Pass" string processing. Instead of using library functions that re-scan the string, use a while loop or a pointer to build the result string manually. This demonstrates an understanding of time complexity ($O(N)$) and memory management.