Author: dharam

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...
Read More

Depth First Traversal

Introduction This is the second post in the Graph Traversals – Online Classes. I Recommend you to look at the first post Breadth First Traversal as it contains more explanation and details and I will keep this post smaller just around the depth first concept. Depth First Traversal The Idea In this traversal, we choose a start vertex and keep moving forward along the length of the graph until there is no undiscovered vertex in that path. Once reaching a dead end, we back track to all the visited vertices and check if we have any vertex which has an adjacent undiscovered vertex. We kee...
Read More

Breadth First Traversal

Introduction This is the first article in the Graph Traversals – Online Classes. Dear Readers, these set of posts under Graph Traversals will make more sense if you have read the Graph Theory. Here is a quick brush up for the same. However, if you are familiar with Graph Theory and have a basic knowledge of what graphs are and how they are stored, you can dive into the traversals. Later in the series we will discover that the Graph Traversals are widely used in various application. Let me point out a couple of real world examples here: How can we conduct matches between teams in a C...
Read More

Make anagrams from two Strings

Problem Statement Given two strings, find the total number of characters we need to delete from these strings to make them anagrams of each other. Understanding Anagrams Anagrams are defined with respect to a given string of characters (not necessarily characters in the English Alphabet) but a wider set of characters may be. Given two strings A and B, if the number of time each character occurs in both the string is exactly same, we say A and B are anagrams. However, the order in which the character appears may be different and doesn't matter. For example A = axbbxxcecdeedda B = abacb...
Read More

Matrix Rotation and Matrix Transpose

Problem Definition – Matrix Rotation (by 90, 180, 270 degrees) This is a very famous interview question and has been asked numerous times. We are trying to solve the problem of matrix rotations where the inputs are as follows: A matrix of dimension M * N A number from the set (90, 180, ,270) by which we need to rotate the matrix. For simplicity we will consider a matrix to be a 2 dimensional array of integers. What does it mean to rotate a matrix? This can only be explained by nice diagrams. Just for a formal definition, I would say that matrix rotation is a structural re-arrangeme...
Read More

Inorder Predecessor of node in Binary Tree Using Parent Pointer

Introduction This is the seventh article in the Tree Traversals - Online Classes. This article presents ways to find out inorder predecessor of node in binary tree. As we have already read about the Inorder Successor it wont take much effort to understand the predecessor. Definition - Inorder Predecessor of node in Binary Tree If a node K is called the inorder predecessor of node N then N must be visited immediately after K in a inorder traversal of the tree. Below is a more formal definition of Inorder Predecessor: If the node has a left sub-tree, then inorder predecessor is the ...
Read More

Inorder Successor of node in Binary Tree Using Parent Pointer

Introduction This is the sixth article in the Tree Traversals - Online Classes. This article presents ways to find out inorder successor of node in binary tree. Before we jump into the code it would be good to correctly define the meaning of the problem. Definition - Inorder Successor of node in Binary Tree If a node K is called the inorder successor of node N then K must be visited immediately after N in a inorder traversal of the tree. Below is a more formal definition of Inorder Successor: If the node has a right sub-tree, then inorder successor is the left most node of the rig...
Read More