Directed Acyclic Graph is a very special graph and has the following properties:
The edges of this graph are directed, it means all the edges have a designated direction.
There is no cycle in the graph, which means that a path will never contain one vertex more than once.
We referred to these kind of graphs in the topological ordering post.
Here we discuss the algorithm to find single source shortest path in such graphs. The good part is that unlike Dijkstra and Bellman Ford this can be solved in linear time O(E+V).
This algorithm for finding shortest path of directed acyclic ...

Read More
# Data Structures

This category contains all the posts related to data structures. For e.g.: Hash Tables, Linked Lists, Trees, Graphs, Heaps, Tries etc..

## Balanced Search Trees – AVL Tree

Introduction
When we talk about balanced search trees, we specifically are talking about two things.
A search trees.
A height balanced tree.
Here in this post we will consider a Binary Search Tree and will try to equip with features to self balance itself upon modifications. Before starting up with the logic and code part we need to understand the motive behind this kind of data structure and more precisely we need to understand the need of such a complex scenario.
Apart from that we also need to understand what it means to be termed as balanced.
What does balancing means?
We sa...

Read More
## Finding loop in Linked List

Problem Statement
You are given a singly linked list which may or may not contain a loop. The task at hand is to find if the loop exists. Here is a diagrammatic representation of a loop in a singly linked list.
[caption id="attachment_3617" align="aligncenter" width="688"] Finding loop in LinkedList[/caption]
It is pretty clear that there is a loop which starts at the node 3 and there are 10 nodes which make the loop. In this case we need to print a YES. If it had been a singly linked list without the node 12 connecting to node 3, we would have printed a NO.
Approach to Finding loop i...

Read More
## Cloning Linked List having Next and Random Pointer

Introduction
This question was asked by a colleague, although it seems to be simple at first but with given restrictions like running time and space limitations, it becomes tricky. You need to be good with Linked Lists to crack the right solution.
Here we try to define the problem in more detail.
Given a Linked List where each node contains two pointers next and random. The next pointer points to the immediate next node and the random pointer points to any random node in the linked list. Clone the linked list and return the head of the clone.
There are definitely certain conditions impos...

Read More
## Shortest path in Binary Search Tree

Introduction
Another interview question for the most interesting data structure called BST (Binary Search Tree). To know more about BSTs check my previous post.
Problem Statement : Given a Binary Search Tree, keyed on positive integers. The task is to find the Shortest path in Binary Search Tree which adds up to the number K. If no such path exists, return a message accordingly.
Understanding the problem
A node in a binary search tree always has a higher key at its right child compared to its left child. There are many path running from the roots to the leaves. When we add up the key val...

Read More
## Linked List Batch Reversing

Introduction
As I am writing this at 2 AM, this is going to be a small post but definitely an interesting one. This is mostly asked in interviews and is related to my previous post for Reversing a LinkedList.
Understanding the problem statement
Given a singly linked list L and a number k, we need to reverse each batch of k elements in the linked list. Here is a pictorial representation for the same.
For the below input linked list and for k equals to 3, you can see the output linked list under it. Each of the triplets are reversed.
Approach
We need to use our reverse linked list func...

Read More
## Topological Ordering for Graphs

Introduction
The topological ordering for graphs get many applications where the nature of the problem is ordered sequential processing. Few of the problems in this category are as follows:
Dynamic Linking/Loading of programs while building and execution.
Deciding the pre-requisites in a course structure.
Job Scheduling in Processors or Assembly Line Processing.
Building an Alien Dictionary from given words.
There are many more but I am sure you got the idea. When we say topological ordering of graph, we are necessarily talking about the ordering of the vertices of the graph.
Un...

Read More