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

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

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

Prefix to postfix (2 solutions) – Code

Prefix To Postfix

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

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

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

Find top trending topics in twitter last hour (2 solutions) – code

top trending topic

Find top trending topics last hour (last day, month, year) is to find the topics that were tweeted most for the given time. To start with, the tweet can be defined as class with topic string and timeStamp . To keep track the topic’s count, we can use a HashMap …

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