Implement Markdown-to-HTML parser | Samsara Coding Question

Quick Overview

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 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 .... ( 2) Soft line breaks: a single newline inside a paragraph becomes . ( 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 ; 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."

Overview: 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 `...` block. Inside any block, line breaks between its lines become ` `. 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: "This is a paragraph with a soft line break.<blockquote>Some quoted text continues here</blockquote>This has a <del>strikethrough</del> word."

Explanation: Two paragraph lines become one `` with ` `, 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: "5 < 6 & 7 > 3 >not a quote ~~open only"

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.

Approach

The parser runs as a small two-stage pipeline: split the text into blocks, then render inline markup inside each block.

1. Normalize. \r\n and \r are collapsed to \n first, so the rest of the code only ever sees \n.

2. Group lines into blocks. Iterating over text.split('\n'), the code keeps a current_type and current_lines accumulator:

A line whose .strip() is empty is blank and calls flush() to end the current block.
Otherwise the line is typed blockquote if it starts with the exact prefix > (and the > is stripped via line[2:]), else paragraph. A line like >not a quote lacks the trailing space, so it stays a paragraph.
Consecutive lines of the same type accumulate; a type change flushes the old block and starts a new one. This makes each maximal same-type run exactly one block.

3. flush(). Joins the block's lines with \n, renders them, and wraps in <blockquote> or .

4. Inline rendering (render_inline). It split('~~') into segments. With k delimiters, it forms k//2 pairs left-to-right: each pair wraps its enclosed (escaped) segment in <del>...</del>, with plain escaped text interleaved between pairs. If k is odd, the final unmatched ~~ is emitted literally followed by its trailing text.

5. Escaping. escape_text escapes &, <, > and turns the intra-block \n into   — so soft line breaks (and multi-line <del> spans) render correctly. Because escaping is applied per ~~-segment, the ~~ markers are never affected. Blocks are concatenated with no separators.

Time complexity:

O(n)

Space complexity:

O(n)