Amazon Interview Question for Software Engineer / Developers


Country: India
Interview Type: Written Test




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

fdb fdvbfdbfdvb fdvbfgdvb gf

- vfdvfdbfdb March 24, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
1
of 1 vote

Start preorder traversal of T1 till either T2 is found or full tree has been traversed.
Case 1. T2 is found: Do preorder traversal of both trees together and keep comparing the nodes. If all nodes same till T2 is completely traversed, T2 is a subtree of T1.
Case 2: Check if T1 is a subtree of T2.

- Anonymous March 25, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

It's important that the trees are ordered the same way.

If both trees are equivalently order (lets say the comparison operator for comparing trees is called "compare"), then the code would look like this:

javascript

function Tree(children){
  this.children = children || [];
  this.children.sort(compare);
}

Tree.prototype = {
  constructor : Tree,
  equals : function(obj){
    return compare(this,obj) == 0;
  },
  contains : function(obj){
    if(this.equals(obj))
      return true;
    for(var c in this.children){
      if(compare(this.children[c],obj) == 0)
        return true;
      if(this.children[c] instanceof Tree && this.children[c].contains(obj))
        return true;
    }
    return false;
  }
};

Here is an example of a "compare" function

javascript

function compare(a,b){
  if(a instanceof Tree && b instanceof Tree){
    // sort Trees with more children first
    if(a.children.length != b.children.length){
      return a.children.length - b.children.length;
    }
    for(var i = 0; i < a.children.length; ++i){
      var comparison = compare(a.children[i],b.children[i]);
      if(comparison != 0)
        return comparison;
    }
    return 0;
  }
  // sort other objects before trees
  if(a instanceof Tree){
    // change trees with one child into objects for sorting purposes
    if(a.children.length == 1)
      a = a.children[0];
    else
      return 1;
  }
  if(b instanceof Tree){
    // change trees with one child into objects for sorting purposes
    if(b.children.length == 1)
      b = b.children[0];
    else
      return -1;
  }
  // sort comparable objects in ascending order
  if(a>b){
    return 1;
  }
  if(a<b){
    return -1;
  }
  return 0;
}

Here are some test cases:

javascript

var a = new Tree([7,5,2,new Tree([6, 4, 3])]);
var b = new Tree([3,6,4]);
var c = new Tree([4]);
var d = new Tree([2,7]);
console.log (b.contains(c)); //true
console.log (a.contains(c)); //true
console.log (a.contains(b)); //true
console.log (a.contains(d)); //false

Here is the same example using arrays as trees:

javascript

function contains(arr1,arr2){
  if(compare(arr1,arr2) == 0)
    return true;
  for(var a in arr1){
    if(contains(arr1[a],arr2))
      return true;
  }
  return false;
}

function compare(a,b){
  if(a.sort)
    a.sort(compare);
  if(b.sort)
    b.sort(compare);
  
  if(a.length == 1)
    a = a[0];
  if(b.length == 1)
    b = b[0];
  
  // sort other objects before arrays
  if(a>b || (!a.length && b.length)){
    return 1;
  }
  if(a<b || (!b.length && a.length)){
    return -1;
  }
  return 0;
}

var a = [7,5,2,[6,4,3]];
var b = [3,6,4];
var c = [4];
var d = [2,7];
console.log (contains(b,c)); //true
console.log (contains(a,c)); //true
console.log (contains(a,b)); //true
console.log (contains(a,d)); //false

- goalbased March 24, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

First see the levels of trees..the tree(T2) with more levels will obviously cover the other one(T1).
now for T1's each element,
recursively search elements in T2 and if all nodes match return true ...

- Anonymous March 29, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

there can be a case when the subtree happens to start from the root of the bigger tree and the levels could be same in that case, the tree with lesser number of nodes is the criteria to find the smaller tree.

- k2 April 15, 2012 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

if it is part of that tree.then match only root of small tree.because address of the small tree would be same as the address of a node of bigger tree.then no need to match further because if address is same then other address would be same.if every data structure is same.

if it says that we want to search value of small tree should be same subtree on bigger tree if it present there.then take a queue put bigger tree nodes on that and search every element from small tree from root of the small tree.

- Anonymous April 28, 2012 | 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