Flow network and min cut

mini cut feature

A flow network is a directed graph where each edge has a capacity and each edge receives a flow. The amount of flow on an edge cannot exceed the capacity of the edge. A flow network has designated source and sink nodes s and t. A flow must satisfy the …

Continue reading

Hierholzer’s algorithm to find Euler path – undirected graph

longest path

An Euler path  is a trail in a graph that visits every edge exactly once. Here we use graph data structure to simulate the set of linked porker cards and find the Euler path between them. In a porker game, if two poker cards have matched suites and figures, they can be link together. Given …

Continue reading

Topological sort using DFS and BFS

Tournamnet ranking

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 …

Continue reading

Find all subset of string in dictionary – code

find all subset string

Find all subset of string in dictionary is to find the subset of an input string that exists in dictionary. The dictionary contains one million words. For this question, the trick is to find subset, not substring. The difference between substring and subset is: The substring is contiguous sequence of …

Continue reading

Find all distinct palindromic substrings using suffix trie

suffix trie feature

All distinct substrings in a word are all contiguous sequence of characters within a string with all possible lengths. A suffix trie is a tree-like data structure that store all suffixes in a word. After you build a suffix trie, all distinct substrings of a word can be retrieved easily. A …

Continue reading

Domino Eulerian path problem using backtracking

dominoes euler path

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 …

Continue reading

Modulo operation and circular array

modulo operation

The modulo operation returns the remainder of one number divided by another. Modulo operator is a arithmetical operator, represented as %. One modulo operation example in math, 6 % 4 is 2. The modulo operation is also used in circular array. When an array index modulo (or mod) the array …

Continue reading

Josephus problem using circular linked list

last men standing

“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 …

Continue reading

Detect cycle and remove cycle in directed graph

detect graph cycle

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 …

Continue reading

Get suggested friends (2 solutions) – DFS and Union Find

suggested friends

Get suggested friends is one of a coding question in social network applications. The data structures for social network is usually a graph. In the graph, you can use depth first search(DFS) or breadth first search(BFS) to find the connections between people. Alternatively, you can also use Union find to …

Continue reading