Amazon Interview Question for Senior Software Development Engineers


Country: United States
Interview Type: Phone Interview




Comment hidden because of low score. Click to expand.
0
of 0 vote

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.

Now, 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

- Anonymous September 26, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

@Ashutosh : The approach may not work. A program may have multiple dependencies and multiple programs may be depending on these dependencies too.. ?

- Byll September 26, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote
How about a graph where each vertex has two sets of edges, depends_on and supports. {{{ 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; } - zortlord September 26, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

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; 
}

- zortlord September 26, 2014 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

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.

- Anonymous September 26, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

looks like a problem for topological sorting in graph...Correct me if wrong..

- deepanshu November 09, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

any solutions to this problem?

- MAndy December 15, 2016 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

This is a salesforce problem..

- Wow November 20, 2017 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

i googled this problem a lot but did not found any solution for it.

- anjneesharma October 03, 2018 | Flag Reply


Add a Comment
Name:

Writing Code? Surround your code with {{{ and }}} to preserve whitespace.

Books

is a comprehensive book on getting a job at a top tech company, while focuses on dev interviews and does this for PMs.

Learn More

Videos

CareerCup's interview videos give you a real-life look at technical interviews. In these unscripted videos, watch how other candidates handle tough questions and how the interviewer thinks about their performance.

Learn More

Resume Review

Most engineers make critical mistakes on their resumes -- we can fix your resume with our custom resume review service. And, we use fellow engineers as our resume reviewers, so you can be sure that we "get" what you're saying.

Learn More

Mock Interviews

Our Mock Interviews will be conducted "in character" just like a real interview, and can focus on whatever topics you want. All our interviewers have worked for Microsoft, Google or Amazon, you know you'll get a true-to-life experience.

Learn More