Amazon Interview Question
Senior Software Development EngineersCountry: United States
Interview Type: Phone Interview
Now with proper format
public class SoftwareGraph{
//the software names
ArrayList<String> name = new ArrayList<String>();
HashMap<String, Integer> nameToIndexMap = new HashMap<String, Integer>();
//dependencies
ArrayList<HashSet<Integer>> dependsOn = new ArrayList<HashSet<Integer>>();
//supports
ArrayList<HashSet<Integer>> supports = new ArrayList<HashSet<Integer>>();
public boolean addSoftware(String name, Collection<String> depends){
if(this.nameToIndexMap.get(name) != null){
return false;
}
//prepare the sets to add
HashSet<Integer> dependsOn = new HashSet<Integer>();
if(depends != null){
for(String dependsName : depends){
Integer dependsIndex = nameToIndexMap.get(dependsName);
if(dependsIndex == null){
return false;
}
dependsOn.add(dependsIndex);
}
}
HashSet<Integer> supports = new HashSet<Integer>();
//add the new content to the graph
this.names.add(name);
this.nameToIndexMap.put(name, this.names.size()-1);
this.dependsOn.add(dependsOn);
this.supports.add(supports);
return true;
}
public boolean remove(String name){
Integer index = nameToIndex.get(name);
if(index == null){
return true;
}
if(supports.get(index).size() == 0){
nameToIndex.remove(name);
names.remove(index);
dependsOn.remove(index);
supports.remove(index);
return true;
}
return false;
}
keep all dependencies in a graph. A directed edge means that there is a dependency. All nodes would keep a dependsOn count which is the number of edges pointing at them. If dependsOn is 0 you can delete the module.
Now for fast lookup into the graph also maintain a hash for each installed module.
How about using a tree, where, root file system ("/"), is the root of the tree. // Being mount point its the first requirement of any program to present in the system.
- Anonymous September 26, 2014Now, various, programs which are made child of this are dependent of this.
when removing you got to remove from the bottom.( leaves )
if any program is removed as nodes, it would be required that the leaves are deleted first.
Insertion of any program shall happen in the leaves as well. If it had to make a node, in bettwen ( for some dependant program ) it would be done likewise.
Kindly let me know if this solution does not work in any test case.
Regards
Ashutosh