Data Structure

Total number of set-bits from 1 to n

Given a positive integer n, count the total number of set bits in binary representation of all numbers from 1 to n. Example: Input: n = 3 Output: 4 The way to solve these sorts of problems is to write out the first few values, and look for a pattern Number binary # bits set F(n) 1 0001 1 1

2018-12-10T23:19:55+05:30Categories: Data Structure|

Strongly Connected Components | Graph

A directed graph is strongly connected if there is a directed path from any vertex to every other vertex. Strong connectivity applies only to directed graphs because in an undirected graph, every vertex can reach every other vertex via any path. This relation between nodes is reflexive, symmetric, and transitive, so it is an equivalence relation. If the graph is not connected

2019-07-07T16:59:52+05:30Categories: Data Structure|

Dijkstra Vs Prim Algorithm | Graph

Prim Algorithm Prim’s algorithm constructs a minimum spanning tree for the graph, which is a tree that connects all nodes in the graph and has the least total cost among all trees that connect all the nodes. However, the length of a path between any two nodes in the MST might not be the shortest path between those two nodes

2020-03-28T14:34:56+05:30Categories: Data Structure|Tags: |

Number of special subsequences in a string

You are given a String S of length N. Now, a special subsequence is one that can be represented in the form a^i b^j c^k, where i≥1, j≥1 and k≥1. In short, a special subsequence is a subsequence that first consist of i ′a′ characters, followed by j ′b′ characters, followed by k ′c′ characters, where i≥1, j≥1 and k≥1

2018-12-02T16:37:07+05:30Categories: Data Structure|

Huffman Coding

Prefix Code It is a type of code system distinguished by its possession of the "prefix property", which requires that there is no whole code word in the system that is a prefix (initial segment) of any other code word in the system. For example, a code with code words {9, 55} has the prefix property; a code consisting of {9, 5, 59, 55}

2018-11-28T22:44:46+05:30Categories: Data Structure|

Longest proper prefix in KMP

Pattern searching is an important problem. Worst case time complexity of the Naive algorithm is O(m(n-m+1)). The time complexity of KMP algorithm is O(n) in the worst case. Every time the naive function fails (or succeeds), it starts matching over from the next character. This might not be necessary. We could use our knowledge of the point of last matching

2018-11-24T21:22:12+05:30Categories: Data Structure|

Detect Cycle | Graph

Introduction Graphs are of two kinds on the basis of the way edges are directed. In Undirected graph all the edges go forward as well as backward between two vertices. In Directed graph edges between two vertices are directional. Algorithm For Detecting Cycle To detect cycles using DFS, use two colors in a undirected graph and three colors in directed

2020-03-28T15:04:20+05:30Categories: Data Structure|Tags: |

Important Algorithms

Rabin-Karp Algorithm for Pattern Searching Majority Voting Algorithm Dutch national flag sorting Kahn’s algorithm for Topological Sorting Tarjan’s Algorithm to find Strongly Connected Components Knuth-Morris-Pratt string matching Prim’s Minimum Spanning Tree Flood-fill Algorithm Dijkstra’s shortest path algorithm

2018-12-08T14:20:40+05:30Categories: Data Structure|

Expression Tree

Expression tree is a binary tree in which each internal node corresponds to operator and each leaf node corresponds to operand. Consider the expression: (a + b*c) * ( d + e) It can be represented as a binary tree as In-order traversal, reconstructs the expression:  (a + b*c) * ( d + e) i.e Infix notation. Post-order traversal results in

2018-09-21T16:32:16+05:30Categories: Data Structure|
Go to Top