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 easy difficulty Coding & Algorithms question, commonly asked during Take-home Project rounds at Google.

What role is this question designed for?

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

Find Feature Activation Order | Google Coding Question

Find Feature Activation Order

Company: Google

Role: Software Engineer

Category: Coding & Algorithms

Difficulty: easy

Interview Round: Take-home Project

You are building a feature-flag system for a product. There are `n` features labeled `0` to `n - 1`. Each dependency pair `[a, b]` means feature `a` depends on feature `b`, so `b` must be active before `a` can be activated. You are also given: - a set `active` of features that are already enabled, and - a target feature `t` that a user wants to activate. A feature can be activated only after **all** of its direct and indirect prerequisites are active. If a prerequisite is not active yet, it must be activated first. Write a function that returns **one valid order** of newly activated features needed to enable `t`. Rules: 1. Only include features that are not already active. 2. The returned order must activate prerequisites before any dependent feature. 3. If `t` is already active, return an empty list. 4. If `t` cannot be activated because its dependency chain contains a cycle, return `null`. Example: - `dependencies = [[3,1],[3,2],[2,0]]` - `active = {1}` - `t = 3` A valid answer is `[0,2,3]`. Implement this efficiently.

Quick Answer: This question evaluates graph-algorithms and dependency-resolution skills, including reasoning about prerequisite relationships, ordering constraints, and cycle detection.

You are building a feature-flag system for a product. There are `n` features labeled `0` to `n - 1`. Each dependency pair `[a, b]` means feature `a` depends on feature `b`, so `b` must be active before `a` can be activated. You are given: - the number of features `n`, - a list of `dependencies` where each entry `[a, b]` means `a` depends on `b`, - a set/list `active` of features that are already enabled, and - a target feature `t` that a user wants to activate. A feature can be activated only after **all** of its direct and indirect prerequisites are active. If a prerequisite is not active yet, it must be activated first. Return **one valid order** of the newly activated features needed to enable `t`. Rules: 1. Only include features that are not already active. 2. The returned order must activate prerequisites before any dependent feature. 3. If `t` is already active, return an empty list. 4. If `t` cannot be activated because its dependency chain contains a cycle, return `null` (`None` in Python). Example: - `dependencies = [[3,1],[3,2],[2,0]]`, `active = {1}`, `t = 3` - A valid answer is `[0, 2, 3]` (feature 0 enables 2, then 2 and the already-active 1 enable 3). When several valid orders exist, the reference solution emits prerequisites in the order their dependency edges are listed, so for a deterministic check assume that convention.

Constraints

0 <= a, b, t < n
Dependency pairs may be listed in any order.
A feature already in `active` (and all of its prerequisites) is treated as satisfied.
The graph may contain cycles; a cycle on the path to t means t is unactivatable.
Already-active features and their prerequisites are never re-added to the result.

Examples

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

Expected Output: [0, 2, 3]

Explanation: Prompt example. Feature 1 is already active; activate 0, then 2 (needs 0), then 3 (needs 1 and 2).

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

Expected Output: [0, 1, 2]

Explanation: Linear chain 2->1->0 with nothing active: must enable 0, then 1, then 2.

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

Expected Output: [0]

Explanation: Single feature with no prerequisites and not active: just activate it.

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

Expected Output: []

Explanation: Target 1 is already active, so no new features are needed.

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

Expected Output: None

Explanation: 0->1->2->0 forms a cycle on the path to t, so t can never be activated.

Input: (5, [[4,3],[3,2],[2,1],[1,0]], [2], 4)

Expected Output: [3, 4]

Explanation: Feature 2 is active (so 1 and 0 below it are pruned); only 3 (needs 2) and then 4 (needs 3) must be activated.

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

Expected Output: [0, 1, 2]

Explanation: Fork: 2 depends on 0 and 1. Edges are listed [2,0] then [2,1], so prerequisites come out as 0, 1, then 2.

Hints

Model features as a directed graph where an edge a -> b means 'a needs b first'. You want all prerequisites of t topologically ordered before t.
A post-order DFS from t naturally appends a node only after all of its prerequisites are appended, giving a valid activation order.
Treat any feature in `active` as a leaf: stop the DFS there and do not add it to the result.
Detect cycles with a three-state coloring (unvisited / on-stack / done): encountering an on-stack node means a back edge, so return null.

Quick Overview

This question evaluates graph-algorithms and dependency-resolution skills, including reasoning about prerequisite relationships, ordering constraints, and cycle detection.