Spell autocorrect with edit distance – Code

spell autocorrector

Google provides a powerful spell correct for validating the keywords we type into the input text box. It checks against a dictionary. If it doesn’t find the keyword in the dictionary, it suggests a most likely replacement. To do this it associates with every word in the dictionary a frequency, …

Continue reading

Depth first search and matrix – Code

DFS and adjacent matrix

Depth first search (DFS) is an algorithm to traverse each element in the data structure. It starts from the source node, which can be root of the tree, or the start of the string, or a cell in matrix. We visit its adjacent node (or children) down the path before …

Continue reading

Monarchy succession order – code

royal succession order

Monarchy succession order is also known as The line of succession to the British throne. The succession to the British throne is determined by descent, sex, legitimacy, and religion. Under common law, the Crown is inherited by a sovereign’s children or by a childless sovereign’s nearest collateral line. The basis …

Continue reading

Detect cycle in graph and convert graph to tree – code

detect graph cycle

A graph is a data structure that consists of a set of vertices (aka nodes) connected by edges. A graph is cyclic if the graph comprises a path that starts from a vertex and ends at the same vertex. A tree is a simple graph with no cycle. In theory, …

Continue reading

Huffman coding and compression – Code

huffman coding

Huffman coding generates the prefix codes based on the frequencies of corresponding characters, and then compresses the data from the generated code. The explanation of Huffman coding and compression can be found in wiki. How to implement Huffman coding and compression in Java? We build frequency-sorted binary tree to encode …

Continue reading

Find K closest points to origin (2 solutions) – code

K closest points

What is K closest points problem? Find K closest points is to find closest points to the pointer(0,0) (it is called center or origin). The input k is to specify how many points you should return. Here we provide 2 solutions. The first one uses PriorityQueue. ProrityQueue is commonly used …

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. What’s the difference between substring and subset? The substring is contiguous sequence of …

Continue reading

Convert hierarchy to nested objects – code

Build status hierarchy object java

There are online tools that convert JSON file to objects. The same idea applies to “convert hierarchy to nested objects”. The syntax of nested object is obj.children[1].children[2]. “obj” is the top level object. Each nested object’s level maps with the level in the hierarchy list. You can access any object …

Continue reading

Bi-directional BFS and examples – Code

BiDirectional BFS

A bi-directional search is to start search from two ends simultaneously. The drive of this is to make the search efficient. BFS is short for Breadth First Search. The search starts from the source node. Then explores all its adjacent nodes before going to the next level adjacent nodes. The …

Continue reading

What are the missing data structures in java collections?

Java node data structures diagram

Java collections provides APIs for many data structures such as ArrayList, Linkedlist, HashMap. They are very handy for us to use. But there are missing data structures in Java collections that are widely used, but not provided. The developers have to write their own implementations for these data structures. What …

Continue reading