How do I practice coding and algorithm questions?

Use PracHub's coding console to write, test, and debug your solutions in Python or JavaScript. View hints, test against sample inputs, and compare with official solutions.

What difficulty level is this coding question?

This is a medium difficulty Coding & Algorithms question, commonly asked during Take-home Project rounds at Intuit.

What role is this question designed for?

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

Produce valid student lineup from parent array

Quick Overview

This question evaluates understanding of rooted tree hierarchies, parent-before-child ordering constraints, and lexicographic minimality when constructing a valid sequence, testing competencies in tree/graph algorithms and deterministic ordering logic.

Company: Intuit

Role: Software Engineer

Category: Coding & Algorithms

Difficulty: medium

Interview Round: Take-home Project

You are given a hierarchy of **n** students represented by a **parent array** `par` of length `n`. - Students are labeled `1..n`. - `par[i]` is the parent (mentor/manager) of student `i+1`. - Exactly one student is the root with `par[root-1] = -1`. - For all other students, `par[i]` is an integer in `[1..n]`. - The input is guaranteed to form a valid rooted tree (no cycles, every node reachable from the root). A *valid lineup* is an ordering of all students such that **each student appears after their parent**. **Task:** Return the **lexicographically smallest** valid lineup (compare two lineups by the first position where they differ; the one with the smaller student id is smaller). **Example** Input: `par = [-1, 1, 1, 2, 2, 2, 2]` This means: - Student 1 is the root. - Students 2 and 3 report to 1. - Students 4,5,6,7 report to 2. One correct output: `[1, 2, 3, 4, 5, 6, 7]` **Constraints (assume):** `1 <= n <= 2e5`.

Quick Answer: This question evaluates understanding of rooted tree hierarchies, parent-before-child ordering constraints, and lexicographic minimality when constructing a valid sequence, testing competencies in tree/graph algorithms and deterministic ordering logic.

You are given a hierarchy of n students represented by a parent array par of length n. Students are labeled from 1 to n. For each student i (1-indexed), par[i-1] is the parent of student i. Exactly one student is the root and has parent -1. The input always forms a valid rooted tree. A valid lineup is an ordering of all students such that every student appears after their parent. Return the lexicographically smallest valid lineup. A lineup A is lexicographically smaller than lineup B if at the first position where they differ, A has the smaller student id. Example: par = [-1, 1, 1, 2, 2, 2, 2] The root is student 1. Students 2 and 3 are children of 1, and students 4, 5, 6, 7 are children of 2. The lexicographically smallest valid lineup is [1, 2, 3, 4, 5, 6, 7].

Constraints

1 <= n <= 200000
Students are labeled 1 through n
Exactly one entry in par is -1
For every other student, par[i] is in the range [1, n]
The input forms a valid rooted tree

Examples

Input: ([-1, 1, 1, 2, 2, 2, 2],)

Expected Output: [1, 2, 3, 4, 5, 6, 7]

Explanation: Student 1 must come first. Then students 2 and 3 become available, so choose 2 before 3. After choosing 2, students 4, 5, 6, 7 become available, but 3 is still smaller than all of them, so it comes next.

Input: ([-1],)

Expected Output: [1]

Explanation: There is only one student, so the lineup contains just that student.

Input: ([-1, 1, 1, 2],)

Expected Output: [1, 2, 3, 4]

Explanation: After placing 1, students 2 and 3 are available. Pick 2 first. Then both 3 and 4 are available, and 3 is smaller, so it must come before 4.

Input: ([2, -1, 2, 1],)

Expected Output: [2, 1, 3, 4]

Explanation: Student 2 is the root. After placing 2, students 1 and 3 are available. Pick 1 first, then 3, then 4.

Input: ([4, 4, 4, -1, 2, 2, 1],)

Expected Output: [4, 1, 2, 3, 5, 6, 7]

Explanation: Student 4 is the root. After 4, students 1, 2, 3 are available. Choose 1, then 2, then 3. After 2, students 5 and 6 become available, and after 1, student 7 becomes available. The smallest eligible student is always chosen next.

Hints

Think of this as finding the lexicographically smallest topological ordering of a tree.
At any step, all students whose parent is already in the lineup are eligible. Use a min-heap to always choose the smallest eligible student.

Quick Overview