A graph is a data structure that consists of a set of nodes (vertices) connected by edges. A graph is cyclic if the graph comprises a path that starts from a node and ends at the same node. In this post, a simplified solution is provided to detect cycle and …
The modulo operation returns the remainder of one number divided by another. Modulo operator is a arithmetical operator, represented as %. For example, 6 % 4 is 2. The modulo operation is very useful in circular array. When an array index modulo (or mod) the array length, the index that …
To find number of possible combinations of valid parentheses, we have to know Catalan number. Catalan numbers are a sequence of natural numbers that follow the formula showing below. The first few Catalan numbers for n = 0, 1, 2, 3, 4, 5 … Cn = 1, 1, 2, 5, …
Build hierarchy tree is to build a corporation hierarchy tree from an employ list. HashMap plays important role to store the data when reading the input. You can get the root by finding the employee without the manager. Starting from the root, get subordinates for each employee. Then you build …
“Josephus problem” or “circle of death problem”. Given a number n people standing in a circle, eliminate every kth one until the last one remain. This problem can be solved with a circular linked list. First, we build a circular Linked List by adding n nodes. The number starts from …
Topological sort is a graph traversal in which node v is visited only after all its dependencies are visited. The graph has to be directed and has no cycles, i.e. directed acyclic graph (DAG). Once the graph is built, you can use the algorithms to find the order. The result …
Word ladder is to find the number of steps to convert one string to another by changing one letter at a time. The intermediate words should be valid and can be found in pre-defined dictionary. The intuitive solution is using breadth first search (BFS). It starts from the original word, …
When you search in Google, it provides autocorrect for validating the keywords you enter into the input box. Behind the scene, it checks the input words against a dictionary. If it doesn’t find the keyword in the dictionary, it suggests a most likely replacement. Here I introduce a simple solution …
A Euler path (Eulerian path) is a path in a graph that you visit each edge exactly once. You can visit the same vertex multiple times though. Dominoes is one example of finding Euler path problem. A domino is a game piece that has 2 numbers on it, one number …
Permutation of multiple arrays and iterator has two tasks. First is the permutation of multiple arrays and output as an array of new combinations. The second is to implement the iterator of this new array. Permutation is an important topic in the fields of combinatorics. It is usually implemented using …
