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 Databricks.

What role is this question designed for?

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

Partition a Target String by Source Substrings

Company: Databricks

Role: Software Engineer

Category: Coding & Algorithms

Difficulty: medium

Interview Round: Onsite

You are given two strings: - `target`: the string that must be represented. - `source`: the string whose substrings may be used. Return a partition of `target` into the minimum possible number of contiguous substrings, where each part must exactly match some contiguous substring of `source`. For every part, return the `[start, end]` indices of the matching substring in `source`. Use 0-based inclusive indices. If multiple minimum-size partitions exist, return any one of them. If `target` cannot be represented, return an empty list or an error value, as agreed with the interviewer. Example: ```text target = "abcdbcd" source = "sabcd" ``` One valid minimum partition is: ```text [[1, 3], [4, 4], [2, 4]] ``` because: ```text source[1..3] = "abc" source[4..4] = "d" source[2..4] = "bcd" ``` and their concatenation is: ```text "abc" + "d" + "bcd" = "abcdbcd" ``` Follow-up: after deleting one character from `target`, return a new minimum partition for the updated target string. Discuss how to recompute or update the result efficiently.

Quick Answer: This question evaluates understanding of string algorithms and optimal partitioning, specifically substring matching and minimizing the number of contiguous segments extracted from a source string.

Part 1: Minimum Partition of Target by Source Substrings

Given two strings target and source, partition target into the minimum number of non-empty contiguous pieces such that every piece appears somewhere as a contiguous substring of source. For each piece, return one matching [start, end] pair in source using 0-based inclusive indices. Concatenating the chosen source substrings in order must reconstruct target exactly. If target is empty, return []. If no partition is possible, return []. If multiple minimum partitions exist, any one is acceptable.

Constraints

0 <= len(target), len(source) <= 2000
target and source consist of lowercase English letters
Indices in the answer must be 0-based and inclusive
Return any one optimal partition if multiple exist

Examples

Input: ("abcdbcd", "sabcd")

Expected Output: [[1, 4], [2, 4]]

Explanation: source[1:5] is abcd and source[2:5] is bcd. Together they form abcdbcd using 2 pieces, which is minimum.

Input: ("cab", "zzcabx")

Expected Output: [[2, 4]]

Explanation: The whole target is already a substring of source.

Input: ("b", "abc")

Expected Output: [[1, 1]]

Explanation: Single-character target.

Input: ("", "abc")

Expected Output: []

Explanation: An empty target needs zero pieces.

Input: ("az", "abc")

Expected Output: []

Explanation: z does not appear in source, so no partition is possible.

Hints

Think about the longest common prefix between target[i:] and source[j:] for every pair of positions.
Once you know the maximum usable piece length from each target index, the problem becomes a minimum-jumps / shortest-path problem on positions 0..len(target).

Part 2: Minimum Partition After Deleting One Character

You are given target, source, and a 0-based index delete_index. First delete target[delete_index]. On the resulting string, compute a partition into the minimum number of non-empty contiguous pieces such that every piece appears as a contiguous substring of source. Return one matching [start, end] pair in source for each piece, using 0-based inclusive indices. If delete_index is invalid, return []. If the updated target is empty, return []. If no partition is possible, return []. If multiple minimum partitions exist, any one is acceptable.

Constraints

0 <= len(target), len(source) <= 2000
target and source consist of lowercase English letters
For a valid delete operation, 0 <= delete_index < len(target)
Indices in the answer must be 0-based and inclusive

Examples

Input: ("abcdbcd", "sabcd", 3)

Expected Output: [[1, 3], [2, 4]]

Explanation: Deleting index 3 removes d, so the new target is abcbcd. That can be formed as abc + bcd.

Input: ("xabc", "zzabc", 0)

Expected Output: [[2, 4]]

Explanation: After deleting x, the updated target is abc, which appears directly in source.

Input: ("q", "abc", 0)

Expected Output: []

Explanation: Deleting the only character leaves an empty target, which needs zero pieces.

Input: ("az", "bc", 0)

Expected Output: []

Explanation: After deletion the new target is z, which does not appear in source.

Input: ("abc", "abc", 3)

Expected Output: []

Explanation: delete_index is out of range, so return the agreed error value [].

Hints

After removing one character, the remaining task is the same core problem as Part 1 on a shorter target string.
If you already know how to compute the best partition for a target string, wrap that logic in a helper and call it on target[:delete_index] + target[delete_index+1:].

Quick Overview

This question evaluates understanding of string algorithms and optimal partitioning, specifically substring matching and minimizing the number of contiguous segments extracted from a source string.