Heap Sort is one of the efficient sorting algorithms with a guaranteed worst case running time of O(NlogN). This is an in place sorting algorithm but it does not offer stable sorting.
In place Sorting: A sorting algorithm which sorts the input using very small or no extra space. It means that the input data is overwritten by the resulting output data.
Stable Sorting: A stable sorting algorithm is one, in which the relative order of equal keys is preserved. It means if there are non unique keys in the input data, then their relative order of occurrence in the input as well as output rem...

Read More
# Author: dharam

## Find the Relative Salary

Puzzle Statement
Steve would like to determine the relative salaries of three coworkers using two facts:
First, he knows that if Fred is not the highest paid of three, then Janice is.
Second, he knows that if Janice is not the lowest paid,, then Maggie is paid the most.
Is it possible to determine the relative salaries of Fred, Maggie and Janice from what Steve knows? If so, who is paid the most and who the least?
Quick Solution
Fact 1 says that if Fred is not the highest paid, then Janice is. This results in two situations:
Fred is not the highest paid
Janice is the hi...

Read More
## Identify the Murderer

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