According to wikipedia,

Backtracking is general algorithm for finding all (or some) solutions to some computational problems, notably constraint satisfaction problems, that incrementally builds candidates to the solutions, and abandons a candidate (backtracks) as soon as it determines that the candidate cannot possibly be completed to a valid solution.

I have compared backtracking to DFS in a previous post, so here I’ll just focus on the classic problems solved by backtracking.

Java garbage collector frees the heap memory occupied by the objects that are no longer reachable. It takes the job from programmers who often forget to release the memory when they no longer need it and sometimes find it hard to debug memory issues.
What does JVM benefit from garbage collection other than preventing programmers from messing up with the memory? The answer is the efficiency at allocating memory for new objects. This is because garbage collector not only frees memory but also compacts objects in the heap. I wonder if other languages without garbage collector have some similar mechanisms for compaction.

This post is about the implementation of garbage collection in JVM. JVM adopts a hybrid of various strategies, but generational GC is the cornerstone.

Given an array of numbers sorted in ascending (or descending) order, a common solution to find a target number is binary search. Binary search starts at the middle position of the array, and narrows down the searching range to half of the array by comparing the target number to the number on the middle position; and then repeats this process until the target number is found or the searching range is left to be 0.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

// suppose the array of nubmers are sorted in ascending order
int binarySearch(int[] array, int target) {
    int i = 0;
    int j = array.length - 1;
    while (i <= j) {
        int mid = (i + j) / 2;
        if (target == array[mid]) return mid;
        if (target < array[mid]) {
            j = mid - 1;
        } else {
            i = mid + 1;
        }
    }
    return -1;
}

Time complexity: O(log(n)).

There are a variety of interesting problems which are derived from this simple searching problem. In Part I, I’ll go through such searching problems confined to an array. In Part II, the problems are focused on the matrix.

Strategy Pattern is a behavioral design patter.

According to wikipedia:

It enables selecting an algorithm at runtime. It

• defines a family of algorithms
• encapsulates each algorithm
• makes the algorithms interchangeable within that family
• lets the algorithm vary independently from clients that use it

I will walk through some examples of strategy pattern in this post, hoping that it will give you and myself some insight of this pattern.

DFS, short for Depth First Search, is an algorithm of searching tree or graph data structures. It starts at the root (or selecting some node as the root in the case of graph), and explores as far (or deep) as possible until it cannot go any further, then it backtracks and tries other paths.

DFS is always implemented using recursion. Its non-recursive implementation depends on an explicit stack.

1
2
3
4
5
6
7
8
9
10
11

// Node represents a node in a graph
void dfs(Node node) {
    if (qualified(node) || !canGoFuther(node)) {
        return;
    }
    for (Node neighbor : getNeighbors(node)) {
        if (canBeProcessed(neighbor)) {
            dfs(neighbor);
        }
    }
}

I have applied DFS to varieties of search problems in previous posts, e.g. problems relating to binary tree, and problems relating to graph. So I won’t cover the same problems in this post, but I’ll write about the topic DFS vs. backtracking which I find both interesting and confusing.

BFS, short for Breadth First Search, is an algorithm of searching tree or graph data structures. It starts at some specific nodes and explores the neighbor nodes first before moving to the next level, until it searches through the whole graph.

BFS usually works with a queue.

1
2
3
4
5
6
7
8
9
10
11

// initialize
queue.add(node);
// search
while (!queue.isEmpty()) {
    // Node represents a node in a graph
    Node node = queue.poll();
    // explore the neighbor nodes
    for (Node neighbor : neighbors) {
        if (isQualified(neighbor)) queue.add(neighbor);
    }
}

BFS and DFS are two typical algorithms of searching graphs, and some searching problems can be solved by Union Find as well, so first I want to discuss the scenarios where we should use BFS, DFS or Union Find. And then I will walk through some problems, if they can be solved using DFS or Union Find, I’ll provide the corresponding solutions; otherwise, I’ll list the reasons why DFS or Union Find cannot be applied to the problems.

Given two positive numbers which are represented in strings, return the sum, difference, product, quotient and remainder of the two numbers.

A solution is to have the string converted to an array where digits are store in a reversed order and then do the calculation on each digit.

A binary tree is a tree where each node has at most two children. Suppose the depth of a binary tree is k, then it has at most 2^k children.
A complete binary tree is a binary tree where every level (except the last) is completely filled, and all nodes at the last level are as far left as possible.
A full binary tree is a complete binary tree where every node other than the leaves has two children.

This post is about some classic problems relating to the binary tree. Most of the problems can be solved using DFS.

Factory Method Pattern provides a way of encapsulating object creation.
The definition by Gang of Four:

Define an interface for creating an object, but let subclasses decide which class to instantiate. The Factory method lets a class defer instantiation it uses to subclasses.

I will first walk through some examples of factory method pattern, and then compare it to the simple factory pattern, hoping that it will give you a better understand of factory method pattern.

Boyer-Moore Majority Vote Algorithm finds the majority of a sequence of elements if there is one. Note that if there is no majority, the algorithm cannot detect it.