Yahoo-GTJAG

1) You have been given a triangle of numbers as shown below. You are supposed to start at the top and go to the base of the triangle by taking a path which gives the maximum sum. You have to print this maximum sum at the end. A path is formed by moving down 1 row at each step to either of the immediately diagonal elements. 
     [2],
    [3,4],
   [6,5,7],
  [4,1,8,3]

2-4-7-8

2) Given an array of strings, display all the strings that are not prefix of any other string in the array.
(Hint #1: Sorting; Hint #2: Trie)

Yahoo-GTJAG-1.java

//assume every value is larger than 0
public static int findMaxSum(ArrayList<int[]> triangle){
    if(triangle == null || triangle.size() == 0) return -1;
    ArrayList<int[]> dp = new ArrayList<>();
    for(int i = 1; i < triangle.size(); i++){
        dp.add(new int[i]);
    }
    return findMaxSum(0, 0, triangle, dp);
}

public static int findMaxSum(int row, int column, ArrayList<int[]> triangle, ArrayList<int[]> dp){
    if(row == triangle.size() - 1) return triangle.get(row)[column];
    else if(dp.get(row)[column] != 0) return dp.get(row)[column];
    
    return dp.get(row)[column] = triangle.get(row)[column] + 
        Math.max(findMaxSum(row + 1, column, triangle, dp), findMaxSum(row + 1, column + 1, triangle, dp));
}

Yahoo-GTJAG-2.java

public static void printNotPrefix(String[] input){
    PrefixTree tree = new PrefixTree();
    for(String string : input){
        tree.insert(string);
    }
    StringBuffer sb = new StringBuffer();
    printNotPrefix(tree.root, sb);
}

public static void printNotPrefix(Node root, StringBuffer sb){
    if(root.isWord && root.sons.size() == 0) System.out.println(sb.toString());
    for(Entry<Character, Node> entry : root.sons.entrySet()){
        sb.append(entry.getKey());
        printNotPrefix(entry.getValue(), sb);
        sb.deleteCharAt(sb.length() - 1);
    }
}

class PrefixTree{
    Node root;
    PrefixTree(){
        root = new Node();
    }
    public void insert(String word){
        if(word == null || word.length() == 0) return;
        insert(this.root, word);
    }
    private void insert(Node root, String word){
        if(word.length() == 0) root.isWord = true;
        else{
            char thisChar = word.charAt(0);
            if(root.sons.containsKey(thisChar)) insert(root.sons.get(thisChar), word.substring(1));
            else{
                root.sons.put(thisChar, new Node());
                insert(root.sons.get(thisChar), word.substring(1));
            }
        }
    }
}

class Node{
    boolean isWord;
    HashMap<Character, Node> sons;
    Node(){
        this.isWord = false;
        this.sons = new HashMap<>();
    }
}