## Count Triangles formed by the elements of array

Problem Statement Given a sorted array of distinct integers, each of these integers can represent a length. The task at hand is to count the number of possible triangles which can be made through these lengths. Of course, if you chose one length to be one side of the triangle, you cannot use that length again in the same triangle. This means, no triangle contains the same length more than once. Important Note: For given sides of lengths a, b and c. A triangle can only be formed if sum of any two sides is greater than the third side. This is called the triangle inequality. The sum of any...

## Understanding Heap Sort

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

## 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...

## 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...

## 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...