Puzzle Statement
The Police have three suspects for the murder of Mr. Cooper: Mr. Smith, Mr. Jones and Mr. Williams. Smith, Jones and Williams each declare that they did not kill Cooper.
Smith also states that Cooper was a friend of Jones and that William disliked him. Jones also states that he did not know Cooper and that he was out of town the day Cooper was killed. William also states that he saw both Smith and Jones with Cooper the day of the killing and that either Smith or Jones must have killed him.
Can you determine who the murderer was if:
One of the three men is guilty, th...

Read More
## Median of a Stream of Integers

[nextpage title="Problem Statement"]
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 importa...

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