Build Up Software

Given a list of system packages, some packages cannot be installed until the other packages are installed. Provide a valid sequence to install all of the packages.
a relies on b
b relies on c
then a valid sequence is [c, b, a]

public List installPackages(List packages) {
    if(packages == null || packages.isEmpty()) return new LinkedList();

    int n = packages.size();
    int[] parentsCount = new int[n];

    for(Node package: packages) {
    	for(Node child: package.children) {   
    		parentsCount[child.label]  ;

    List sequence = new LinkedList<>(); //output to return
    for(Node package: packages) {
    	dfs(sequence, parentsCount, package);

    return sequence;

private void dfs(List sequence, int[] parentsCount, Node package) {
    if(parentsCount[package.label] == 0) {      
   	sequence.add(package.label);             //install package
    	parentsCount[package.label] --;        
    	for(Node child: package.children) {
    		parentsCount[child.label]-- ;  
    		dfs(sequence, parentsCount, child);

Get one-to-one training from Google Facebook engineers

Top-notch Professionals

Learn from Facebook and Google senior engineers interviewed 100+ candidates.
Most recent interview questions and system design topics gathered from aonecode alumnus.
One-to-one online classes. Get feedbacks from real interviewers.

Customized Private Class

Already a coding expert? - Advance straight to hard interview topics of your interest.
New to the ground? - Develop basic coding skills with your own designated mentor.
Days before interview? - Focus on most important problems in target company question bank.