Most import aspects of software development

After a few years of software development, it is a good time to recap what are the most important aspects that I should be aware of when working any project.

1. The code base should be well tested that it has unit-tests, integration/acceptance-tests, external/smoke-tests. Unit test is about testing a single class by mocking its dependencies if necessary. Integration or acceptance tests should be testing the APIs provided by your application, particular front-to-back workflows, story-based features (as someone, I should be able to do something, etc.). External or smoke tests are verifying that the contracts between your application and your external dependencies are intact. There are a few reasons why automated tests are important:
   1. developers have the confidence to refactor or make functional changes as they can run the automated tests to check whether there are any breaking changes
   2. no more painful and error prone manual tests conducted by the QA team -- cost savings, although UAT (User-Acceptance Test) is still required
   3. greatly shortens the release cycle because you spend a lot less time doing the manual tests
2. Modeling of the business objects is important because it not only affects how easy it is to query your business objects from the persistent layer, but also the performance of querying. One of the project that I worked on was storing a map of data into an oracle database as a CLOB data type (imagine a map is marshalled as XML string and stored as a DB column). It turned out to be rather inefficient to query any field inside that CLOB column, as you have to load the whole CLOB to your application!
3. Availability and scalability are also crucial to any production system. Even Facebook does not guarantee that their query engine is available 100% of time (as they still have to do the manual failover of their name nodes, part of their Hadoop DFS cluster, from time to time). I won't treat Facebook as a mission critical application that has to be available all the time, but you can sense that to achieve a 100% availability, you will have to really think about your failover or DR (Disaster-Recovery) plan. Scalability is a tricky topic, as you can either scale horizontally by adding more nodes, or scale vertically by adding more cores/memories to the existing nodes (further reading on Amdahl's law). Depends on where the bottleneck of growth is, you might have database scalability, application scalability, caching scalability, etc.

An efficient Stack implementation with getMin() and getMax() methods

When we use stack to keep a collection of numbers, we might want to know what are the minimum and maximum numbers in the stack. 

Suppose we are pushing {72,12,55,78,22,34} into a stack, this is what happens

Action	Stack Elements (Top ... Bottom)	Min	Max
push(72)	72	72	72
push(12)	12,72	12	72
push(55)	55,12,72	12	72
push(78)	78,55,12,72	12	78
push(22)	22,78,55,12,72	12	78
push(34)	34,22,78,55,12,72	12	78

If we pop the stack above 3 times, the max should change to 72; if we pop 2 more times, the min should change to 72. It sounds like we need a data structure that keeps the current min and max when we push or pop the stack. Indeed, a stack is a perfect choice here. When pushing a number to the stack, we also push the current min and max values into the min and max stacks respectively. Similarly, when poping out a number from the stack, we also pop out from the min and max stacks, such that the top of the min and max stacks will always have the min and max values of the current stack respectively.

The complexity of the getMin() and getMax() methods are O(1), regardless of how many items are in the stack, same as the push(item) and pop() methods.

Here is an implementation of the Stack with getMin() and getMax() methods

import java.util.Stack;
import java.util.concurrent.locks.ReentrantReadWriteLock;

public class SmartStack<E extends Comparable<E>> {

    private ReentrantReadWriteLock readWriteLock = new ReentrantReadWriteLock();
    private ReentrantReadWriteLock.ReadLock readLock = readWriteLock.readLock();
    private ReentrantReadWriteLock.WriteLock writeLock = readWriteLock.writeLock();

    private Stack<E> mins = new Stack<E>();
    private Stack<E> maxs = new Stack<E>();
    private Stack<E> delegate = new Stack<E>();

    public E push(E item) {
        writeLock.lock();
        try {
            // stores the current min to the mins stack
            if (mins.isEmpty() || (!mins.isEmpty() && item.compareTo(mins.peek()) < 0)) {
                mins.push(item);
            } else {
                mins.push(mins.peek());
            }

            // stores the current max to the maxs stack
            if (maxs.isEmpty() || (!maxs.isEmpty() && item.compareTo(maxs.peek()) > 0)) {
                maxs.push(item);
            } else {
                maxs.push(maxs.peek());
            }

            return delegate.push(item);
        } finally {
            writeLock.unlock();
        }
    }

    public E pop() {
        writeLock.lock();
        try {
            E item = delegate.pop();
            // pop both mins and maxs stacks, such that peeking on them will tell us the current min or max
            mins.pop();
            maxs.pop();
            return item;
        } finally {
            writeLock.unlock();
        }
    }

    public E peek() {
        readLock.lock();
        try {
            return delegate.peek();
        } finally {
            readLock.unlock();
        }
    }

    public E getMin() {
        readLock.lock();
        try {
            return mins.peek();
        } finally {
            readLock.unlock();
        }
    }

    public E getMax() {
        readLock.lock();
        try {
            return maxs.peek();
        } finally {
            readLock.unlock();
        }
    }

    public boolean empty() {
        readLock.lock();
        try {
            return delegate.empty();
        } finally {
            readLock.unlock();
        }
    }

    public int search(E item) {
        readLock.lock();
        try {
            return delegate.search(item);
        } finally {
            readLock.unlock();
        }
    }
    
}

Here is the unit test of the above class written in Groovy

import org.junit.Before
import org.junit.Test

class SmartStackTest {

    SmartStack stack

    @Before
    public void before() {
        stack = new SmartStack()
        stack.push(72)
        stack.push(12)
        stack.push(55)
        stack.push(78)
        stack.push(22)
        stack.push(34)
    }

    @Test
    public void canGetCurrentMinValue() {
        assert stack.min == 12

        5.times { stack.pop() }

        assert stack.min == 72
    }

    @Test
    public void canGetCurrentMaxValue() {
        assert stack.max == 78

        4.times { stack.pop() }

        assert stack.max == 72
    }

    @Test
    public void canPeek() {
        assert stack.peek() == 34
    }

    @Test
    public void isEmpty() {
        assert !stack.empty()
    }

    @Test
    public void canSearch() {
        // the 1-based position from the top of the stack where the object is located
        assert stack.search(34) == 1
        assert stack.search(22) == 2
        assert stack.search(78) == 3
        assert stack.search(55) == 4
        assert stack.search(12) == 5
        assert stack.search(72) == 6
        // not in the stack should return -1
        assert stack.search(11112) == -1
    }
    
}

Sorting objects with one-way dependency using Topological Sort with Directed Graphs

Suppose there are a bunch of objects to be evaluated, each of which might depend on a number of other objects being evaluated first before it can be evaluated. The objects being depended on might depend on other objects. There is no cyclic dependency that object A depends on object B, and object B depends on object C, and object C depends on object A.

To solve this problem, we want to sort these objects such that when traversing through these objects, they should be ready for evaluation and their dependencies, if applicable, should have been evaluated. The sorting algorithm and data structure that are applicable for this problem is Topological Sort with Directed Graphs.

If the edges in a graph have a direction, the graph is called a directed graph, as shown above. The arrows in the figure show the direction of the edges. We also include two vertices here to represent isolated objects that don't depend on other objects.

The arrows in the figure represent evaluation direction. For example, to evaluate E, we must first evaluate A and B. To evaluate H, we might want a sorted collection like this:

ADBECFDGH or ADGBECFH

There are many other possible ordering, depending on the approach you take to implement the topological sort.

DirectedGraph.java

import java.util.*;

public class DirectedGraph<T> implements Iterable<T> {

    // key is a Node, value is a set of Nodes connected by outgoing edges from the key
    private final Map<T, Set<T>> graph = new HashMap<T, Set<T>>();

    public boolean addNode(T node) {
        if (graph.containsKey(node)) {
            return false;
        }

        graph.put(node, new HashSet<T>());
        return true;
    }

    public void addNodes(Collection<T> nodes) {
        for (T node : nodes) {
            addNode(node);
        }
    }

    public void addEdge(T src, T dest) {
        validateSourceAndDestinationNodes(src, dest);

        // Add the edge by adding the dest node into the outgoing edges
        graph.get(src).add(dest);
    }

    public void removeEdge(T src, T dest) {
        validateSourceAndDestinationNodes(src, dest);

        graph.get(src).remove(dest);
    }

    public boolean edgeExists(T src, T dest) {
        validateSourceAndDestinationNodes(src, dest);

        return graph.get(src).contains(dest);
    }

    public Set<T> edgesFrom(T node) {
        // Check that the node exists.
        Set<T> edges = graph.get(node);
        if (edges == null)
            throw new NoSuchElementException("Source node does not exist.");

        return Collections.unmodifiableSet(edges);
    }

    public Iterator<T> iterator() {
        return graph.keySet().iterator();
    }

    public int size() {
        return graph.size();
    }

    public boolean isEmpty() {
        return graph.isEmpty();
    }

    private void validateSourceAndDestinationNodes(T src, T dest) {
        // Confirm both endpoints exist
        if (!graph.containsKey(src) || !graph.containsKey(dest))
            throw new NoSuchElementException("Both nodes must be in the graph.");
    }

}

TolopogicalSort.java

import java.util.ArrayList;
import java.util.HashSet;
import java.util.List;
import java.util.Set;

public class TopologicalSort {

    public static <T> List<T> sort(DirectedGraph<T> graph) {
        DirectedGraph<T> reversedGraph = reverseGraph(graph);

        List<T> result = new ArrayList<T>();
        Set<T> visited = new HashSet<T>();

        /* We'll also maintain a third set consisting of all nodes that have
         * been fully expanded.  If the graph contains a cycle, then we can
         * detect this by noting that a node has been explored but not fully
         * expanded.
         */
        Set<T> expanded = new HashSet<T>();

        // Fire off a Depth-First Search from each node in the graph
        for (T node : reversedGraph)
            explore(node, reversedGraph, result, visited, expanded);

        return result;
    }


    /**
     * Recursively performs a Depth-First Search from the specified node, marking all nodes
     * encountered by the search.
     *
     * @param node     The node to begin the search from.
     * @param graph    The graph in which to perform the search.
     * @param result   A list holding the topological sort of the graph.
     * @param visited  A set of nodes that have already been visited.
     * @param expanded A set of nodes that have been fully expanded.
     */
    private static <T> void explore(T node, DirectedGraph<T> graph, List<T> result, Set<T> visited, Set<T> expanded) {
        if (visited.contains(node)) {
            // if this node has already been expanded, then it's already been assigned a
            // position in the final topological sort and we don't need to explore it again.
            if (expanded.contains(node)) return;

            // if it hasn't been expanded, it means that we've just found a node that is currently being explored,
            // and therefore is part of a cycle.  In that case, we should report an error.
            throw new IllegalArgumentException("A cycle was detected within the Graph when exploring node " + node.toString());
        }

        visited.add(node);

        // recursively explore all predecessors of this node
        for (T predecessor : graph.edgesFrom(node))
            explore(predecessor, graph, result, visited, expanded);

        result.add(node);
        expanded.add(node);
    }

    private static <T> DirectedGraph<T> reverseGraph(DirectedGraph<T> graph) {
        DirectedGraph<T> result = new DirectedGraph<T>();

        // Add all the nodes from the original graph
        for (T node : graph) {
            result.addNode(node);
        }

        // Scan over all the edges in the graph, adding their reverse to the reverse graph.
        for (T node : graph) {
            for (T endpoint : graph.edgesFrom(node)) {
                result.addEdge(endpoint, node);
            }
        }

        return result;
    }

}

Below demonstrate the setup of the directed graph and will print out the sorted result.

    public static void main(String[] args) {
        DirectedGraph graph = new DirectedGraph()
        graph.addNode("A");
        graph.addNode("B");
        graph.addNode("C");
        graph.addNode("D");
        graph.addNode("E");
        graph.addNode("F");
        graph.addNode("G");
        graph.addNode("H");
        graph.addNode("I");
        graph.addNode("J");

        graph.addEdge("A", "D");
        graph.addEdge("A", "E");
        graph.addEdge("B", "E");
        graph.addEdge("C", "F");
        graph.addEdge("D", "G");
        graph.addEdge("E", "H");
        graph.addEdge("F", "H");
        graph.addEdge("G", "H");

        List sorted = TopologicalSort.sort(graph)

        System.out.println(sorted)
    }

Merge Sort in Java

The merge sort is a much more efficient sorting algorithm than those simple ones, for example, bubble sort, selection sort, and insertion sort. While the simple sorting algorithms have O(N²) complexity, the merge sort is O(N*logN). 

The merge sort routine tries to break down an array into 2 sub-arrays, sort these sub-arrays, and merge them back, in a recursive way, as you shall see in the implementation below, as well as the graph below.

 

import java.util.Arrays;
import java.util.Random;

public class MergeSortTest {

    static int numberOfElements = 10;
    static int maxValue = 100;

    public static void main(String[] args) {
        int[] original = createArrayWithRandomValues();
        // workspace array is used to keep the partial sorted results
        int[] workspace = new int[original.length];
        mergeSort(original, workspace, 0, numberOfElements - 1);

        System.out.println("The sorted array is " + Arrays.toString(original));
    }

    private static int[] createArrayWithRandomValues() {
        Random random = new Random();
        int[] original = new int[numberOfElements];
        for (int i = 0; i < numberOfElements; i++) {
            original[i] = random.nextInt(maxValue);
        }
        System.out.println("The original array is " + Arrays.toString(original));
        return original;
    }

    private static void mergeSort(int[] original, int[] workSpace, int lowerBound, int upperBound) {
        if (lowerBound != upperBound) {
            // find midpoint
            int mid = (lowerBound + upperBound) / 2;
            // sort lower half
            mergeSort(original, workSpace, lowerBound, mid);
            // sort upper half
            mergeSort(original, workSpace, mid + 1, upperBound);
            // merge them
            merge(original, workSpace, lowerBound, mid, upperBound);
        }
    }

    private static void merge(int[] original, int[] workSpace, int lowerBound, int middle, int upperBound) {
        // Copy both parts into the workspace array
        System.arraycopy(original, lowerBound, workSpace, lowerBound, upperBound + 1 - lowerBound);

        int leftPointer = lowerBound;
        int rightPointer = middle + 1;
        int originalPointer = lowerBound;

        // Copy the smallest values from either the left or the right side back to the original array
        while (leftPointer <= middle && rightPointer <= upperBound) {
            if (workSpace[leftPointer] <= workSpace[rightPointer]) {
                // copy and move the pointer on workspace to the next smallest value on left (if there is any)
                original[originalPointer++] = workSpace[leftPointer++];
            } else {
                // copy and move the pointer on workspace to the next smallest value on right (if there is any)
                original[originalPointer++] = workSpace[rightPointer++];
            }
        }
        // Copy the rest of the left side of the array into the target array
        while (leftPointer <= middle) {
            original[originalPointer++] = workSpace[leftPointer++];
        }

        // if there are elements left in the right side of the workspace, those
        // are the largest values of the merged array, so no action is required
    }
    
}

Insertion Sort in Java

Insertion sort is about twice as fast as the bubble sort, and faster than selection sort.

In an insertion sort routine, we will pick a marker (starting from index=1), store the marked number, and compare the marked number with its neighbours on the left. Shift all the neighbours, which are larger than the marked number, one position to the right. After the shift, insert the marked number to the empty slot. Repeat this procedure until the marker index points to the last number on the right.

Below demonstrates one of the implementations of the insertion sort algorithm.

import java.util.Arrays;
import java.util.Random;

public class InsertionSortTest {

    static int numberOfElements = 10;
    static int maxValue = 100;

    public static void main(String[] args) {
        int[] original = createArrayWithRandomValues();

        insertionSort(original);

        System.out.println("The sorted array is " + Arrays.toString(original));
    }

    private static int[] createArrayWithRandomValues() {
        Random random = new Random();
        int[] original = new int[numberOfElements];
        for (int i = 0; i < numberOfElements; i++) {
            original[i] = random.nextInt(maxValue);
        }
        System.out.println("The original array is " + Arrays.toString(original));
        return original;
    }

    private static void insertionSort(int[] original) {
        int markerIndex, emptySlotIndex;
        for (markerIndex = 1; markerIndex < original.length; markerIndex++) {
            int marked = original[markerIndex]; // use a temp variable to store the marked number
            emptySlotIndex = markerIndex;
            while (emptySlotIndex > 0 && original[emptySlotIndex - 1] >= marked) {
                original[emptySlotIndex] = original[emptySlotIndex - 1]; // shift element right
                emptySlotIndex--; // moves the empty slot index one position to the left
            }
            original[emptySlotIndex] = marked; // insert marked element
        }
    }
    
}

Selection Sort in Java

Selection sort is slightly faster than bubble sort because the number of required swaps is reduced from O(N²) to O(N), while the number of comparisons remains O(N²).

Below demonstrates one of the implementations of the selection sort algorithm.
 

import java.util.Arrays;
import java.util.Random;

public class SelectionSortTest {

    static int numberOfElements = 10;
    static int maxValue = 100;

    public static void main(String[] args) {
        int[] original = createArrayWithRandomValues();

        selectionSort(original);

        System.out.println("The sorted array is " + Arrays.toString(original));
    }

    private static int[] createArrayWithRandomValues() {
        Random random = new Random();
        int[] original = new int[numberOfElements];
        for (int start = 1; start <= numberOfElements; start++) {
            original[start - 1] = random.nextInt(maxValue);
        }
        System.out.println("The original array is " + Arrays.toString(original));
        return original;
    }


    private static void selectionSort(int[] original) {
        int outer, inner, minIndex;
        for (outer = 0; outer < original.length - 1; outer++) { // from 1st element to next-to-last element
            minIndex = outer; // each round the min index starts from the outer index
            for (inner = outer + 1; inner < original.length; inner++) { // from outer + 1 element to the last element
                if (original[inner] < original[minIndex]) { // remember the index for the new minimum
                    minIndex = inner;
                }
            }

            // swap the elements between outer index and min index
            int temp = original[outer];
            original[outer] = original[minIndex];
            original[minIndex] = temp;

        }
    }
    
}

Bubble Sort in Java

Given an array of n (n>1) numbers, we want to sort them such that the smallest number is on the left, and the largest number is on the right. This is where all the sorting fun comes from. 

Bubble sort is one of the slowest of all sorting algorithms, but it is conceptually the simplest. 

In bubble sort routine, we start by comparing two numbers in the array, say the 1st (array[0]) and 2nd (array[1]) numbers. If the 1st number is larger than the 2nd number, we swap them, otherwise don't do anything. Then we move over one position and compare the 2nd and 3rd numbers, and so on, until we've completed the comparison of the second last and the last number. At this point, the largest number has been bubbled up all the way to the right (array[n-1]). On the 2nd round, we only need to do the comparison and swap from array[0] to array[n-2], which will ensure array[n-2] has the 2nd largest value in the array. Continue like this until the (n-1)th round.

The algorithm complexity, when expressed in Big O notation, is O(N²). This is because, given an array of 10 numbers, you will need 9 comparisons on the first round to bubble the largest number to the right, and 8 comparisons on the second round, and so on, while the last round requires 1 comparison. That is

9 + 8 + 7 + 6 + 5 + 4 + 3 + 2 + 1 = 45, or n*(n-1)/2, 

where n is the number of elements in the array. On the other hand, a swap is only required when the number on the left is larger than the one on the right, although in the worst case scenario, when the initial array is sorted such that the largest number is on the left and the smallest number is on the right, a swap is necessary for every comparison. Therefore, the number of swaps and comparisons are proportional to n².This is how we work out bubble sort's complexity O(N²).

Below demonstrates one of the implementations of the bubble sort algorithm.

import java.util.Arrays;
import java.util.Random;

public class BubbleSortTest {

    static int numberOfElements = 10;
    static int maxValue = 100;

    public static void main(String[] args) {
        int[] original = createArrayWithRandomValues();

        bubbleSort(original);

        System.out.println("The sorted array is " + Arrays.toString(original));
    }

    private static int[] createArrayWithRandomValues() {
        Random random = new Random();
        int[] original = new int[numberOfElements];
        for (int start = 1; start <= numberOfElements; start++) {
            original[start - 1] = random.nextInt(maxValue);
        }
        System.out.println("The original array is " + Arrays.toString(original));
        return original;
    }

    private static void bubbleSort(int[] original) {
        int outer, inner;
        for (outer = original.length - 1; outer > 1; outer--) { // from last element to the 2nd element
            for (inner = 0; inner < outer; inner++) { // from the 1st element to outer index - 1
                if (original[inner] > original[inner + 1]) { // bubble up the bigger value to the right
                    int temp = original[inner];
                    original[inner] = original[inner + 1];
                    original[inner + 1] = temp;
                }
            }
        }
    }

}