Given the post order array find if tree is BST

Problem An array which is a Post order traversal of a Binary Tree. Write a function to check if the Binary Tree formed from the array is a Binary Search Tree. Eg:  2 1 3 The array given as input would be 1 3 2. Write a function to say if the tree formed is a Binary Search Tree. Example 2: 4 is root. 0 is left child of 1 , 1 is left child of 2 and 2 is left child of 4. 5 is right child of 4 and 6 is right child of 5.        4    2      5   1     ...

Read More

Skiplist - TOC

Following are the topics on skiplist: Skiplists Skiplist vs Binary tree...

Read More

Fox and Duck

Problem A duck, pursued by a fox, escapes to the center of a perfectly circular pond. The fox cannot swim, and the duck cannot take flight from the water. The fox is four times faster than the duck. Assuming the fox and duck pursue optimum strategies, is it possible for the duck to reach the edge of the pond and fly away without being eaten? If so, how? Solution This is not a simple mathematical puzzle to solve like normal common problems. Fox in this puzzle is too fast and clever for any normal and simple strategy. From the speed...

Read More

Road Race

Problem In the final stretch of a road race, you pass the 2nd-place runner right before crossing the finish line. What place do you finish in?Pu Solution Second place. You would have had to pass the first place racer to have finished in first place....

Read More

Sum of Hats

Problem There are 3 people Abel,Bill and Clark.Three of them have numbers written on their hats.One can only see the numbers written on others hats and can not see the number written on his own hat. Sum of numbers on any two 2 hats is equal to the number on the third hat.Now the following event occurs 1. Abel was asked about the number on his hat.He replied "Don't Know" 2. Bill was asked about the number on his hat.He also replied "Don't Know" 3. Clark was asked about the number on his hat.He also replied "Don't Know"a 4. Abel was asked...

Read More

Coins on the Table

Problem Variant 1----------- There is a table on which a number of coins are placed. You also know that there are as many coins with Head up as many coins with Tail up. Now you have to divide the coins (number of coins is even) into two equal piles such that number of coins with Heads up and Tails up in either piles be the same. The catch is you are blind folded and you cannot determine the sides (for sure) if you are blinded Variant 2-----------  Your friend pulls out a perfectly circular table and a sack of quarters, and proposes...

Read More

40 Pounds in the Balance

Problem You are given a mystery ball and are told that it has a whole-number weight between 1 and 40 lbs (inclusive). You are then given a balance scale are are allowed to pick four weights, each weighing any whole-number amount. You much choose these weights so that no matter what the mystery ball weighs, you will be able to determine its weight using just the balance scale and these four weights. What weights should you choose? Solution The weights should be 1, 3, 9, and 27 lbs. With the 1 lb weight alone, You can only determine...

Read More

Crazy guy in Airplane

Problem People are waiting in line to board a 100-seat airplane. Steve is the first person in the line. He gets on the plane but suddenly can't remember what his seat number is, so he picks a seat at random. After that, each person who gets on the plane sits in their assigned seat if it's available, otherwise they will choose an open seat at random to sit in. The flight is full and you are last in line. What is the probability that you get to sit in your assigned seat Solution There is a 1/2 chance that you'll get to sit in your assigned...

Read More

Print a Binary tree in level order with new line after every level

Problem Given a binary tree, you have to print level order traversal of the tree (left child then right child) but every next level has to be printed in next line. Example If the given tree is 5 10 15 56 47 12 42 Then the output should be 5 10 15 56 47 12 42 Solution  Here is the approach: Start with a root node. Add it to a new list. Now add all the children of the elements present in the new list and print the element, after removing the element. Once the array is empty, print the new line. Here is the code public...

Read More

Given an array filled with char elements, find the max length of continuous white space

Problem Given array filled with char elements, can you suggest a most efficient way to find the max length of continuous white space? Solution Scan the array left to right, keep a count of white space. When you reach a non-whitespace character, check that count against the current max; if it's higher, it becomes the new max. Set the count back to zero, continue scanning. Time complexity - O(n) This is O(n) and you can't really do better because you have to touch each element at least once. But of-course we can optimize it. Consider...

Read More

Monty hall problem - Choose the Correct Door

Problem On the game show "Let's make a deal", Monty Hall (the host) walks up to a contestant and gives them $100 unless they want to play "the three doors". They usually turn down the money and play "the three doors". Now behind one of the doors is an enourmous cash prize, behind the other too are silly prizes such as a years supply of toilet paper or a goat. So Monty asks this same contestant to pick a door, which they do. Then, before opening the chosen door and revealing what's behind it, he opens one of the other doors which...

Read More