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

What role is this question designed for?

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

Find k-th recipient in command propagation order

Company: Imc

Role: Software Engineer

Category: Coding & Algorithms

Difficulty: medium

Interview Round: Take-home Project

## Chain of Command (k-th Receiver in DFS-by-Child-Id Order) A company org chart forms a rooted tree with `n` people (nodes), labeled `1..n`. You are given an array `parent[1..n]` describing the tree: - `parent[i] = -1` means `i` is the root (top leader) - otherwise, `parent[i]` is the direct manager (parent) of person `i` - each node has zero or more direct reports (children) ### Command propagation rule When a person `u` issues a command, it is sent to **all subordinates** of `u` (all descendants of `u`), using this strict order: 1. Consider `u`’s direct children, sorted by increasing person id. 2. Send the command to the smallest-id child first. 3. Before sending to the next child, the command must be **fully propagated** throughout the current child’s entire subtree using the **same rule**. This defines a deterministic traversal order over the descendants of `u`: - It is equivalent to a DFS preorder over `u`’s subtree **excluding `u`**, where children are visited in ascending id. ### Task Given: - `parent[1..n]` - an issuer `u` - an integer `k` (1-indexed) Return the person id of the **k-th** subordinate who receives the command in the propagation order. If `u` has fewer than `k` descendants, return `-1`. ### Input/Output - Input: `parent[]`, `u`, `k` - Output: the person id of the k-th recipient, or `-1` ### Notes / Assumptions - The input forms a valid tree (exactly one root). - `k` is 1-indexed over recipients (descendants only; the issuer `u` is not counted). - Constraints may be large (e.g., `n` up to 2e5), so an approach better than simulating propagation step-by-step for each query is typically expected (if multiple queries are present, state how many).

Quick Answer: This question evaluates understanding of tree traversals, subtree indexing, and order-statistics on rooted trees, focusing on DFS-preorder propagation when children are visited in ascending id.

A company org chart forms a rooted tree with `n` people labeled `1..n`. You are given `parent`, a 0-indexed array of length `n` where `parent[i]` is the manager id of person `i+1`; a value of `-1` marks the root (top leader). Every non-root person has exactly one manager and zero or more direct reports. When a person `u` issues a command it is propagated to all of `u`'s descendants in a strict order: at each node, visit the direct children in increasing id order, and before moving on to the next child, fully propagate the command through the current child's entire subtree using the same rule. This is exactly a DFS preorder over `u`'s subtree, excluding `u`, with children visited in ascending id order. Given `parent`, an issuer `u`, and a 1-indexed integer `k`, return the person id of the k-th subordinate to receive the command. If `u` has fewer than `k` descendants, return `-1`.

Constraints

1 <= n <= 2 * 10^5 (n = len(parent))
People are labeled 1..n; parent is 0-indexed so parent[i] describes person i+1.
Exactly one entry of parent equals -1 (the unique root).
1 <= u <= n
1 <= k, and the input forms a valid tree (no cycles).
If u has fewer than k descendants, return -1.

Examples

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

Expected Output: 5

Explanation: children[1]=[2,3], children[2]=[4,5], children[3]=[6]. DFS preorder from root 1 (excluding 1): 2,4,5,3,6. The 3rd recipient is 5.

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

Expected Output: 2

Explanation: The first recipient is the smallest-id child of the root, which is 2.

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

Expected Output: 4

Explanation: Issuer u=2 has children [4,5]; the first recipient is 4.

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

Expected Output: -1

Explanation: Issuer u=2 has only 2 descendants (4 and 5), fewer than k=3, so return -1.

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

Expected Output: -1

Explanation: Person 6 is a leaf with no descendants, so any k returns -1.

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

Expected Output: -1

Explanation: Single-node tree: the root has no subordinates, so return -1.

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

Expected Output: 5

Explanation: A degenerate chain 1->2->3->4->5. DFS from 1: 2,3,4,5. The 4th recipient is 5.

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

Expected Output: 1

Explanation: person1's parent=2, person2's parent=3, person3 is root, person4's parent=3. children[3]=[2,4], children[2]=[1]. DFS from 3: 2,1,4. The 2nd recipient is 1, showing ids are not assumed to be in traversal order.

Hints

Build a children adjacency list from parent, then sort each node's children by id so the smallest-id child is visited first.
The propagation order is exactly a DFS preorder of u's subtree with u itself excluded — count nodes as you pop them and stop when the count reaches k.
Use an explicit stack and push children in reverse id order so the smallest id is processed next; this avoids recursion-depth limits for chains up to 2*10^5 deep.

Quick Overview

This question evaluates understanding of tree traversals, subtree indexing, and order-statistics on rooted trees, focusing on DFS-preorder propagation when children are visited in ascending id.