How do I practice coding and algorithm questions?

Use PracHub's coding console to write, test, and debug your solutions in Python or JavaScript. View hints, test against sample inputs, and compare with official solutions.

What difficulty level is this coding question?

This is a Medium difficulty Coding & Algorithms question, commonly asked during Technical Screen rounds at Samsara.

What role is this question designed for?

This question is commonly asked for Software Engineer candidates at Samsara during technical interviews.

Parse Markdown Links Without Regex | Samsara Coding Question

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.

Input: ('Broken [label](url) stays',)

Expected Output: 'Broken [label](url) stays'

Explanation: The URL is not wrapped in double quotes, so the pattern is malformed and must stay unchanged.

Input: ('Line 1: [A]("u1")\nLine 2: [B]("u2").',)

Expected Output: 'Line 1: <a href="u1">A</a>\nLine 2: <a href="u2">B</a>.'

Explanation: Links should be parsed across newline characters as well.

Input: ('Ignore \\[not a link]("u") but parse [yes]("ok")',)

Expected Output: 'Ignore \\[not a link]("u") but parse <a href="ok">yes</a>'

Explanation: The escaped `[` is literal, so that pattern is ignored, while the later valid link is converted.

Input: ('[A]("he said \\\"hi\\\"")',)

Expected Output: '<a href="he said \\\"hi\\\"">A</a>'

Explanation: Escaped quotes inside the URL are treated as literal characters, not as the closing quote.

Input: ('[a [b] c]("u")',)

Expected Output: '<a href="u">a [b] c</a>'

Explanation: Nested brackets inside the label are handled with stack matching, so the outer pair becomes the link label.

Input: ('',)

Expected Output: ''

Explanation: An empty input should return an empty output.

Input: ('[A]("u)',)

Expected Output: '[A]("u)'

Explanation: The closing quote and parenthesis are missing, so the malformed pattern remains unchanged.

Input: ('Start [L1]("u1"), [L2]("u2"), [L3]("u3"), [L4]("u4"), [L5]("u5"), [L6]("u6"), [L7]("u7"), [L8]("u8"), [L9]("u9"), [L10]("u10") end.',)

Expected Output: 'Start <a href="u1">L1</a>, <a href="u2">L2</a>, <a href="u3">L3</a>, <a href="u4">L4</a>, <a href="u5">L5</a>, <a href="u6">L6</a>, <a href="u7">L7</a>, <a href="u8">L8</a>, <a href="u9">L9</a>, <a href="u10">L10</a> end.'

Explanation: A longer input with many replacements checks that the parser handles large strings efficiently.

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.

Quick Overview

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.