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 Onsite rounds at Apple.

What role is this question designed for?

This question is commonly asked for Machine Learning Engineer candidates at Apple during technical interviews.

Wrap Matching Substrings in Bold Tags

Company: Apple

Role: Machine Learning Engineer

Category: Coding & Algorithms

Difficulty: medium

Interview Round: Onsite

During a machine learning engineer phone screen, the coding task was: You are given a string `text` and a list of strings `patterns`. Return a new string where every substring of `text` that matches any string in `patterns` is wrapped in HTML-style bold tags: `` and ``. Rules: - If two matched ranges overlap, they must be merged into one bold segment. - If two matched ranges are adjacent, they should also be merged into one bold segment. - The output should contain the minimum number of bold tag pairs needed to cover all matches. Example 1: - Input: `text = "abcxyz123"`, `patterns = ["abc", "123"]` - Output: `"abcxyz123"` Example 2: - Input: `text = "aaabbcc"`, `patterns = ["aaa", "aab", "bc"]` - Output: `"aaabbcc"` Implement a function that returns the formatted string.

Quick Answer: This question evaluates string manipulation, pattern matching, and interval-merging competency within algorithmic problem-solving for text processing and HTML-like formatting.

You are given a string `text` and a list of strings `patterns`. Return a new string where every occurrence of any pattern in `text` is wrapped in HTML-style bold tags: `` and ``. If two matched ranges overlap, they must be merged into one bold segment. If two matched ranges are adjacent, they should also be merged. The final output must use the minimum number of bold tag pairs needed to cover all matches.

Constraints

0 <= len(text) <= 1000
0 <= len(patterns) <= 100
1 <= len(patterns[i]) <= 100 for each pattern that exists
Both `text` and `patterns[i]` consist of lowercase English letters

Examples

Input: ("abcxyz123", ["abc", "123"])

Expected Output: "abcxyz123"

Explanation: The matches are `abc` and `123`, and they are separate, so they become two bold segments.

Input: ("aaabbcc", ["aaa", "aab", "bc"])

Expected Output: "aaabbcc"

Explanation: `aaa` and `aab` overlap near the start, and `bc` touches that merged region, so all matched characters from index 0 to 5 are wrapped together.

Input: ("ababcd", ["ab", "abc", "bcd"])

Expected Output: "ababcd"

Explanation: The matches overlap and connect across the whole string, so a single pair of tags wraps everything.

Input: ("hello", [])

Expected Output: "hello"

Explanation: With no patterns, nothing is bolded.

Input: ("", ["a", "bc"])

Expected Output: ""

Explanation: An empty text produces an empty result.

Input: ("a", ["a", "aa"])

Expected Output: "a"

Explanation: The single character matches `a`, so the whole string is bolded.

Input: ("abcdef", ["gh", "ij"])

Expected Output: "abcdef"

Explanation: None of the patterns appear in the text, so the output is unchanged.

Hints

Try marking which character positions belong to at least one matched pattern, then build the answer from those marks.
While scanning from left to right, keep track of the furthest end index of any pattern that starts at or before the current position.

Quick Overview

This question evaluates string manipulation, pattern matching, and interval-merging competency within algorithmic problem-solving for text processing and HTML-like formatting.