Category: Ideas
-
Longest Increasing Subsequence
Longest Increasing Subsequence(LIS) is one of the most common problems of dynamic programming. Longest increasing subsequence problem is to find a subsequence of a given sequence in which the subsequence’s elements are in sorted order, lowest to highest, and in which the subsequence is as long as possible For example, when we have…
-
Kruskal Algorithm
Kruskal algorithm is a way to find a Minimum Spanning Tree(MST) from undirected edge-weighted graph. Minimum Spanning Tree(MST) is a subset of the edges of a connected, edge-weighted undirected graph that connects all the vertices together, without any cycles and with the minimum possible total edge weight. That is, it is a spanning tree whose sum of…
-
Backtracking
Backtracking is a method that removes child nodes that will not satisfy the condition and go back to parent node to proceed to other child nodes. Usually backtracking is related with DFS, which searches through all the children nodes. Typically, problems that require “Print all” or “Get all” are the…
-
Tree Problem Solutions
Top-Down Solution Using the value that came up with the first node, pass the value to the children nodes. It can be considered as pre-order tree traversal. If you can use parameters and the value of the node itself to determine what should be the parameters passed to its children,…
-
BFS and DFS
Breadth-First Search Breadth-First search is commonly used to find the shortest path from the root node to target node. Implementation Note that we used visited hash set to skip adding duplicate nodes, but there are some cases where one does not need the visited hash. Depth-First Search Depth-First search can…
-
Tree Traversal
Tree is a frequently used data structure that simulates a tree structure. Each node of the tree will have a root value and a list of subtrees of child nodes. There are 3 different ways to traverse all nodes in the tree. Pre-order Traversal (NLR) Visit the root node first.…
Will the Guru 