Parse Markdown Links Without Regex

Q: Parse Markdown Links Without Regex

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.

Q: 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.

Q: What difficulty level is this coding question?

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

Q: What role is this question designed for?

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

Question

Implement a function that converts simplified link syntax [text]("url") into an HTML anchor tag text 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 Go to Link now." Input: "[A]("u1") and [B]("u2")" Output: "A and B" Input: "Broken [label](url) stays" Output: "Broken [label](url) stays"

PracHub · Accepted Answer

def solution(text): n = len(text) if n == 0: return "" escaped = [False] * n slash_run = 0 for i, ch in enumerate(text): if ch == '\': slash_run += 1 else: escaped[i] = (slash_run % 2 == 1) slash_run = 0 next_quote = [-1] * (n + 1) next_pos = -1 for i in range(n - 1, -1, -1): if text[i] == '"' and not escaped[i]: next_pos = i next_quote[i] = next_pos result = [] last_emit = 0 stack = [] i = 0 while i < n: ch = text[i] if ch == '[' and not escaped[i]: stack.append(i) elif ch == ']' and not escaped[i] and stack: label_start = stack.pop() if i + 2 < n and text[i + 1] == '(' and text[i + 2] == '"': end_quote = next_quote[i + 3] if i + 3 <= n else -1 if end_quote != -1 and end_quote + 1 < n and text[end_quote + 1] == ')': result.append(text[last_emit:label_start]) label = text[label_start + 1:i] url = text[i + 3:end_quote] result.append(f'{label}') last_emit = end_quote + 2 stack.clear() i = end_quote + 1 i += 1 result.append(text[last_emit:]) return ''.join(result)

Quick Overview

Solution

Hints