Author: dharam

Median of a Stream of Integers

Here is a very interesting problem which has been asked in many interviews and coding competitions. The problem statement goes as follows: Given a never ending stream of number, at any point in time, find the median of all the numbers received till that point. This means, we need to recalculate the new median whenever there is a number available in the input stream. This problems seems to be a very practical one, imagine a lot of sensors in manufacturing plants are pushing data about temperature, pressure and other physical parameters. It is very important to keep track of the average and ...
Read More

Operations on a Heap

Introduction In this post, we will try to put together all the leanings from the previous posts and define the basic operations on a heap. Also, we will try and derive the running time of each such operation and write code for the same. Also, we will discuss an interesting problem statement which can be easily solved using the heap property. Basic Operations on Heap The heap can support the following basic operations as any other data structure IncreaseKey - Changes the key value of a given node to a new value. It is assumed that the new value is at least as big as the current value....
Read More

Building Heaps from an array of keys

[nextpage title="Introduction"] In the last post we learnt the basics of the heap data structure, its array and tree representations. We also learnt about the heap property and its significance. In the process of learning we understood that a given node can be disturbed and the heap property needs to be restored using the Heapify operation. Here in this post, we will try building heaps from an array of keys. Building Heaps Let us think about the easiest way to build a heap. Assume we are given the below array A: This clearly is not satisfying the max heap property because the root ...
Read More

Understanding the Heap Datastructure

Introduction Heap(specifically binary heap) is a special data structure which can be viewed as a nearly complete binary tree. This post is mostly focused on understanding the heap datastructure The first few impressions about heap after reading the above line: The height of the binary tree would be minimum. For e.g.: if the tree has N nodes, the height would be logN. The tree can also be stored in an array, in fact it would be easier to store this tree in an array (because it is complete). This makes it an awesome data structure because the minimum height guarantees logN running ti...
Read More

Single Source Shortest Path – Directed Acyclic Graph

[nextpage title="Introduction"] 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 sho...
Read More

Save the largest area

Problem Statement In the historic city of Technisia there are rectangular monuments made of stones. The monuments are placed on the ground in such a way that they all lie in one row. The width of each monument is one unit and the length may vary.  The population of the city is growing and people need empty spaces to build houses and markets. The mayor decides to demolish the monuments and presents a demolition schedule. You being a monument lover, would like to preserve the most of what can be preserved, hence you start finding a solution to save the largest area. Upon your request the may...
Read More

Cursed Trees – Interview Question

Problem Statement This is an awesome interview question which tests our ability to extensively use data structures. We are given an array of trees with different heights. The trees have a curse upon them, they do not grow any more and for a given pair of trees, if a tree is taller than the one to its left then the tree will die in a year. The task at hand is to find out, the number of years after which no trees will die. Explanation Year 1 : At the end of the first year the trees with height 6 , 14 and 10 will die. All of these trees have a smaller tree to their left and the r...
Read More