Parse Markdown Links Without Regex
Company: Samsara
Role: Software Engineer
Category: Coding & Algorithms
Difficulty: medium
Interview Round: Technical Screen
Implement a function that converts simplified link syntax [text]("url") into an HTML anchor tag <a href="url">text</a> across an entire input string. Constraints: do not use regular expressions; rely only on basic string operations (e.g., indexOf, split, substring). Requirements:
- Support multiple links per line and across lines.
- Preserve all non-link text and punctuation.
- Leave malformed patterns (e.g., missing brackets or quotes) unchanged.
- If brackets appear inside the label, treat the innermost valid [ ... ] preceding a (" ... ") as the link label.
- Treat escaped brackets or quotes (preceded by a backslash \) as literals.
- Analyze the time and space complexity of your approach.
- Provide unit tests for typical, edge, and large inputs.
Examples:
Input: "Click [Go to Link]("whateverlink.com") now."
Output: "Click <a href=\"whateverlink.com\">Go to Link</a> now."
Input: "[A]("u1") and [B]("u2")"
Output: "<a href=\"u1\">A</a> and <a href=\"u2\">B</a>"
Input: "Broken [label](url) stays"
Output: "Broken [label](url) stays"
Quick Answer: This question evaluates proficiency in string parsing, tokenization, escape-sequence handling, and input validation required to convert simplified Markdown-style link syntax into HTML anchors without using regular expressions.
Implement a function that scans a string and converts every valid simplified markdown link of the form `[label]("url")` into an HTML anchor tag `<a href="url">label</a>`. You must not use regular expressions; rely only on basic string operations and manual parsing. Support multiple links anywhere in the input, including across newline characters. Preserve all non-link text exactly. If a pattern is malformed (for example, missing brackets, quotes, or the closing parenthesis), leave it unchanged. A bracket or quote preceded by an odd number of backslashes is escaped and must be treated as a literal. Resolve nested brackets with normal stack matching, so the `]` before a candidate URL matches its corresponding unescaped `[` after any inner bracket pairs are closed.
Constraints
- 0 <= len(text) <= 200000
- Do not use regular expressions.
- Only exact unescaped patterns of the form `[label]("url")` should be converted; malformed patterns must remain unchanged.
Examples
Input: ('Click [Go to Link]("whateverlink.com") now.',)
Expected Output: 'Click <a href="whateverlink.com">Go to Link</a> now.'
Explanation: A well-formed link is converted and surrounding text is preserved.
Input: ('[A]("u1") and [B]("u2")',)
Expected Output: '<a href="u1">A</a> and <a href="u2">B</a>'
Explanation: The parser must handle multiple valid links in the same string.
Hints
- Use a stack to track positions of unescaped `[` characters. Each unescaped `]` closes the most recent unmatched `[`.
- To keep the parser linear, precompute which characters are escaped and where the next unescaped `"` appears.