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 nan 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.

Reconstruct DNA from tagged fragments | Microsoft Interview Question

Q: Reconstruct DNA from tagged fragments

This question evaluates understanding of sequence reconstruction, graph modeling, and traversal/orientation constraints, focusing on ordering labeled fragments into a single non-repeating chain.

You are given a list of DNA fragments. Each fragment is represented by a Sequence object containing two endpoint labels and a DNA string payload.

Your task is to implement:

String shotgunSequence(List<Sequence> sequences)

The function must order the fragments into a single chain that uses every fragment exactly once, then return the reconstructed DNA string by concatenating the payload strings in that chain order.

Part 1 (Directed chaining)

Each fragment has:

startId (string)
endId (string)
payload (string)

A fragment i can be followed by fragment j iff:

i.endId == j.startId

Guarantees

All labels ( startId / endId ) are unique identifiers where applicable.
There exists exactly one valid ordering that uses all fragments.
The valid ordering forms one continuous chain.

Example

Fragments:

( "AAA" , "AAC" , "AAAA" )
( "AGG" , "ACC" , "GGGG" )
( "AAC" , "ACT" , "TTTT" )
( "ACT" , "AGG" , "CCCC" )

Valid label chain: AAA → AAC → ACT → AGG → ACC

Output: "AAAATTTTCCCCGGGG"

Follow-up (Unknown direction / two tags)

Now each fragment has:

tag1 (string)
tag2 (string)
payload (string)

Fragment orientation is unknown: a fragment can be traversed as either tag1 → tag2 or tag2 → tag1.

Two consecutive fragments can be connected if they share a tag (i.e., the end tag of the current traversal equals a tag on the next fragment, choosing its traversal direction appropriately).

Guarantees

At least one valid ordering exists that uses all fragments exactly once.
You must still use all fragments.

Example

Fragments:

( A , B , "AAAA" )
( B , C , "TTTT" )
( C , D , "CCCC" )
( D , B , "GGGG" )

One valid tag walk: A → B → C → D → B

Output: "AAAATTTTCCCCGGGG"

What to return

Return the concatenation of payloads in the chosen fragment order. (No extra separators; do not merge/overlap payload strings.)

You are given a list of DNA fragments. Each fragment is represented by a Sequence object containing two endpoint labels and a DNA string payload.

Your task is to implement:

String shotgunSequence(List<Sequence> sequences)

Part 1 (Directed chaining)

Each fragment has:

startId (string)
endId (string)
payload (string)

A fragment i can be followed by fragment j iff:

i.endId == j.startId

Guarantees

All labels ( startId / endId ) are unique identifiers where applicable.
There exists exactly one valid ordering that uses all fragments.
The valid ordering forms one continuous chain.

Example

Fragments:

( "AAA" , "AAC" , "AAAA" )
( "AGG" , "ACC" , "GGGG" )
( "AAC" , "ACT" , "TTTT" )
( "ACT" , "AGG" , "CCCC" )

Valid label chain: AAA → AAC → ACT → AGG → ACC

Output: "AAAATTTTCCCCGGGG"

Follow-up (Unknown direction / two tags)

Now each fragment has:

tag1 (string)
tag2 (string)
payload (string)

Fragment orientation is unknown: a fragment can be traversed as either tag1 → tag2 or tag2 → tag1.

Two consecutive fragments can be connected if they share a tag (i.e., the end tag of the current traversal equals a tag on the next fragment, choosing its traversal direction appropriately).

Guarantees

At least one valid ordering exists that uses all fragments exactly once.
You must still use all fragments.

Example

Fragments:

( A , B , "AAAA" )
( B , C , "TTTT" )
( C , D , "CCCC" )
( D , B , "GGGG" )

One valid tag walk: A → B → C → D → B

Output: "AAAATTTTCCCCGGGG"

What to return

Return the concatenation of payloads in the chosen fragment order. (No extra separators; do not merge/overlap payload strings.)

Reconstruct DNA from tagged fragments

Quick Overview

Part 1 (Directed chaining)

Guarantees

Example

Follow-up (Unknown direction / two tags)

Guarantees

Example

What to return

Comments (0)

Reconstruct DNA from tagged fragments

Quick Overview

Part 1 (Directed chaining)

Guarantees

Example

Follow-up (Unknown direction / two tags)

Guarantees

Example

What to return

Comments (0)