Autocomplete with trie (3 solutions) – Code

autocomplete with trie listing

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

Depth first search in matrix using recursion

DFS and adjacent matrix

An adjacency matrix is a 2d array representing a graph. The nodes are the headings for the rows and columns. The element in the cell indicates whether an edge is present between two nodes. Depth first search (DFS) is an algorithm used to traverse or search in a graph. The …

Continue reading

Shortest path and 2nd shortest path using Dijkstra – code

shortest path using Dijkstra java

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. This post provides code to find shortest path and second …

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

Huffman coding and decoding – Step by step

huffman coding

By applying huffman algorithms, we compress the input string by using the generated code. We can also use the code to decompress to get the original string. Here are the steps of huffman coding and decoding. The code is available in Java, JavaScript and Python. Amazon Interview Question(modified) Implement the …

Continue reading

Build hierarchy tree – Code

build hierarchy tree listing

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

Detect cycle and remove cycle in directed graph

detect graph cycle

A graph is a data structure that consists of a set of nodes (vertices) connected by edges. A graph is cyclic if the graph comprises a path that starts from a node and ends at the same node. In this post, a simplified solution is provided to detect cycle and …

Continue reading

Find K closest points to origin (3 solutions) – Time complexity explained

K closest points

The K closest problem is to find K 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. The Euclidean distance formula is √[ (x2–x1)^2 + (y2–y1)^2]. For this question, we don’t need to calculate the actual …

Continue reading

Prefix to postfix (2 solutions) – stack and recursion

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

Modulo operation and circular array

modulo operation

The modulo operation returns the remainder of one number divided by another. Modulo operator is a arithmetical operator, represented as %. One modulo operation example in math, 6 % 4 is 2. The modulo operation is also used in circular array. When an array index modulo (or mod) the array …

Continue reading