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.

Chinese number system

This problem comes from a Google interview (http://www.careercup.com/question?id=14942235). You probably know that the number "4" is considered unlucky number in China. Here is the problem:

Number '4' is considered an unlucky number in China because it is nearly homophonous to the word "death". For this reason, there is a new number system similar to the decimal system but has no '4'. For example: 1,2,3,5,6,7...13,15...23,25...33,35...39,50...
Here 5 is 4 in decimal system, and 15 is 13... Write a function which takes as an input a positive number (Chinese number) and provides an output number (decimal number or error):
1 -> 1;
2 -> 2;
5 -> 4;
4 -> illegal;
15 -> 13;

Solution:

public int chineseNumberToDecimal(String chineseNumber) {
    // check the input
    if(chineseNumber.contains("4")){
        throw new IllegalArgumentException("Digit 4 is illegal");
    }
  
    // convert to nonary number
    char[] chineseCharArray = chineseNumber.toCharArray();
    for (int i = 0; i < chineseCharArray.length; i++) {
        if (chineseCharArray[i] >= '4' && chineseCharArray[i] <= '9') {
            chineseCharArray[i]--;
        }
    }
    String nonaryNumber = new String(chineseCharArray);
  
    // get the decimal version of the nonary number
    int decimalNumber = Integer.valueOf(nonaryNumber, 9);
  
    return decimalNumber;
}

The whole idea is based on that a Chinese number is a number in the nonary system and its digits are: 0, 1, 2, 3, 5, 6, 7, 8, 9. The ordinary nonary system has the digits: 0, 1, 2, 3, 4, 5, 6, 7, 8. Therefore we can convert the given Chinese number into an ordinary number in the nonary system. Then it is easy to get the decimal number having an ordinary nonary number.

Can you think of the opposite function - decimalToChineseNumber?

How to find k-th element from the end of a linked list?

The solution below uses recursion to get the number of elements in the linked list and then prints only the value at the k-th node from end of the Linked List.

public static void kthElement(LinkedList list, int k) {
    ListIterator iterator = list.listIterator();
    handleNextElement(iterator, k);
}

private static int handleNextElement(ListIterator iterator, int k) {
    int elementValue = 0;
    if (!iterator.hasNext()) {
        return 0;
    }

    elementValue = iterator.next();
    int count = handleNextElement(iterator, k) + 1;

    if (count == k) {
        System.out.println(elementValue);
    }

    return count;
}

k-th node from end

Another solution is non-recursive where you run two runners/iterators in parallel with distance k between them.

Integer kthElement(LinkedList list, int k) {
    if (k < 1 || k > list.size()) {
        return null;
    }

    ListIterator iterator = list.listIterator();
    for (int i = 0; i < k; i++) {
        if (iterator.hasNext()) {
            iterator.next();
        } else {
            return null;
        }
    }

    ListIterator iterator2 = list.listIterator();
    while (iterator.hasNext()) {
        iterator.next();
        iterator2.next();
    }

    Integer result = iterator2.next();
    return result;
}

2 iterators with distance k between them

This solution takes O(n) time and O(1) space.