0

Reconstruct a string from chained segments

by Frontier Interview· 1 day ago· ⑂ 0 remixes

Question: Reconstruct a string from chained segments

Companies: Microsoft AI, Microsoft

Difficulty: Medium

Problem statement

A log-shipping service splits a long message into fragments and sends them out of order. Each fragment is a triple [start_id, end_id, payload]: it covers the stretch from marker start_id to marker end_id and carries the text payload.

Together the fragments form one directed chain: the end_id of one fragment is the start_id of the next. No two fragments share a start_id, and no two share an end_id. The same id can still be one fragment's end_id and another fragment's start_id.

Implement reconstruct(segments: List[List[str]]) -> str. It returns the payloads concatenated in chain order, from the first fragment to the last.

If the input is not one chain, raise an error. That covers a cycle, more than one chain, or a repeated start or end id.

Constraints

  • 0 <= len(segments) <= 10^5
  • Ids are non-empty strings. Payloads may be empty.
  • Aim for O(n) time, plus the length of the output.

Example 1

segments = [["p3", "p4", "fox"], ["p1", "p2", "the "], ["p2", "p3", "quick "]]
output: "the quick fox"

p1 is never an end id, so the chain starts there: p1 -> p2 -> p3 -> p4.

Example 2

segments = [["m", "n", "ab"], ["n", "m", "cd"]]
output: error

Every id is both a start and an end, so there is no first fragment. The segments form a cycle.

Expect follow-ups: several independent chains, ids that the path passes through more than once, fragments that can be read in either direction, and fragments that arrive as a stream.

Reconstructed from the reported question; details may differ from what interviewers ask.

Approach

Treat each segment as a directed edge start_id -> end_id that carries a payload. Because start ids are unique and end ids are unique, every id has at most one outgoing segment and at most one incoming segment. The segments therefore form a linked list, and the job is to find its head and walk it.

Brute force. Pick each segment and check whether any other segment ends at its start. That finds the head in O(n^2). Then, at each step, scan all segments for the one whose start equals the current end. That is O(n^2) again. It is correct and worth saying out loud, but a hash map removes both scans.

Linear method.

  1. Build by_start: start_id -> segment and a set ends of all end ids. While building, reject a repeated start or a repeated end, because the input promise is broken.
  2. The head is the only start id that is not in ends. If there are zero heads, the segments form a cycle. If there are two or more, they form more than one chain. Both are errors.
  3. From the head, follow by_start[cur], append its payload, and move to its end id. Stop when the current id has no outgoing segment.
  4. If the walk used fewer than n segments, the rest form a detached cycle (for example x -> y -> x). That cycle does not create a second head, so this count check is the only way to catch it.

Collect the payloads in a list and join once at the end. Repeated += on strings can cost quadratic time.

Invariants.

  • Each id has in-degree and out-degree at most 1, so the walk from the head never revisits an id and cannot loop.
  • After k steps, parts holds the payloads of the first k chain segments, in order.
  • A valid input has exactly one id with in-degree 0 and out-degree 1 (the head), and exactly one id with in-degree 1 and out-degree 0 (the tail).

Empty payloads are fine: they still link the chain and contribute nothing to the result.

Code

from collections import defaultdict
from typing import Dict, List, Sequence, Tuple

Segment = Sequence[str]  # [start_id, end_id, payload]


def reconstruct(segments: List[Segment]) -> str:
    """Join payloads along the single chain. O(n) time beyond the output."""
    if not segments:
        return ""
    by_start: Dict[str, Segment] = {}
    ends = set()
    for seg in segments:
        start, end, _ = seg
        if start in by_start:
            raise ValueError(f"duplicate start id {start!r}")
        if end in ends:
            raise ValueError(f"duplicate end id {end!r}")
        by_start[start] = seg
        ends.add(end)

    heads = [s for s in by_start if s not in ends]
    if len(heads) != 1:
        raise ValueError(f"expected one chain head, found {len(heads)}")

    parts: List[str] = []
    cur = heads[0]
    while cur in by_start:
        _, nxt, payload = by_start[cur]
        parts.append(payload)
        cur = nxt                               # unique ends: the walk cannot loop
    if len(parts) != len(segments):
        raise ValueError("segments do not form one chain (a detached cycle exists)")
    return "".join(parts)


def reconstruct_all(segments: List[Segment]) -> List[str]:
    """Follow-up: several disjoint chains. Returns one string per chain,
    ordered by head id; raises if any segment sits on a cycle."""
    by_start = {seg[0]: seg for seg in segments}
    ends = {seg[1] for seg in segments}
    out: List[str] = []
    used = 0
    for head in sorted(s for s in by_start if s not in ends):
        parts, cur = [], head
        while cur in by_start:
            _, cur, payload = by_start[cur]
            parts.append(payload)
        used += len(parts)
        out.append("".join(parts))
    if used != len(segments):
        raise ValueError("some segments form a cycle")
    return out


def reconstruct_eulerian(segments: List[Segment]) -> str:
    """Follow-up: ids may repeat (a node is entered and left several times).
    Use every segment exactly once: Hierholzer's algorithm, O(n log n)
    because neighbours are sorted to make the answer deterministic."""
    if not segments:
        return ""
    out_edges: Dict[str, List[Tuple[str, str]]] = defaultdict(list)
    balance: Dict[str, int] = defaultdict(int)
    for start, end, payload in segments:
        out_edges[start].append((end, payload))
        balance[start] += 1
        balance[end] -= 1
    for node in out_edges:                      # pop() takes the smallest last
        out_edges[node].sort(reverse=True)
    starts = [v for v, b in balance.items() if b == 1]
    if len(starts) > 1 or any(abs(b) > 1 for b in balance.values()):
        raise ValueError("no path uses every segment")
    begin = starts[0] if starts else min(out_edges)

    stack: List[Tuple[str, str]] = [(begin, "")]
    path: List[str] = []
    while stack:
        node, _ = stack[-1]
        if out_edges[node]:
            nxt, payload = out_edges[node].pop()
            stack.append((nxt, payload))
        else:
            path.append(stack.pop()[1])
    if len(path) != len(segments) + 1:
        raise ValueError("segments are not connected")
    return "".join(reversed(path))


if __name__ == "__main__":
    segs = [["c", "d", "lo"], ["a", "b", "he"], ["d", "e", "!"], ["b", "c", "l"]]
    assert reconstruct(segs) == "hello!"
    assert reconstruct([]) == ""
    assert reconstruct([["x", "y", "solo"]]) == "solo"
    assert reconstruct([["x", "y", ""], ["y", "z", "ok"]]) == "ok"
    for bad in (
        [["a", "b", "1"], ["b", "a", "2"]],                       # pure cycle
        [["a", "b", "1"], ["c", "d", "2"]],                       # two chains
        [["a", "b", "1"], ["b", "c", "2"], ["x", "y", "3"], ["y", "x", "4"]],
        [["a", "b", "1"], ["a", "c", "2"]],                       # duplicate start
    ):
        try:
            reconstruct(bad)
            raise AssertionError(f"accepted {bad}")
        except ValueError:
            pass
    assert reconstruct_all([["c", "d", "2"], ["a", "b", "1"], ["d", "e", "3"]]) == ["1", "23"]
    assert reconstruct_eulerian(segs) == "hello!"
    # node b is visited twice: a->b->c->b->d
    assert reconstruct_eulerian([["b", "d", "4"], ["a", "b", "1"], ["c", "b", "3"], ["b", "c", "2"]]) == "1234"
    # long chain, shuffled
    import random
    n = 10000
    chain = [[f"n{i}", f"n{i+1}", chr(97 + i % 26)] for i in range(n)]
    want = "".join(s[2] for s in chain)
    random.shuffle(chain)
    assert reconstruct(chain) == want
    assert reconstruct_eulerian(chain) == want
    print("ok")

Complexity

Let n be the number of segments and L the total payload length.

  • reconstruct: O(n + L) time. Building the map and set is O(n), the walk is O(n), and the final join is O(L). Space is O(n) for the map and set, plus O(L) for the output.
  • reconstruct_all: O(n log n + L) time, because the heads are sorted to give a stable order. Without sorting it is O(n + L). Space is O(n + L).
  • reconstruct_eulerian: O(n log n + L) time, because each node's outgoing edges are sorted so the result is deterministic. Hierholzer itself is O(n). Space is O(n + L), and the explicit stack avoids Python's recursion limit on long chains.
  • Brute force: O(n^2) time, O(1) extra space.

Test cases

  • [["c","d","lo"], ["a","b","he"], ["d","e","!"], ["b","c","l"]] -> "hello!" (shuffled input).
  • [] -> "".
  • [["x","y","solo"]] -> "solo" (one segment is both head and tail).
  • [["x","y",""], ["y","z","ok"]] -> "ok" (an empty payload still links the chain).
  • [["a","b","1"], ["b","a","2"]] -> error: no head, the segments form a cycle.
  • [["a","b","1"], ["c","d","2"]] -> error: two heads, two chains.
  • [["a","b","1"], ["b","c","2"], ["x","y","3"], ["y","x","4"]] -> error: one head, but the walk uses only 2 of 4 segments (detached cycle).
  • [["a","b","1"], ["a","c","2"]] -> error: duplicate start id.
  • 10,000 segments n0 -> n1 -> ... -> n10000, shuffled -> the payloads in order. This checks that the solution is linear and does not recurse.
  • Follow-up, several chains: [["c","d","2"], ["a","b","1"], ["d","e","3"]] -> ["1", "23"].
  • Follow-up, repeated ids: [["b","d","4"], ["a","b","1"], ["c","b","3"], ["b","c","2"]] -> "1234" (path a -> b -> c -> b -> d).

Follow-ups

  1. Several independent chains. Drop the "exactly one head" rule. Walk from every head and return one string per chain (reconstruct_all). Fix an order for the output, such as sorted head id or input order of the head segment, and say which one you chose. Any segments the walks never reach lie on cycles, so report them.
  2. Ids may repeat (the path passes through an id more than once). A node can now have several outgoing segments, so a greedy walk can strand edges. The task becomes "use every edge exactly once": an Eulerian path. Check the degrees first. At most one node may have out - in = 1 (the start), at most one may have in - out = 1, and every other node must be balanced. Then run Hierholzer's algorithm (reconstruct_eulerian). If several orders are valid, the interviewer has to define a tie-break. Sorting the neighbours gives the lexicographically smallest edge order, which is the same idea as LeetCode's "Reconstruct Itinerary".
  3. Undirected segments. A segment may be read either way. If you read it backwards, its payload is reversed (in a DNA framing, reverse-complemented). Build an undirected multigraph. A valid answer needs zero or two odd-degree ids, and the path starts at an odd-degree id when there is one. Run Hierholzer on the undirected graph and mark each edge as used through a shared edge id, so it is not taken twice. Transform each payload according to the direction in which it was traversed.
  4. Streaming or out-of-order arrival. Segments arrive one at a time and the caller asks for the longest assembled prefix so far. Keep by_start and by_end, and merge each new segment with any neighbouring fragments on either side, as union-find does for intervals. Each fragment stores its head id, its tail id, and its pieces. Each arrival costs O(1) amortized, plus the cost of concatenating pieces when the string is read.
  5. Validation and error reporting at scale. On real pipeline data, return a structured report instead of raising: duplicate ids, orphans, cycles, and the longest valid chain. For data too large for memory, shard by id and do the linking as a join on end_id = start_id, then resolve chain order with pointer jumping (list ranking) in O(log n) rounds.

Interviewer expectations

Mid-level (L4)

  • Sees the input as a linked list and finds the head as the start id that is never an end id.
  • Writes a correct O(n) walk with a hash map and joins the payloads once, without quadratic string building.
  • Handles the empty input and the single segment, and tests on a shuffled example.

Senior (L5)

  • Validates the input without being asked: duplicate ids, no head, several heads, and a detached cycle caught by counting the segments used.
  • Explains the in-degree and out-degree invariant and uses it to argue that the walk ends.
  • Extends the solution to several chains cleanly, and recognises repeated ids as an Eulerian path problem with the degree conditions.

Staff (L6+)

  • Implements Hierholzer iteratively, explains why a greedy walk fails when ids repeat, and raises the tie-break question.
  • Covers undirected and reversible segments, the streaming merge design, and the trade-off between raising errors and returning a partial-result report.
  • Discusses the distributed version (a join on ids plus list ranking) and how to test it with randomized round-trip generators.

Sign in to comment, vote or remix.