# Algorithms

This category contains all the posts related to Algorithms. For e.g.: Sorting, Hashing, Searching, Tree Traversals, Graph Theory etc.

## Interleaving Strings

Problem Statement This is a question from one of the interview experiences. The statement, "Given three strings A, B and C find if C is an interleaving of A and B." Interleaving is defined as below: A string C is said to be an interleaving of two strings A and B if C contains a sub sequence of A and B such that the relative order of characters in A and in B are preserved in C. For e.g. : A - ABCD B - BACDX C - ABACDXBCD The Idea - Interleaving Strings Here I am not giving any solution which is less than O(M*N) solution where M is the length of the shortest string among A and B...

## Minimum Spanning Tree Prim’s Algorithm

Introduction What is the minimum length of the network cable we require if we have to connect 100 computing machines in a building distributed across multiple floors? How do I guarantee that there can be no other minimum length possible than what I derive? Why is it even important to find the minimum length? The history of the problem You can read the classic problem solved by MST Applications of Minimum Spanning Tree Defining Spanning Trees A spanning tree is always defined for a weighted Graph G(V,E) where the weights are positive. This means that all the edges carry some positive we...

## Shortest Path using Dijkstra’s Algorithm

Introduction This is the third post in the Graph Traversals – Online Classes. After learning how to move through a graph, we might be interested in learning more. One interesting problem is determining the shortest path between two vertices of a graph. The problem can be extended and defined in many other forms. I prefer to call it "minimizing the cost". For e.g. When we measure the cost in terms of the distances between vertices, it can be called as the Shortest Path. When we measure the cost in terms of the money spent between vertices, it can be called as the Cheapest Path. Whe...