Back to Roblox questions
CodingSoftware Engineer

Avatar Assembly

Role: Software Engineer

You're building a Roblox avatar out of named components. Some components have dependencies — they can only be placed after their dependencies are already in place. Return a valid placement order using a level-order topological sort.

Problem Statement

Input: components: List[List[str]]

Each inner list describes one component and its dependencies:

  • group[0] — the component to place
  • group[1:] — components that must be placed before group[0]

All unique component names (whether they appear as a target or only as a dependency) must appear in the output.

Output: A valid placement order as a list of strings. If a cycle exists, return [].

Level-Order Tie-Breaking Rule

Components are placed in rounds using a round-based variant of Kahn's algorithm:

  1. At the start of each round, collect a snapshot of all currently-ready components (those with no unmet dependencies).
  2. Sort them by their earliest appearance index in the input (the smallest group index where the component appears anywhere — as a target or dependency). Break further ties lexicographically.
  3. Output all components in that round's sorted order.
  4. Only after the full round completes do newly-unlocked components become candidates for the next round.

Key point: A component unlocked during a round must wait until the next round, even if its earliest appearance index is smaller than components still in the current round.

Examples

Example 1 — Simple chain

python
components = [
    ["Hat", "Head"],   # Hat requires Head
    ["Head", "Torso"], # Head requires Torso
    ["Torso"],         # Torso has no dependencies
]
Output: ["Torso", "Head", "Hat"]

Example 2 — Dependency-only node

python
components = [
    ["Face", "Head"],  # Head only appears as a dependency, never as group[0]
]
Output: ["Head", "Face"]

Example 3 — Same-round tie-breaking

python
components = [
    ["Cape", "Base"],  # group index 0
    ["Base"],          # group index 1
    ["Gloves", "Base"],# group index 2
    ["Shoes"],         # group index 3
]

# Round 0 snapshot: Base (first seen at idx 0 as dep), Shoes (idx 3) → ["Base", "Shoes"]
# Round 1 snapshot: Cape (idx 0), Gloves (idx 2)                     → ["Cape", "Gloves"]

Output: ["Base", "Shoes", "Cape", "Gloves"]

Example 4 — Why level-order matters

python
components = [
    ["Hat", "Head"],    # idx 0 — Head first seen here
    ["Head", "Torso"],  # idx 1 — Torso first seen here
    ["Torso"],          # idx 2
    ["Shoes"],          # idx 3
]

# Round 0 snapshot: Torso (first_pos=1), Shoes (first_pos=3) → ["Torso", "Shoes"]
#   Placing Torso unlocks Head, but Head must wait for round 1.
# Round 1: Head (first_pos=0)
# Round 2: Hat  (first_pos=0)

Output: ["Torso", "Shoes", "Head", "Hat"]

Notice that with a naive global priority queue, Head (first_pos=0) would jump ahead of Shoes — but the level-order rule prevents that.

Example 5 — Cycle detection

python
components = [["A", "B"], ["B", "A"]]
Output: []

Function Signature

python
def assemble_avatar(components: List[List[str]]) -> List[str]:

Constraints

  • Component names are non-empty strings
  • The same component may appear in multiple groups
  • Components that only appear as dependencies (never as group[0]) must still be included in the output
  • If no valid ordering exists (cycle), return []