Data Structures

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

Filling Wine Glasses Interview Question

Introduction This is another interesting interview question and took me sometime to think for an answer. The problem statement goes as follow: "There are wine glasses stacked such that the top level has one glass, the second level has two glasses, the third one has three glasses and so on. Imaging that the levels are deep enough. Each of the glass in the stack has volume u. Now given a jug of volume V full of wine such that V >= u, find the lowest level where wine can reach." Analyzing the problem statement Here is a supporting image for the problem statement. Now I pick up the ju...
Read More

Adding numbers using Linked Lists

Introduction Adding numbers has always been fascinating and you may think it to be the easiest mathematical operation possible. But believe me many a times that becomes the toughest problem to solve. Let us discuss this in more detail. It is really easy to add two numbers stored in two memory locations. The ALU provides you the option to use the ADD feature and store it on the DATA bus. This is feasible when both the numbers can fit on the DATA bus one at a time. So, what about adding excessively large numbers, I know that the limit of BigInteger, Long, Double etc is too huge. But what if ...
Read More

Reversing a Singly Linked List

Introduction Many people have asked me to explain the dynamics of how the reversing of a singly linked list works, when we do not have the liberty of creating a new linked list, may be due to limitation of memory. The Idea behind Reversing a Singly Linked List The idea is to iterate through the complete linked list and maintain three pointers as listed below: Pointer to the head of un reversed list headOfUnReversedLL. Pointer to the head of reversed list headOfReversedLL. Pointer to the node to be reversed nodeToReverse. In each iteration we follow the below four steps: The h...
Read More

Shortest Path Using Bellman Ford Algorithm

Introduction This post about Bellman Ford Algorithm is a continuation of the post Shortest Path Using Dijkstra's Algorithm. While learning about the Dijkstra's way, we learnt that it is really efficient an algorithm to find the single source shortest path in any graph provided it has no negative weight edges and no negative weight cycles. The running time of the Dijkstra's Algorithm is also promising, O(E +VlogV) depending on our choice of data structure to implement the required Priority Queue. Why Bellman Ford Algorithm? There can be scenarios where a graph may contain negative weight ...
Read More

Further Reading for Minimum Spanning Tree

Introduction This is a supplement to the posts for Minimum Spanning Tree and their Analysis. Check out the other related articles in the following section. Further Reading for Minimum Spanning Tree This section is meant to be read in conjunction to the post Minimum Spanning Tree - Prim's Algorithm The minimum spanning tree of a Graph is the union of minimum spanning trees of its connected components. This is a very important observation and it must be discussed in length and breadth because this will help us design our algorithm for MST in a better way. Why is it so important to underst...
Read More

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

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