longest repeated substring using simplest suffix tree

public class SuffixTree {

STNode root;

class STNode {

int data ;

STNode[] edges;

STNode(int d){

data = d;

}

STNode(){

}

}

//assume small cases: a-z

STNode addString(String s, int data){

if(root==null)

root = new STNode(-1);

STNode current = root;

int index = 0;

while(index<s.length()){

if(current.edges==null)

current.edges = new STNode[26];

int pos = s.charAt(index) - 'a';

if(current.edges[pos]==null)

current.edges[pos] = new STNode();

current = current.edges[pos];

index++;

}

current.data = data; //leaf store the position

return root;

}

public void addAllSubString(String s){

for(int i=0;i<s.length();i++){

this.addString(s.substring(i), i);

}

}

public String findLongestRepeatSub(String s){

this.addAllSubString(s);

Deque<STNode> sk = new ArrayDeque<STNode>();

sk.add(root);

int maxL = 0;

int currentL = 0;

STNode target = root;

while(!sk.isEmpty()){

Deque<STNode> temp = new ArrayDeque<STNode>();

while(!sk.isEmpty()){

STNode n = sk.remove();

currentL++;

int counter=0;

if(n.edges!=null){

for(STNode nd : n.edges){

if(nd!=null){

sk.add(nd);

counter++;

}

}

}

if(counter>1 || counter==1 && n.data>0){

if(currentL>maxL){

maxL = currentL;

target = n;

}

}

}

sk = temp;

}

int cn = 0;

//go down to the leaf if not on leaf yet.

while(target.data<=0){

if(target.edges!=null){

for(STNode nd : target.edges){

if(nd!=null){

target = nd;

cn++;

}

}

}

}

if(cn!=0)

return s.substring(target.data, s.length()-cn+1);

else

return s.substring(target.data, s.length());

}

}

In-Order Flatten A Binary Tree to Linked List

In-order flatten binary tree, the idea here is similar to in-order traverse of the tree, keep a pointer to previous node visited, then link current node with previous.

public static void FlattenABinaryTreetoLinkedListInOrder(Node root){

Stack<Node> s = new Stack<Node>();

Node c = root;

Node pre = null;

while(!s.isEmpty()||c!=null){

if(c!=null){

s.push(c);

c = c.left;

}

else{

Node n = s.pop();

if(pre!=null){

pre.right = n;

pre.left = null;

}

pre = n;

n = n.right;

}

}

}

Pre-Order Flatten A Binary Tree to Linked List

To do it iteratively is little bit tricky, since when we do down to the left of tree, we need to remember the way to go back to right.

The idea is to use a stack to store the right child when we go to left.

Here is the code:

public static void FlattenABinaryTreetoLinkedList(Node root){

Stack<Node> s = new Stack<Node>();

Node c = root;

while(!s.isEmpty()||c!=null){

if(c.left!=null){//keep on going left

if(c.right!=null)//remember the right child

s.push(c.right);

c.right = c.left;

c.left = null;

c = c.right;

}

else{//reach the far left, now we need to go right

Node n = s.pop();

c.right = n;

c = n;

}

}

}

Construct Tree from given Inorder and Preorder traversals

Problem:
Give two strings representing the inorder and preorder traversals of binary tree, construct the tree.

The key here is that preorder traversal, the first char is the tree root. And then based on that char, find the its position in inorder string, then its left portion of in order string is the left subtree, right portion is the right subtree.

And do it recursively, make it simpler.

public static Node constructTree(String pre, String in){

if(pre.isEmpty())

return null;

if(pre.length() == 1)

return new Node(pre.charAt(0));

Node root = new Node(pre.charAt(0));

String[] ins = splitStringBy(in, pre.charAt(0));

                root.left = constructTree(pre.substring(1, ins[0].length()+1), ins[0]);

root.right = constructTree(pre.substring(ins[0].length()+1), ins[1]);

return root;

}

public static String[] splitStringBy(String str, char root){

String[] re = new String[2];

re[0] = str.substring(0, str.indexOf(root));

re[1] = str.substring(str.indexOf(root)+1);

return re;

}

Find the maximum sum from leaf to root in a binary tree

Given a Binary Tree, find the maximum sum from a leaf to root and return this leaf as well.


The key is from root to leave, add up the node value and pass the sum to the lower levels. 

public static int maxSumFromRootHelper(Node root, int sum){

if(root == null)

return sum;

else{

return Math.max(maxSumFromRootHelper(root.left, root.data + sum),

  maxSumFromRootHelper(root.right, root.data + sum));

}

}

//store the max sum result

static int max_sum = Integer.MIN_VAL;

//store the leaf 

static Node maxNode = null;

public static void findLeaveWithMaxSumFromRoot(Node root, int sum){

if(root == null)

return;

sum = sum + root.data;

if(root.left == null && root.right ==null){

if(sum > max_sum){

max_sum = sum;

maxNode = root;

}

}

else{

findLeaveWithMaxSumFromRoot(root.left, sum);

findLeaveWithMaxSumFromRoot(root.right, sum);

}

} 

divide number and return result in a string

This is a google interview question: 

Divide number and return result in form of a string. e.g 100/3 result should be 33.(3) Here 3 is in brackets because it gets repeated continuously and 5/10 should be 0.5.

Here is my attempt, the key is to doing module and division, also figure out how many 0s are there after decimal point. 

public static String divideToString(int num1, int num2){
    int d = num1/num2;
    int m = num1%num2;
    boolean flag = false;
    Set<Integer> seen = new HashSet<Integer>();
    StringBuilder sb = new StringBuilder();
    sb.append(d);
    while(m!=0){
    if(!flag){
        sb.append(".(");
        flag = true;
    } 

     

    num1 = m*10;
    d = num1/num2;
    m = num1%num2;

       

    if(seen.contains(num1)){
    sb.append(")");
    break;
    }else{
    sb.append(d);  
    seen.add(num1);
    }
    }

   

    return sb.toString();
}

Permutations for digits represented by Phone Number

This is a stackoverflow question: http://stackoverflow.com/questions/1851239/permutations-for-digits-represented-by-phone-number

This can be done by dynamic programming and just need to keep track of the previous result list and build result based on it.

public static List<String> allWordsFromPhonePad(int number){

HashMap<Integer, String > h = new HashMap<Integer, String>(){{

        put(1,"");

        put(2, "ABC");

        put(3, "DEF");

        put(4, "GHI");

        put(5, "JKL");

        put(6, "MNO");

        put(7, "PQRS");

        put(8, "TUV");

        put(9, "WXYZ");

        put(0, "");

    }};

    List<String> result = new ArrayList<String>();

    result.add("");

    while(number>0){

    int last = number%10;

    List<String> temp = new ArrayList<String>();

   

    for(String s: result){

    String map = h.get(last);

    for(char c : map.toCharArray()){

    temp.add(String.valueOf(c) + s);

    }

    }    

    number = (number-last)/10;

    if(!temp.isEmpty())

    result = temp;

    }

   

    return result;

}