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 Technical Screen rounds at Microsoft.

What role is this question designed for?

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

Assemble DNA payload strings from tagged fragments

Quick Overview

This question evaluates proficiency in string manipulation, sequence assembly, and labeled-graph path reconstruction—skills involved in ordering fragments by matching start/end tags and concatenating payloads—and it belongs to the Coding & Algorithms domain.

Company: Microsoft

Role: Software Engineer

Category: Coding & Algorithms

Difficulty: medium

Interview Round: Technical Screen

You are given a list of DNA-like fragments. Each fragment is a tuple: - `start_tag`: string - `end_tag`: string - `payload`: string A valid DNA chain is formed by ordering fragments so that the `end_tag` of one fragment matches the `start_tag` of the next fragment. The assembled DNA string is the concatenation of `payload`s in chain order. Assume tags are arbitrary strings (e.g., `"AAA"`, `"AAC"`). ## Q1: Single forward chain Given fragments that form exactly one continuous chain using the rule `prev.end_tag == next.start_tag`, assemble and output the final concatenated string. Example: Input: - `(XXX, ATG, "Hello")` - `(ATG, GCA, "World")` - `(GCA, TAG, "!")` - `(TAG, YYY, "Done")` Output: - `"HelloWorld!Done"` ## Q2: Chain can be traversed in either direction Now treat each fragment as connecting two tags, and you may traverse the final chain either in the forward direction or in the reverse direction. - Forward traversal outputs payloads in forward order. - Reverse traversal outputs payloads in reverse order. - Either output is acceptable. For the example above, valid outputs include: - `"HelloWorld!Done"` (forward) - `"Done!WorldHello"` (reverse) ## Q3: Multiple DNA chains Now the input fragments may form multiple disjoint chains (still assuming they can be arranged into simple chains with no branching within a chain). Output all assembled strings, one per chain, in any order. ### Output format - Q1/Q2: a single string - Q3: a list/array of strings (one per chain)

Quick Answer: This question evaluates proficiency in string manipulation, sequence assembly, and labeled-graph path reconstruction—skills involved in ordering fragments by matching start/end tags and concatenating payloads—and it belongs to the Coding & Algorithms domain.

Part 1: Assemble a Single Forward DNA Chain

You are given a list of DNA-like fragments. Each fragment is a tuple `(start_tag, end_tag, payload)`. The fragments are guaranteed to form exactly one directed continuous chain, meaning the `end_tag` of each fragment matches the `start_tag` of the next fragment. Assemble the chain and return the concatenation of the payload strings in chain order. If the input list is empty, return the empty string.

Constraints

0 <= len(fragments) <= 100000
Each `start_tag`, `end_tag`, and `payload` is a string.
For non-empty input, the fragments form one valid directed path with no branching.
No tag has more than one outgoing fragment or more than one incoming fragment.
The total length of all payload strings is at most 1000000.

Examples

Input: ([('XXX', 'ATG', 'Hello'), ('ATG', 'GCA', 'World'), ('GCA', 'TAG', '!'), ('TAG', 'YYY', 'Done')],)

Expected Output: 'HelloWorld!Done'

Explanation: The fragments are already in chain order.

Input: ([('B', 'C', '2'), ('A', 'B', '1'), ('C', 'D', '3')],)

Expected Output: '123'

Explanation: The correct chain is A -> B -> C -> D, so the payload order is 1, 2, 3.

Hints

Think of each fragment as a directed edge from `start_tag` to `end_tag`.
The first fragment starts at the tag that appears as a `start_tag` but never as an `end_tag`.

Part 2: Assemble a DNA Chain Traversable in Either Direction

You are given a list of DNA-like fragments. Each fragment is a tuple `(tag_a, tag_b, payload)`. This time, treat each fragment as an undirected connection between two tags. The fragments are guaranteed to form one simple chain with no branching. You may traverse the chain from either endpoint. When traversing, output each fragment's payload in traversal order; the payload string itself is not reversed. Conceptually, either direction is a valid assembly. For deterministic results in this problem, return the assembly obtained by starting from the lexicographically smallest endpoint tag. If the input list is empty, return the empty string.

Constraints

0 <= len(fragments) <= 100000
Each `tag_a`, `tag_b`, and `payload` is a string.
For non-empty input, the fragments form one simple undirected path with no branching.
Each tag has undirected degree at most 2.
The total length of all payload strings is at most 1000000.

Examples

Input: ([('XXX', 'ATG', 'Hello'), ('ATG', 'GCA', 'World'), ('GCA', 'TAG', '!'), ('TAG', 'YYY', 'Done')],)

Expected Output: 'HelloWorld!Done'

Explanation: The endpoints are XXX and YYY. Starting from XXX gives the forward payload order.

Input: ([('M', 'Z', 'middle'), ('A', 'M', 'start')],)

Expected Output: 'startmiddle'

Explanation: The endpoints are A and Z. Starting from A visits payloads start, then middle.

Hints

Build an undirected adjacency list where each edge stores its payload.
A chain endpoint is a tag with degree 1. Start from the smaller endpoint and walk without going back over the edge you just used.

Part 3: Assemble Multiple Forward DNA Chains

You are given a list of DNA-like fragments. Each fragment is a tuple `(start_tag, end_tag, payload)`. The fragments may belong to multiple disjoint directed chains. Within each chain, fragments are ordered by the rule that the `end_tag` of one fragment equals the `start_tag` of the next fragment. There is no branching within any chain. Return the assembled payload string for every chain. Conceptually, the chains may be returned in any order; for deterministic results in this problem, return the assembled strings sorted lexicographically.

Constraints

0 <= len(fragments) <= 100000
Each `start_tag`, `end_tag`, and `payload` is a string.
The fragments form zero or more disjoint directed paths.
No tag has more than one outgoing fragment or more than one incoming fragment.
The total length of all payload strings is at most 1000000.

Examples

Input: ([('A', 'B', 'Hi'), ('C', 'D', 'Bye')],)

Expected Output: ['Bye', 'Hi']

Explanation: There are two one-fragment chains. The returned list is sorted lexicographically.

Input: ([('M', 'N', 'b'), ('A', 'B', 'x'), ('B', 'C', 'y'), ('N', 'O', 'c')],)

Expected Output: ['bc', 'xy']

Explanation: The chains are M -> N -> O producing bc, and A -> B -> C producing xy.

Hints

Use indegree and outdegree to find the starting tag of each chain.
After finding every start tag, traverse each chain exactly once and collect its payloads.

Quick Overview