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 hard difficulty Coding & Algorithms question, commonly asked during Onsite rounds at Wave.

What role is this question designed for?

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

Construct a circular gift exchange across families

Q: Construct a circular gift exchange across families

This question evaluates ability to model constrained permutations and apply graph-theoretic and combinatorial reasoning to produce a single circular ordering where adjacent elements come from different sub-groups.

You are given a “big family” composed of several sub-families. Each sub-family is a list of unique person IDs/names.

Example input:

[[A1, A2], [B1, B2], [C1]]

You need to produce a circular gift-exchange chain that includes every person exactly once, such that:

No one gives a gift to someone in the same sub-family.
- In the chain order, this means adjacent people (giver → receiver) must come from different sub-families.
The arrangement must form one cycle (a single circular chain).
- If the output order is p0, p1, ..., p(n-1) , then gifts go p0→p1, p1→p2, ..., p(n-2)→p(n-1), p(n-1)→p0 .

Input

A list of sub-families, where each sub-family is a list of strings (or integers) representing people.

Output

Return any valid circular ordering of all people (or equivalently, the directed gift pairs), or indicate that it is impossible .

Notes / Clarifications

People are distinct across all sub-families.
The chain must include everyone exactly once.
If there are multiple valid answers, any one is acceptable.

Example (one possible valid output)

For [[A1, A2], [B1, B2], [C1]], a valid circular ordering could be:

[A1, B1, A2, B2, C1]

This implies: A1→B1→A2→B2→C1→A1, and no adjacent pair is from the same sub-family.

You are given a “big family” composed of several sub-families. Each sub-family is a list of unique person IDs/names.

Example input:

[[A1, A2], [B1, B2], [C1]]

You need to produce a circular gift-exchange chain that includes every person exactly once, such that:

No one gives a gift to someone in the same sub-family.
- In the chain order, this means adjacent people (giver → receiver) must come from different sub-families.
The arrangement must form one cycle (a single circular chain).
- If the output order is p0, p1, ..., p(n-1) , then gifts go p0→p1, p1→p2, ..., p(n-2)→p(n-1), p(n-1)→p0 .

Input

A list of sub-families, where each sub-family is a list of strings (or integers) representing people.

Output

Return any valid circular ordering of all people (or equivalently, the directed gift pairs), or indicate that it is impossible .

Notes / Clarifications

People are distinct across all sub-families.
The chain must include everyone exactly once.
If there are multiple valid answers, any one is acceptable.

Example (one possible valid output)

For [[A1, A2], [B1, B2], [C1]], a valid circular ordering could be:

[A1, B1, A2, B2, C1]

This implies: A1→B1→A2→B2→C1→A1, and no adjacent pair is from the same sub-family.

Construct a circular gift exchange across families

Quick Overview

Input

Output

Notes / Clarifications

Example (one possible valid output)

Submit Your Answer to Earn 20XP

Construct a circular gift exchange across families

Quick Overview

Input

Output

Notes / Clarifications

Example (one possible valid output)

Submit Your Answer to Earn 20XP