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

British royal succession order – code

royal succession order

British royal succession order is also known as the line of succession to the British throne. Under common law, the crown is inherited by a sovereign’s children or by a childless sovereign’s nearest collateral line. You can get the current British monarchy succession order here. When you are asked to …

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

Depth first search in weighted graph using recursion

DFS in weighted graph

In a social network, an individual person is a node. Between two people there is an undirected edge because they are mutual friends. When one person tells another person a story, they both know the story. Given timestamp as the time two people meet, timestamp can be seen as the …

Continue reading

Find a random number NOT in array – code

find random not in array

Find random number not in array is a tricky question. It is pretty straight forward to find a random element in array by getting an random index within the range. If you are asked to find a random element that is NOT in array, your brain might not response quickly …

Continue reading

Build nested object from hierarchical list- code

build nested object

Similar to convert JSON file to objects, we can covert hierarchical list to a nested object. The input is like a table of content with multiple levels, the output is a nested object obj.children[1].children[2]. “obj” is the top level object. Each nested object’s level maps with the level in the …

Continue reading