Katkat
Back

Assemble DNA payload strings from tagged fragments

MicrosoftSoftware Engineer · Technical Screen
MediumSoftware EngineerTechnical ScreenCoding & Algorithms

Last updated

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)