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);
    }
}

Fibonacci numbers - 4 solutions

Find the n-th Fibonacci number. The Fibonacci numbers are integers 0, 1, 1, 2, 3, 5, 8, 13, 21, ...
Wikipedia says:

By definition, the first two numbers in the Fibonacci sequence are 0 and 1 (alternatively, 1 and 1), and each subsequent number is the sum of the previous two. 

For example the 7-th Fibonacci number in the sequence is 8. Here are a few solutions. The first one is a trivial one and follows the definition - i.e. it uses recursion.

long fibonacciRecursive(int n) {
    if (n == 0 || n == 1) {
        return n;
    }
    return fibonacciRecursive(n - 1) + fibonacciRecursive(n - 2);
}

The second solution is iterative. A drawback here is that the size of the array which is used to store the Fibonacci numbers needs to be defined statically.

long fibonacciIterative(int n) {
    int size = 100;
    long[] fibonacciNumbers = new long[size + 1];
    fibonacciNumbers[0] = 0;
    fibonacciNumbers[1] = 1;
  
    for (int i = 2; i <= n; i++) {
        fibonacciNumbers[i] = fibonacciNumbers[i - 1]
                            + fibonacciNumbers[i - 2];
    }
    return fibonacciNumbers[n];
}

The third solution is again iterative. The difference here is that it uses an array with size 3. This is a very elegant and optimized solution.

long fibonacciIterativeLowMem(int n) {
    int[] fibonacciNumbers = new int[3];
    fibonacciNumbers[0] = 0;
    fibonacciNumbers[1] = 1;

    for (int i = 2; i <= n; i++) {
        fibonacciNumbers[i % 3] = fibonacciNumbers[(i - 1) % 3]
                                + fibonacciNumbers[(i - 2) % 3];
    }
    return fibonacciNumbers[n % 3];
}

Here is one more solution that uses an optimization called memoization. The idea here is that we avoid the calculation of the tasks we already had calculated.

long fibonacciMemoization(int n) {
    int size = 100;
    long[] fibonacciNumbers = new long[size+1];
    fibonacciNumbers[0] = 0;
    fibonacciNumbers[1] = 1;
    for (int i = 2; i < size; i++) {
        fibonacciNumbers[i] = -1;
    }
  
    if (fibonacciNumbers[n] != -1) {
        return fibonacciNumbers[n];
    } else {
        fibonacciNumbers[n] = fibonacciMemoization(n - 1)
                            + fibonacciMemoization(n - 2);
        return fibonacciNumbers[n];
    }
}

Reverse a LinkedList

Given a singly linked list. You have to revers it.

The first solution uses recursion.

Node reverseList(Node previous, Node current) {
    Node tmp;
    if (current.next == null) {
        current.next = previous;
        return current;
    }
    tmp = reverseList(current, current.next);
    current.next = previous;
    return tmp;
}

The second solution is non-recursive.

Node reverse(Node current) {
    Node tmp;
    Node previous = null;
    while (current != null) {
        tmp = current.next;
        current.next = previous;
        previous = current;
        current= tmp;
    }
    return previous;
}

Sum of nodes at odd and even levels of Binary Tree

Given a Binary Tree, write a function which calculates the difference between the sum of node values at odd levels and sum of node values at even levels, i.e. function(BinaryTree) = (sum of values of nodes at odd height) - (sum of values of node at even height). Consider the root node is at height 1.

int calculateDifference(BinaryTree root) {
    if (root == null) {
        return 0;
    }
    int result = root.getData() - calculateDifference(root.getLeft())
              - calculateDifference(root.getRight());
    return result;
};

The solution is short and uses recursion. The idea is that you negate all levels under the current one (the level of the current node) and you do that on each step of the recursion.

sum[l1] - (sum[l2] - (sum[l3] - (sum[l4] - ... = sum[l1] - sum[l2] + sum[l3] - sum[l4]...

Deifference between sum of nodes on even height and sum of nodes on odd height

Determine if a number is power of 2

How can you check if a number is power of 2? This is not so hard to solve and in fact there are many ways you can implement a solution. One of the most obvious solutions is probably the one where you repeatedly divide the number by 2 until you end with 1 (in case the number is power of 2) or you reach an odd number higher than 1 (in case the number is not power of 2).

boolean isPowerOf2(int x) {
    while (((x % 2) == 0) && x > 1) {
        x /= 2;
    }
    return (x == 1);
}

A lot nicer solution is the one using bit operation:

boolean isPowerOf2(int x) {
    return x > 0 && (x & (x - 1)) == 0;
}

Here the idea is that every number that is a power of 2 has exactly one bit set to 1 in its binary representation and if you subtract 1 from this number you get a number where all first bits (starting from right) are 1 in the binary representation:

2    =  00000010     2  - 1 = 1  = 00000001
4    =  00000100     4  - 1 = 3  = 00000011
8    =  00001000     8  - 1 = 7  = 00000111
16   =  00010000     16 - 1 = 15 = 00001111
...

And if you do a bitwise AND (operator '&') on the original number and the original number subtracted by 1, we get 0:

2  & 1  = 00000010 & 00000001 = 0
4  & 3  = 00000100 & 00000011 = 0
8  & 7  = 00001000 & 00000111 = 0
16 & 15 = 00010000 & 00001111 = 0
...

Rotate Matrix

Here is another Google interview question (http://www.careercup.com/question?id=14891673):

Given a matrix represented as int[n][n], rotate it 90 degrees clockwise in-place. (In-place means minimal extra memory to be used, i.e. don't make a new array to copy into). Rotate clockwise means top-row becomes right-column, right column becomes bottom-row etc.

In the solution uses one extra integer variable to rotate elements in each iteration. There are two for loops - the outer one deals with one layer of the matrix per iteration, while the inner one deals with rotation of the elements of the layers.

void rotateMatrix(int a[][]) {
    int n = a.length;
    if (n <= 1) {
        return; // nothing to do
    }

    /* layers */
    for (int i = 0; i < n / 2; i++) {
        /* elements */
        for (int j = i; j < n - i - 1; j++) {
            int saved = a[i][j];
            a[i][j] = a[n - j - 1][i];
            a[n - j - 1][i] = a[n - 1 - i][n - 1 - j];
            a[n - 1 - i][n - 1 - j] = a[j][n - 1 - i];
            a[j][n - 1 - i] = saved;
        }
    }
}

In the picture below you can see the different layers in different colours. It shows what happens after each iteration of the outer for loop.