Reverse a singly linked list

I was asked this question during an interview today.  I didn't do well though.  I guess because it was an interview, I had some pressure and could think fast and clearly.  In fact, this question is pretty easy with the recursive.  When I got home, it didn't take me too long to figure out the correct answer.  Here is the code in Java.

class Node {
    Node next;
}

class Util {
    public static void reverseNode(Node node) {
        reverseNode(node, null);
    }
   
    private static void reverseNode(Node node, Node previous) {
        if (node != null) {
            reverseNode(node.next, node);
            node.next = previous;
        }
    }
}

Update:

The recursive solution is easy to understand and implement.  However, you may get a StackOverflow exception if the list is big.  Here is the non-recursive solution:

class Util {
    public static void reverseNode(Node node) {
        Node previous = null;
        while (node != null) {
            Node next = node.next;
            node.next = previous;
            previous = node;
            node = next;
        }
    }
}

Reverse the string word by word, in place

The idea is reverse the string character by character first, then reverse the word character by character.  For example, we have string "abc defg hijk".  The first step is to reverse the string character by character:

"abc defg hijk" ==> "kjih gfed cba"

Then reverse the word in the output string character by character:

"kjih gfed cba" ==> "hijk defg abc"

The run time is O(n) with constant extra space.  Here is the code in java:

    public static void resverseString(char[] input) {
        reverseString(input, 0, input.length - 1);
        int start = 0;
        int end = 0;
        for (char temp : input) {
            if (temp == ' ') {
                reverseString(input, start, end - 1);
                start = end + 1;
            }
            end++;
        }
        reverseString(input, start, end - 1);
    }
   
    private static void reverseString(char[] input, int start, int end) {
        while (start < end) {
            swap(input, start, end);
            start++;
            end--;
        }
    }
   
    private static void swap (char[] input, int i, int j) {
        char temp = input[i];
        input[i] = input[j];
        input[j] = temp;
    }

Weak Reference in Java

Today, during a phone interview, I was asked a question about WeakReference in Java.  I only knew that the weak referenced object can be garbage collected by JVM, and nothing more.  I did a little research, and realized that there are 4 types of references in Java:

1. Strong Reference
2. Soft Reference
3. Weak Reference
4. Phantom Reference

They are in the order from strong to weak references.  3 classes, SoftReference, WeakReference, and PhantomReference are for the last 3 references.  For strong reference, just use new operator. Below is a great blog talking about all 4 references:

Understanding Weak References

Print a sequence of Fibonacci number

The trick is that you should use BigInteger instead of long.  Otherwise, you will get overflow pretty soon.  Here is the code:

import java.math.BigInteger;

public class Fibonacci {
    /**
     * print out a list of Fibonacci sequence to n places.
     * if n = 0, no number will be printed out.  if n = 1, print the first Fibonacci number.
     *
     * @param n the number of Fibonacci to be printed out
     */
    public static void print(int n) {
        BigInteger f0 = BigInteger.ZERO;
        BigInteger f1 = BigInteger.ONE;
        for (int i = 0; i < n; i++) {
           
            System.out.print(f0);
            if (i != n - 1) {
                System.out.print(", ");
            }
            BigInteger temp = f1;
            f1 = f1.add(f0);
            f0 = temp;
        }
    }
}

Update: Another thing to consider is that don't use recursive method to compute Fibonacci number because it is too expensive.  The run time is 2^n to recursively compute Fibancci number.

Print a singly linked list reversely

For a singly linked list, you can only access the list element from the head.  At the first glance, it seems difficulty printing the element reversely (the tail first).  However if you know recursive, the problem becomes quite easy. Here is how to solve this problem in Java:

public class ListUtil {
    public static <T> void  reversePrint(List<T> list) {
        if (list == null || list.isEmpty()) {
            System.out.println("empty list");
        } else {
            Iterator<T> iter = list.iterator();
            reversePrint(iter);
        }
    }
   
    private static <T> void reversePrint(Iterator<T> iter) {
        if (iter.hasNext()) {
            T data = iter.next();
            reversePrint(iter);
            System.out.println(data);
        }
    }
}

Count the number of occurrences of a given key in an array

This was asked in on-site Microsoft interview (see original post).  It seems the answers to this question are not correct.  This question can be solved in O(logN) with binary search.  We know how to find the first occurrence of a given key in a sorted array (see my previous post).  It is easy to modify the algorithm to find the last occurrence of the given key in a sorted array:

    /**
     * find the last occurrence of the target in a sorted array
     * @param input a sorted array
     * @param target
     * @return the last index of target or -1
     */
    public static int findLastOccurence(int[] input, int target) {
        int lower = -1;
        int upper = input.length;

        while (lower + 1 != upper) {
            int  middle = (lower + upper) >>> 1;

            if (input[middle] > target) {
                upper = middle;
            } else {
                lower = middle;
            }
        }

        if (lower != -1 && input[lower] == target) {
            return lower;
        } else {
            return -1;
        }
    }

After knowing indexes of the first and last occurrences, it is easy to know the number of occurrences (or the range).  The run time for finding the number of occurrences is O(logN) since finding first and last occurrences is O(logN).

Find the first occurrence of an integer in sorted array

Normal binary search will return the target randomly if multiple targets are in the given array.  Below is the modified version of binary search, and it is faster than normal binary search since it requires only one comparison with each loop:

    /**
     * find the index of first occurrence of target
     * @param input is a sorted array
     * @param target
     * @return the first index of target or -1
     */
    public static int findFirstOccurence(int[] input, int target) {
        int lower = -1;
        int upper = input.length;

        while (lower + 1 != upper) {
            //avoid overflow.  See here
            int  middle = (lower + upper) >>> 1;

            if (input[middle] < target) {
                lower = middle;
            } else {
                upper = middle;
            }
        }

        if (upper < input.length && input[upper] == target) {
            return upper;
        } else {
            return -1;
        }
    }

The run time of above method is still O(logn).

Implementation of the procedure RANDOM(a, b) that only makes calls to RANDOM(0, 1).

Implementation of the procedure RANDOM(a, b) that only makes calls to RANDOM(0, 1).  This is the question asked in book "Introduction to Algorithm."  I spent some time figuring out the following solution implemented in Java.  The assumption is that we can get random number 0 and 1 which I use Java class Random to generate.

import java.util.Random;
public class RandomGenerator {
    private static Random rand = new Random();

    /**
     * generate a random nubmer between a (inclusive) and b (exclusive)
     */
    public static int random(int a, int b) {
        if (a >= b) {
            throw new UnsupportedOperationException("2nd param must be greater than 1st param");
        }
        return a + generate(b - a);
    }
    /**
     * generate the random between 0 to a (exclusive)
     */
    private static int generate(int a) {
        int run = leastPowerOfTwo(a);

        while (true)  {
            int power = 1;
            int sum = 0;
            for (int i = 0; i < run; i++) {
                sum += random01() * power;
                power *= 2;
            }
            if (sum < a) {
                return sum;
            }
        }
    }

    /**
     * find the least power of 2 which is greater than or equal to the given input a
     */
    private static int leastPowerOfTwo(int a) {
        int power = 0;
        int temp = a;
        while (temp > 0) {
            temp >>>= 1;
            power++;
        }
        //if a is a power of 2
        if ((a & (a - 1)) == 0) {
            power--;
        }
        return power;
    }

    /**
     * a method to randomly generate 0 or 1
     * @return 0 or 1
     */
    private static int random01() {
        return rand.nextInt(2);
    }
}

The trick is to use the binary representation for the generated random number.  For example, to generate a random within [0, 5),  we need to call random(0, 1) 3 times since 2 ^ 3 = 8.  If call random(0, 1) 2 times, we only have 2 ^ 2 = 4 random numbers.  We only need to keep random number less than 5, and if we get a number is greater than 4, we just retry until we get the number is less than 5.   Below is the binary representation for 3 runs of random(0, 1)

#run #3   #2   #1
          0    0     0        0
          0    0     1        1
          0    1     0        2
          0    1     1        3
          1    0     0        4
          1    0     1        5
          1    1     0        6
          1    1     1        7


The informal proof of the above algorithm is that the chance to generate each number is same (1/8).  Since we only keep the number from 0 to 4, the chance to generate the number from 0 to 4 is still same.  Then the above algorithm does generate the correct random numbers.  I ran this program on my machine to generate random number from 7 to 12 (exclusive) for 10 million times, and here is the result:

7:   1997855
8:   2000311
9:   2000140
10: 2000369
11: 2001325

Maximum subarray

This is an interview question:

Given an integer array, find the max sum in any contiguous sub-array.  If all elements are negative, then the sum is 0. The following code just finds the max sum without returning the start and end indexes:

public class MaxSubArray {
    public static int maxSum(int[] input) {
        int currentSum = 0;
        int maxSum = 0;
        for (int i = 0; i < input.length; i++) {
            currentSum = Math.max(currentSum + input[i], 0);
            maxSum = Math.max(maxSum, currentSum);
        }
        return maxSum;
    }
}

The following code returns max sum with starting and ending indexes. If all elements are negative, return start and end indexes as 0 and -1, respectively.

public class MaxSubArray {
    public static MaxSubArrayResult compute(int[] input) {

        MaxSubArrayResult result = new MaxSubArrayResult(0, -1, 0);
        int currentSum = 0;
        int currentStart = 0;
        for (int currentEnd = 0; currentEnd < input.length; currentEnd++) {
            currentSum += input[currentEnd];
            if (currentSum > result.maxSum) {
                result.start = currentStart;
                result.end = currentEnd;
                result.maxSum = currentSum;
            } else if (currentSum < 0){
                currentStart = currentEnd+ 1;
                currentSum = 0;
            }
        }
        return result;
    }

    public static class MaxSubArrayResult {
        public int start;
        public int end;
        public int maxSum;

        public MaxSubArrayResult(int start, int end, int sum) {
            super();
            this.start = start;
            this.end = end;
            this.maxSum = sum;
        }

        @Override
        public String toString() {
            return String.format("start = %d, end = %d, maxSum = %d", start, end, maxSum);
        }
    }
}

The run time for both method is linear (O(n)).