Spell autocorrect with edit distance – Code

autocorrect

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

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

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

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. What is trie? A trie is a tree-like data structure in which every node stores a character. After building the trie, …

Continue reading

Word break using memoization – Code

word break java

What is word break? 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. Memoization is one of Dynamic programming(DP) technique. DP is able to solve a complex …

Continue reading

Huffman coding and compression – Code

Huffman coding and compression

What is Huffman code? Huffman code is a particular type of optimal prefix code. It is commonly used for lossless data compression. The explanation of Huffman coding and compression can be found in wiki. How to implement Huffman coding and compression? We use frequency-sorted binary tree to encode symbols. Here …

Continue reading

Prefix to postfix (2 solutions) – Code

convert prefix to postfix java

In mathematics expressions, there are infix, prefix and postfix notations. Infix notation is characterized by the placement of operators between operands. For example, the plus sign in 2 + 2. Prefix notation is a notation in which operators precede their operands, such as + 3 4. Postfix notation is a …

Continue reading