Author: dharam

Identify Apple and Oranges Labels

Puzzle Statement There are three boxes, one contains only apples, one contains only oranges, and one contains both apples and oranges. The boxes have been incorrectly labelled such that no label identifies the actual contents of the box it labels. Opening just one box and without looking in the box, you take out one fruit. By looking at the fruit, how can you immediately label all of the boxes correctly? Solution It might look tricky but if we can think for a while and decide upon which box to open the solution really becomes simple. Let us first note down the facts we know for sure:...
Read More

Graph Theory Applications – The Instant Insanity Puzzle

[nextpage title="Applications of Graph Theory"] Graph Theory is used in modelling and solving a lot of real world problems, games and puzzles. Here we discuss a very famous puzzle " The Instant Insanity " problem. The goal of this post is to demonstrate that such complicated problem statements can be so easily modeled and solved using Graph Theory. Also I would like to build some more  interest into Graph Theory. If you want to feel more comfortable with the basics of Graph Theory, here is a list of primers you might like to read once. Problem Definition - The Instant Insanity Puzzle The...
Read More

Priority Queues

Introduction You have N distinct jobs to process, and you are given the responsibility to schedule them on the only available job processor. New jobs keeps on getting added into the set of available jobs. Not all the jobs are to be executed as they come. There might be few which needs to be executed immediately and few can be postponed for some time. You have an efficiently algorithm to decide the priority of an incoming job. The task at hand is as follows: To schedule available jobs based on the priority assigned to them. Add new jobs to the set after assigning a priority to it. ...
Read More

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

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

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