Wednesday, November 25, 2015

Amazon Interview Question

The Question is this: 
      6
    /  \
   3    5
  / \     \
 2   5    4
    / \
   7  4
There are 4 leaves, hence 4 root to leaf paths:
   Path           Sum
6->3->2           632
6->3->5->7       6357
6->3->5->4       6354
6->5>4            654  
Expected Answer: 632+6357+6354+654=13997 


The Program is this:


public class Main {
    public static void main(String[] args) {
        BinaryTree T = new BinaryTree(6);
        T.specialInsert();
        int answer = new AddLinkedListContnents().addLinkedLists(T.rootToLeaf());
        System.out.println("answer="+answer);
    }
}


//--------------------------------------------------------------------------------------------
import java.util.ArrayList;

public class BinaryTree {
    BinaryTree left, right;
    int data;
    public BinaryTree(int data) {
        this.data=data;
        this.left=null;
        this.right=null;
    }
    public void specialInsert()    {
        /*   6
            /  \
           3    5
          / \     \
         2   5    4
            / \
           7  4        */
        BinaryTree T = this;
        T.left=new BinaryTree(3);
        T.left.left=new BinaryTree(2);
        T.left.right=new BinaryTree(5);
        T.left.right.left=new BinaryTree(7);
        T.left.right.right=new BinaryTree(4);
        T.right=new BinaryTree(5);
        T.right.right=new BinaryTree(4);
    }
    private ArrayList<LinkedList> ArrList;
    public ArrayList<LinkedList> rootToLeaf()    {
        ArrList=new ArrayList<LinkedList>();
        rootToLead(this, new ArrayList<Integer>());
        for(LinkedList L:ArrList)    {
            L.printList();
        }
        return ArrList;
    }
    private void rootToLead(BinaryTree T, ArrayList<Integer> path)    {
        if(T!=null)    {
            path.add(T.data);
            if(T.left==null && T.right==null)    {
                ArrList.add(new LinkedList(path));
            }    else    {
                rootToLead(T.left, new ArrayList<>(path));
                rootToLead(T.right, new ArrayList<>(path));
            }
        }
    }
}


//--------------------------------------------------------------------------------------------
import java.util.ArrayList;
import java.util.Collections;

public class LinkedList {
    LinkedList next;
    int data;
    private int size;
    public LinkedList(int data) {
        this.data=data;
        this.next=null;
        this.size++;
    }
    public LinkedList(ArrayList<Integer> values) {
        Collections.reverse(values);
        //Inserts Values in reverse
        this.data=values.get(0);
        this.next=null;
        this.size++;
        insert(values);
    }
    private void insert(ArrayList<Integer> values) {
        int size = values.size();
        if(size>0)    {
            LinkedList L = this;
            for(int i=1; i<size; i++)    {
                L.next=new LinkedList(values.get(i));
                L=L.next;
                this.size++;
            }
        }
    }
    public void insert(int data)    {
        LinkedList L = this;
        while(L!=null)
            L=L.next;
        L.next=new LinkedList(data);
        this.size++;
    }
    public void printList()    {
        LinkedList L = this;
        StringBuffer sb = new StringBuffer();
        while(L!=null)    {
            sb.append(L.data).append(", ");
            L=L.next;
        }
        System.out.println(sb.toString());
    }
    public int getSize() {
        return size;
    }
    /*public void setSize(int size) {
        this.size = size;
    }*/
}


//--------------------------------------------------------------------------------------------
import java.util.ArrayList;

public class AddLinkedListContnents {
    public int addLinkedLists(ArrayList<LinkedList> ALs)    {
        int LargestArraySize=FindLargestArraySize(ALs);
        int carry = 0;
        StringBuffer sb = new StringBuffer();
        for(int i=0; i<LargestArraySize; i++)    {           
            int current_sum = carry;
            int size = ALs.size();
            for(int j=0; j<size; j++)    {
                if(ALs.get(j)!=null)    {               
                    current_sum=current_sum+ALs.get(j).data;
                    ALs.set(j, ALs.get(j).next);
                }
            }
            carry=current_sum/10;
            current_sum=current_sum%10;
            sb.append(current_sum);
            current_sum=0;
        }
        sb.append(carry);
        return Integer.parseInt(sb.reverse().toString());
    }
    private int FindLargestArraySize(ArrayList<LinkedList> ALs)    {
        int size=0;
        for(LinkedList L:ALs)    {
            if(size<L.getSize())
                size=L.getSize();
        }
        return size;
    }
}
//--------------------------------------------------------------------------------------------

No comments:

Post a Comment

UA-39217154-2