Implement Markdown-to-HTML parser
Company: Samsara
Role: Software Engineer
Category: Coding & Algorithms
Difficulty: medium
Interview Round: Technical Screen
Implement a function that converts a plain-text string into HTML supporting only these features:
(
1) Paragraphs: two or more consecutive newline characters separate paragraphs; wrap each paragraph in <p>...</p>.
(
2) Soft line breaks: a single newline inside a paragraph becomes <br/>.
(
3) Blockquotes: one or more consecutive lines that each begin with "> " (greater-than followed by a space) form a single <blockquote>...</blockquote>; within the blockquote, strip the leading "> " from each quoted line; preserve soft line breaks as <br/>; blockquotes cannot span paragraphs.
(
4) Strikethrough: text enclosed by a pair of tildes, e.g., ~~like this~~, becomes <del>like this</del>.
(
5) Formatting commands do not cross paragraphs; if a strikethrough is opened in one paragraph, it must close in the same paragraph or be treated as literal text. The output must be valid HTML; exact whitespace and self-closing syntax need not match any reference output. Provide the algorithm, discuss how you will tokenize/scan the input (single pass vs. multi-pass), specify time and space complexity in terms of input length n, and describe how you will handle edge cases such as trailing spaces, empty paragraphs, consecutive blockquote groups, malformed or unmatched tildes, and lines that mix quoted and non-quoted text. Include a few test cases, for example: "This is a paragraph with a
soft line break.
> Some quoted text
> continues here
This has a ~~strikethrough~~ word."
Quick Answer: This question evaluates parsing and string-processing skills, including tokenization, stateful scanning, inline versus block-level markup handling, edge-case management (e.g., unmatched delimiters, trailing spaces, empty paragraphs) and reasoning about time and space complexity.
Implement `solution(text)` that converts a plain-text string into HTML using only a limited Markdown subset. Normalize line endings first. A blank line is any line whose trimmed contents are empty, and blank lines end the current block. A maximal consecutive run of lines starting with `> ` becomes one `<blockquote>...</blockquote>` block; remove the leading `> ` from each quoted line. A maximal consecutive run of other non-blank lines becomes one `<p>...</p>` block. Inside any block, line breaks between its lines become `<br/>`. Inline strikethrough uses pairs of `~~` inside a single block; pair markers from left to right, convert the enclosed text to `<del>...</del>`, and if the last opening `~~` in a block has no closing `~~` in that same block, keep it as literal text. Escape `&`, `<`, and `>` in normal text so the output is valid HTML. A line beginning with `>` but not the exact prefix `> ` is normal paragraph text. Return all rendered blocks concatenated in order with no extra separators.
Constraints
- 0 <= len(text) <= 200000
- The parser only needs to support paragraphs, soft line breaks, blockquotes, and strikethrough as described.
- A blockquote marker is recognized only when a line starts with the exact prefix `> `.
- Strikethrough markers `~~` are paired left to right within the same block only; unmatched final `~~` is treated as literal text.
Examples
Input: ("This is a paragraph with a\nsoft line break.\n\n> Some quoted text\n> continues here\n\nThis has a ~~strikethrough~~ word.",)
Expected Output: "<p>This is a paragraph with a<br/>soft line break.</p><blockquote>Some quoted text<br/>continues here</blockquote><p>This has a <del>strikethrough</del> word.</p>"
Explanation: Two paragraph lines become one `<p>` with `<br/>`, the quoted lines become one `<blockquote>`, and the paired `~~` becomes `<del>`.
Input: ("5 < 6 & 7 > 3\n>not a quote\n~~open only",)
Expected Output: "<p>5 < 6 & 7 > 3<br/>>not a quote<br/>~~open only</p>"
Explanation: The second line is not a blockquote because it starts with `>` but not `> `. The final unmatched `~~` is kept literally.
Hints
- Scan the input line by line. Blank lines end the current block, and switching between quoted and non-quoted lines also starts a new block.
- Handle inline parsing one block at a time. A simple state machine for whether you are currently inside `~~...~~` avoids quadratic rescanning.