Reconstruct a string from chained segments

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.