Longest path of matched cards – code

longest path matched cards

Longest path of matched cards is to link the cards that have the matched suite or figure. This is an Eulerian path problem. An Eulerian path (or Eulerian trail) is a trail in a finite graph that visits every edge exactly once (allowing for revisiting vertices). First we link the matched cards as a chain by applying …

Continue reading

Get suggested friends (2 solutions) – code

suggested friends

When you are asked to design the data structures for social network, normally the answer is graph. In the graph, We can use DFS or BFS to find the connections between people. Alternatively, we can also use Union find to group the people by their connections. Here we provide solutions …

Continue reading

Find ranking with topological sorting (2 solutions)

Tournament ranking with topo sort

Find ranking with topological sorting is to find winner and ranking in tournament. 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, aks directed acyclic graph (DAG). Once the graph …

Continue reading

People who know story by time stamp -code

people know story by timestamp

People who know story by time stamp is to simulate social network using graph data structure. The individual person is a node. The edge is from one person to another person when one tells another a story. The edge is bi-directional since both people know the story. The graph can …

Continue reading

Autocomplete with trie – Code

Autocomplete with trie java

Autocomplete is a feature that search box returns the suggestions based on what you have typed. Autocomplete with trie provides an implementation of auto-complete by using data structure trie. A trie is a tree-like data structure in which every node stores a character. After building the trie, strings or substrings …

Continue reading

Word break using memoization – Code

wordbreak with memoization

Word break is to divide a string into sub-strings that defined in dictionary. The problem is usually solved with recursion. The time complexity is exponential. Here we introduce word break using memoization, which helps to improve complexity. Memoization is one of Dynamic programming(DP) techniques. DP is able to solve a …

Continue reading

Shortest path from source to destination in matrix – Code

shortest path in matrix

Shortest path in matrix is to find the shortest distance from the the source to the destination. As you know, graph can be represented as adjacent matrix. Therefore, we can use the Breadth First Search algorithm in graph to solve this problem. BFS starts from the source node. It explores …

Continue reading

Shortest path and 2nd shortest path using Dijkstra – code

shortest path using Dijkstra java

What is Dijkstra’s algorithm? Dijkstra’s algorithm is an algorithm to find the shortest paths between vertices in a graph. It uses greedy technique by picking the un-visited vertex with the lowest distance. When all vertices have been evaluated, the result is the shortest path. Find 2nd shortest path is a …

Continue reading

Build hierarchy tree – Code

Build hierarchy tree java

Build hierarchy tree reads employee data and build a corporation hierarchy tree from the list. HashMap plays important role to store the data when reading the input. The trick of this question is to find the root. You can get the root by finding the employee without the manager. Starting …

Continue reading

Web scrape and parsing in Java (5 Ways)

web scrape

Internet is the great resource to get information, for study, business or hobby. There are many ways of information retrieval with web scrape and parsing from Internet. All programing languages provide the libraries to do so. In this post, I introduce 5 ways of web scrape and parsing. 1. HttpURLConnection …

Continue reading