How do I approach Coding & Algorithms interview questions?

Coding & Algorithms questions require understanding of core concepts and practice. PracHub provides solutions with explanations to help you master coding & algorithms interviews.

What difficulty level is this interview 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.

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 payloads 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 Overview

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)

Assemble DNA payload strings from tagged fragments

Quick Overview

Q1: Single forward chain

Q2: Chain can be traversed in either direction

Q3: Multiple DNA chains

Output format

Comments (0)

Assemble DNA payload strings from tagged fragments

Quick Overview

Q1: Single forward chain

Q2: Chain can be traversed in either direction

Q3: Multiple DNA chains

Output format

Comments (0)