Nᵗʰ Fibonacci Number - Matrices Multiplication

We can find the nᵗʰ Fibonacci number by multiplying matrices. Here is a good explanation of it - Nth Fibonacci Number - multiplying matrices. Let matrix A = [ [ 1 1 ] [ 1 0 ] ]. In order to find the nᵗʰ Fibonacci number all you need is finding the nᵗʰ power of the matrix A.

public class FibonacciMatrixMultiplication {

    static int fibonacciNumber(int n) {
        int A[][] = { { 1, 1 }, { 1, 0 } };
        if (n == 0)
            return 0;
        power(A, n - 1);
        return A[0][0];
    }

    /*
     * Helper function that multiplies 2 matrices X and Y of size 2x2, and puts
     * the multiplication result back in X[][]
     */
    static void multiply(int X[][], int Y[][]) {
        int x = X[0][0] * Y[0][0] + X[0][1] * Y[1][0];
        int y = X[0][0] * Y[0][1] + X[0][1] * Y[1][1];
        int z = X[1][0] * Y[0][0] + X[1][1] * Y[1][0];
        int w = X[1][0] * Y[0][1] + X[1][1] * Y[1][1];
        X[0][0] = x;
        X[0][1] = y;
        X[1][0] = z;
        X[1][1] = w;
    }

    /*
     * Helper function that calculates X[][] raise to the power n and puts the
     * result in X[][]
     */
    static void power(int X[][], int n) {
        int i;
        int A[][] = { { 1, 1 }, { 1, 0 } };
        // n - 1 times multiply the matrix to {{1,0},{0,1}}
        for (i = 2; i <= n; i++) {
            multiply(X, A);
        }
    }

    /**
     * @param args
     */
    public static void main(String[] args) {
        int n = 10;
        System.out.println("Fibonacci number no." + n + " is "
                         + fibonacciNumber(n));
    }

}

For more Fibonacci number problems you can visit "Fibonacci numbers - 4 solutions"

Binary Tree - height and size

What is height and what is size of Binary Tree?
The size of a tree is the size of the root. The size of a node is the number of descendants it has including itself. Therefore, the tree size is the number of all tree nodes.
The height (or depth) of a tree is the length of the path from the root to the deepest node in the tree. A (rooted) tree with only one node (the root) has a depth of zero. Conventionally, an empty tree (tree with no nodes, if such are allowed) has depth and height −1.
In the picture below you see a binary tree with height 3 and size 9.

Binary Tree

Here are two functions calculating the size and the height of a binary tree. The first function is recursive and returns the height:

int heightOfBinaryTree(BinaryTree node) {
    if (node == null) {
        return -1;
    } else {
        return 1 + Math.max(heightOfBinaryTree(node.left),
                            heightOfBinaryTree(node.right));
    }
}

The size solution is recursive, too:

int binaryTreeSize(BinaryTree node) {
    if (node == null) {
        return 0;
    }
    return (binaryTreeSize(node.left) + binaryTreeSize(node.right) + 1);
}

Binary Tree - sum of two nodes (Google Interview Question)

Here is another Google Interview problem:

Given a BST and a value x. Find two nodes in the tree whose sum is equal x. Additional space: O(height of the tree). It is not allowed to modify the tree.

The solution uses two stacks and the size of the binary tree. The approach is recursive and is similar to the binary search algorithm in arrays. The two stacks contain candidate answer numbers and on each iteration based on a calculation we pop or add new number in a stack. The binary tree size is used in cases where no answer exists. In these cases the algorithm starts endless loop.

void algorithm(Stack stk1, Stack stk2,
   double x, int size) {
    if (size == 0){
        System.out.println("No answer is found!");
        return;
    }
    if (!stk1.isEmpty() && !stk2.isEmpty()) {
        if (stk1.peek().data + stk2.peek().data == x) {
            System.out.println("Nodes are:\n" + stk1.peek().data + "\n"
            + stk2.peek().data);
            return;
        }
        if (stk1.peek().data + stk2.peek().data > x) {
            if(stk2.size()==1){
                BinaryTree node = stk2.pop();
                stk2.add(node);
                addRightNodes(stk2, node.getLeft());
            } else {
                addLeftNodes(stk2, stk2.pop());
            }    
        } else if (stk1.peek().data + stk2.peek().data < x) {
            if(stk1.size()==1){
                BinaryTree node = stk1.pop();
                stk1.add(node);
                addLeftNodes(stk1, node.getRight());
            } else {
                addRightNodes(stk1, stk1.pop());
            }    
        }
    }
    algorithm(stk1, stk2, x, --size);
}

See also the "Sum of nodes at odd and even levels of Binary Tree" problem.

Brackets - number of possible soltions

Given a string containing only the symbols '?', '(' and ')'. You can replace the '?' with either '(' or ')'. Your task is to write a function that tells the number of possible solutions where brackets are used correctly.
Example:
Given the string "?(????)?" the function should return 6.
The correct possible solutions are:
((()()))
(((())))
(())(())
(()(()))
((())())
(()()())

Here is one recursive solution. Three parameters are passed to the function - the given string, the current index of the string and count - an integer calculated based on the brackets - if '(' we add 1 to count and if ')' we decrease count by one. We start iteration over the string's characters starting from the first. If the current symbol is '(' or ')', the the count is recalculated and the iteration goes on. If the current symbol is '?', then there are 2 possibilities either '(' or ')' and that gives 2 branches of the recursion.

long bracket(String str, int index, int count) {
    int n = str.length() - 1;
    long solution = 0;

    if (index > n) {
        if (count == 0)
            solution = 1;
        else
            solution = 0;
    } else {
        if (count < 0)
            solution = 0;
        else

        if (str.charAt(index) == '(')
            solution = bracket(str, index + 1, count + 1);
        else if (str.charAt(index) == ')')
            solution = bracket(str, index + 1, count - 1);
        else if (str.charAt(index) == '?') {
            solution = (bracket(str, index + 1, count + 1) + bracket(str, index + 1, count - 1));
        }
    }

    return solution;
}

The next solution uses the Dynamic Programming method. Here we create a table where we build a row based on the previous row. Here is an explanation of the table. Let's look the string "??(???". We consider two parameters - our two dimensions of the table:
- count: number_of_opening_brackets - number_of_closing_brackets
- index: this is the index of the current character we look at
If the last one is a "?" or ')' - there is one possible solution and if it is '(' there is no solution. That means the last row of our table will be 0, 1, 0, 0... Only in case the last symbol is '(', there will be, obviously, no solutions at all. This is a special case. Imagine, we are now considering the penultimate symbol. Based on the count number and the symbol staying in this position, we calculate the penultimate row. In our case the penultimate symbol is '?'. If count is 0, then we place '(' instead of the '?' and continue. If count is 1, there is no way we can have count 0 in the end no matter what we place instead of the '?'. If count is 2, then we write ')' in place of the '?' and continue. The rest of the count values - 3, 4, 5, won't give a solution. That means our penultimate row will be 1, 0, 1, 0, 0...
We actually build row i based on row (i+1). The logic is the following:
if the symbol is ')' then cell[i][j] = cell[(i + 1)][j - 1];
if the symbol is '(' then cell[i][j] = cell[(i + 1)][j + 1];
if the symbol is '?' then cell[i][j] = cell[(i + 1)][j - 1] + cell[(i + 1)][j + 1];

Our answer is the value in cell[0][0].

long bracketDP(String str) {
    int strLength = str.length() - 1;

    for (int i = 0; i <= strLength; i++) {
        arr[strLength][i] = 0;
    }

    if (str.charAt(strLength) != '(')
        arr[strLength][1] = 1;

    for (int i = strLength - 1; i >= 0; i--) {// index
        for (int j = 0; j <= strLength; j++) {// count
            if (j == 0) {
                if (str.charAt(i) == ')')
                    arr[i][j] = 0;
                if (str.charAt(i) == '(')
                    arr[i][j] = arr[(i + 1)][j + 1];
                if (str.charAt(i) == '?') {
                    arr[i][j] = arr[(i + 1)][j + 1];
                }
            } else {
                if (str.charAt(i) == ')')
                    arr[i][j] = arr[(i + 1)][j - 1];
                if (str.charAt(i) == '(')
                    arr[i][j] = arr[(i + 1)][j + 1];
                if (str.charAt(i) == '?') {
                    arr[i][j] = arr[(i + 1)][j - 1] + arr[(i + 1)][j + 1];
                }
            }
        }
    }
    return arr[0][0];
}

In fact, constructing each row all we need is the previous row. It means that we can do with memory reserved for only two rows - we use one to construct the second and then we use the second and write the results to the first one. Then we again use row one to construct the second row, and so on. Here is an optimization we can do:

long bracketDP2(String str) {
    int strLength = str.length() - 1;

    for (int i = 0; i <= strLength; i++) {
        arr[strLength % 2][i] = 0;
    }

    if (str.charAt(strLength) != '(')
        arr[strLength % 2][1] = 1;

    for (int i = strLength - 1; i >= 0; i--) {// index
        for (int j = 0; j <= strLength; j++) {// count
            if (j == 0) {
                if (str.charAt(i) == ')')
                    arr[i % 2][j] = 0;
                if (str.charAt(i) == '(')
                    arr[i % 2][j] = arr[(i + 1) % 2][j + 1];
                if (str.charAt(i) == '?') {
                    arr[i % 2][j] = arr[(i + 1) % 2][j + 1];
                }
            } else {
                if (str.charAt(i) == ')')
                    arr[i % 2][j] = arr[(i + 1) % 2][j - 1];
                if (str.charAt(i) == '(')
                    arr[i % 2][j] = arr[(i + 1) % 2][j + 1];
                if (str.charAt(i) == '?') {
                    arr[i % 2][j] = arr[(i + 1) % 2][j - 1] + arr[(i + 1) % 2][j + 1];
                }
            }
        }
    }
    return arr[0][0];
}

For more brackets problems visit "Bracket combinations"

Bracket combinations (Google Interview Question)

Write a function that prints all combinations of well-formed brackets. The input is a number which says how many pairs of brackets will the different outputs have. For Brackets(3) the output would be:
((()))  (()())  (())()  ()(())  ()()().

The solution below uses recursion. The logic here is very simple - every output is constructed starting with its first symbol. On each step a new symbol is added following these rules:

• rule 1: if the number of opened brackets is equal to the number of closing brackets, then the only next possible symbol to add is '('
• rule 2: if the number of opened brackets is more than the number of closing brackets, then there are two options - either we add ')' or '('
• rule 3: if the number of opened brackets is more than half the number of all brackets, then the construction went wrong and we break the whole case
• rule 4: if the number of opened brackets is less than the number of closing brackets, then the construction went wrong and we break the whole case
• rule 5: the last symbol of the output cannot be '('

private void Brackets(String output, int open, int close, int total) {
    if (output.length() == total * 2 && output.charAt(total * 2 - 1) != '(') {
        System.out.println(output);
    } else if (open > total || open < close) {
        return;
    } else {
        if ((open == close)) {
            Brackets(output + "(", open + 1, close, total);
        }
        if ((open > close)) {
            Brackets(output + "(", open + 1, close, total);
            Brackets(output + ")", open, close + 1, total);
        }
    }
}

public void Brackets(int total) {
    Brackets("", 0, 0, total);
}

This is an Interview Question for Software Engineers at Google. Here you can find more information.

Delete node in LinkedList

Delete a given node in a singly linked list. You don't have an access to the root node of the list. You have only access to the given node. Let's suppose this is your definition of a node.

class Node {
    Node next;
    int data;
}

Deleting a node in the middle of a singly linked list could happen if you copy the value from the next node over the given node and then to delete the next node.

public static void deleteMiddleNode(Node n){
    if(n == null){
        System.out.println("Node value is incorrect");
    }
    // in case of last element
    if(n.next == null){
        n = null;
    }
  
    Node next = n.next;
    n.data = next.data;
    n.next = next.next;
}

Travel from string to string (Google Interview question)

Google Interview Question (http://www.careercup.com/question?id=14947965):

Given a source string and a destination string write a program to display sequence of strings to travel from source to destination. Rules for traversing:
1. You can only change one character at a time
2. Any resulting word has to be a valid word from dictionary
Example: Given source word CAT and destination word DOG , one of the valid sequence would be
CAT -> COT -> DOT -> DOG
Another valid sequence can be
CAT -> COT - > COG -> DOG
One character can change at one time and every resulting word has be a valid word from dictionary

The solution here includes not only functions but global variables as well.

public class SourceToDestinationString {
    // Container for the valid words
    HashSet dictionary = null;
    // Container for words already passed by a word sequence
    HashSet visited;

    public SourceToDestinationString() {
        super();
        visited = new HashSet();
        dictionary = new HashSet();
        initDictionary();
    }

    private void initDictionary() {
        // Add the wrods in the dictionary
    }

    // Returns all valid words suitable for the next step of the path
    private ArrayList generateWords(String source, int position) {
        if (position < 0 || position >= source.length())
            return null;
        ArrayList result = new ArrayList();
        for (char ch = 'A'; ch <= 'Z'; ch++) {
            StringBuffer tmpWord = new StringBuffer(source);
            tmpWord.setCharAt(position, ch);
            String word = tmpWord.toString();
            if (dictionary.contains(word)) {
                result.add(word);
            }
        }

        return result;
    }

    // The sequence of words is written in the stack 'path' 
    public void sourceToDestinationString(Stack path, String destination) {
        String source = path.peek();
        if (source.equals(destination)) {
            System.out.print("Solution is ");
            System.out.println(path);
            return;
        }

        visited.add(source);

        for (int i = 0; i < source.length(); i++) {
            ArrayList words = generateWords(source, i);
            for (String nextWord : words) {
                if (visited.contains(nextWord))
                    continue;
                path.push(nextWord);
                sourceToDestinationString(path, destination);
                path.pop();
            }
        }
  
        visited.remove(source);
    }
}