Loading page…
Practice problem · easy
You work on a package manager for a code editor. A project depends on n packages, numbered 0 to n - 1. Some packages need others to be installed first.
If packages need each other in a loop, none of them can ever be installed. A package that needs a package inside a loop is stuck too. Before the install starts, the tool must tell the user exactly which packages are stuck, so they know where to look.
Write blocked_packages(n, needs).
n is the number of packages.needs[i] = [package, required] means package cannot be installed until required has been installed.[] when every package can be installed.Input: n = 6, needs = [[1, 0], [2, 1], [3, 2], [2, 3], [4, 3], [5, 0]]
Output: [2, 3, 4]Packages 2 and 3 need each other. Package 4 needs 3, so it is stuck behind them. Install what you can, and see what is left.
| Round | Queue | Install | Counts left (0 to 5) |
|---|---|---|---|
| start | 0 | 0, 1, 2, 1, 1, 1 | |
| 1 | 1, 5 | 0 | 0, 0, 2, 1, 1, 0 |
| 2 | 5 | 1 | 0, 0, 1, 1, 1, 0 |
| 3 | 5 | 0, 0, 1, 1, 1, 0 |
The queue is empty. Packages 2, 3 and 4 still have a count above 0, so they are the answer.
Input: n = 3, needs = [[1, 0], [2, 1]]
Output: []A chain with no loop. Every package gets installed.
Input: n = 3, needs = [[0, 1], [1, 2], [2, 0]]
Output: [0, 1, 2]All three need each other in a ring. No package has a count of 0 to start with, so none is installed.
1 ≤ n ≤ 100,0000 ≤ len(needs) ≤ 100,000, and every row is [package, required] with 0 ≤ package, required < n and package ≠ requiredThere can be 100,000 packages and 100,000 needs. Going over every need again after each install would be n × m: 10 billion steps. The answer must handle each package and each need a few times, which is n + m.
blocked_packages · runs in your browserCoding is easiest on a laptop. On a phone, read, trace and try small edits.