Interviews

Build Up Software

user profile image
System made a post.

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.
e.g.
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);
    	}
    }
}


One-on-One Algorithm and Coding Training

One-on-One System Design Training

One-on-One Mock Interview

Get one-to-one training from Google Facebook engineers


Top-notch Professionals

Learn from Facebook, Google, Uber senior engineers interviewed 100+ candidates.aonecode.com
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.


Free Consultation

aonecoding@gmail.com