Wednesday, June 25, 2014

Given the post order array find if tree is BST


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.

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.
   2      5
  1      6

0 1 2 6 5 4 is the input array. Also, post order traversal has been explained here as well.


Consider the solution given here.
We know in BST root is bigger than all nodes in left subtree and is no larger than all nodes in right subtree. Thus, if the array is a post traversal of a BST, then arr[n-1] can divide the array into two parts arr[0, i) and arr[i, n-1), where
(1)each item in arr[0, i) is less than arr[n-1]
(2)each item in arr[i, n-1) is not less than arr[n-1]
(3)both arr[0, i) and arr[i, n-1) are post traversals of BSTs.
bool isPostTraversalOfBST(int arr[], int n)
 if(n < 2) return true;

 int i = 0;
 //try to find out the beginning of right subtree's traversal
 for(; arr[i] < arr[n-1]; ++i) ;
 //check if all arr[i,n-1) >= arr[n-1]
 for(int j = i + 1; j + 1 < n; ++j){
  if(arr[j] < arr[n-1]) return false;
 //check if both two parts are post traversals of BSTs
 return isPostTraversalOfBST(arr, i) &&
     isPostTraversalOfBST(arr + i, n - i - 1);

Sunday, June 15, 2014

Skiplist - TOC

Following are the topics on skiplist:

Friday, June 13, 2014

Fox and Duck


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?


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 of the fox it is obvious that duck cannot simply swim to the opposite side of the fox to escape. Pi*R/4 < R.

Let V be the speed of Duck and 4V speed of fox. Lets d is distance for duck to reach the edge and assume the fox is on exactly opposite side on the circle.

For duck to reach safely at edge d/v <= pi*R/4v
that is d <= (pi/4)*R
(as fox has to cover pi*R)

Now we need to find out the position from where duck can swim to the shore in time less then Pi*R/4V. Pi = 3.14.

If duck starts circling in the pond exactly at distance d1
then 2*pi*d1/v <= 2*R/4v
therefore the duck should start circling at d1 radius = R/4.

To keep things simple we will take the distance from center for the duck to escape when the fox is on the exact opposite side of the pond to be R/4.
So duck can swim in 3R/4V which is less than Pi*R/4V.

Now the next challenge is how we can make sure the clever fox will be on the opposite side. Here is the tricky part.

Let the duck rotate around the pond in a circle of radius R/4. Now fox and duck will take exact same time to make a full circle. Now reduce the radius the duck is circling by a very small amount (Delta). Now the Fox will lag behind, he cannot stay at a position as well. Now in due time duck will get to a position we wanted, 3/4*R distance away from shore where fox is on the exact opposite side of the pond. From there duck can swim safely to shore and fly away.


Road Race


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


Second place. You would have had to pass the first place racer to have finished in first place.

Thursday, June 12, 2014

Sum of Hats


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 again ,to which he replied "50"
How did he know it.And what are the numbers on other people's hats.


Coins on the Table


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 a game.
"We'll take turns putting a quarter on the table," he says. "Each quarter must lay flat on the table, and cannot sit on top of any other quarters. The last person to successfully put a quarter on the table wins."
He gives you the choice to go first or second. What should you do, and what should your strategy be to win?


Variant 2-
You should go first, and put a quarter at the exact center of the table.

Then, each time your opponent places a quarter down, you should place your next quarter in the symmetric position on the opposite side of the table.

This will ensure that you always have a place to set down our quarter, and eventually your oppponent will run out of space.


40 Pounds in the Balance


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?


The weights should be 1, 3, 9, and 27 lbs.

With the 1 lb weight alone, You can only determine a mystery ball of weight 1 lb.

With the 1 and 3 lb weights alone, you can determine a mystery ball of between 1 and 4 lbs. For example, if the mystery ball weighed 4 lbs, you could determine this by putting the 1 and 3 lb weights on one side of the balance, and the mystery ball on the other side. As another example, if the mystery ball weighed 2 lbs, you could determine this by putting the 3 lb weight on one side of the balance, and the mystery ball plus the 1 lb weight on the other side.

With the 9 lb weight in the mix, we can now determine the weights of a mystery ball between 1 and 13 lbs. And finally, with the 27 lb weight, we can determine any weight between 1 and 40 lbs.

Crazy guy in Airplane


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


There is a 1/2 chance that you'll get to sit in your assigned seat.

We first make two observations:

1. If any of the first 99 people sit in your seat, you WILL NOT get to sit in your own seat.

2. If any of the first 99 people sit in Steve's seat, you WILL get to sit in your seat. To see why, let's say, for the sake of example, that Steve sat in A's seat, then A sat in B's seat, then B sat in C's seat, and finally, C was the person who sat in Steve's seat. We can see that this forms a sort of loop in which every person who didn't sit in their own seat is actually sitting in the seat of the next person in the loop. This loop will always be formed when a person finally sits in Steve's seat (and if Steve sits in his own seat, we would consider this to be a loop of length 1), and so after that point, everybody gets to sit in their own seat.

Based on these observations, we know that the instant that a passenger sits in either Steve's seat or your seat, the game for you is "over", and it is fully decided if you will be sitting in your seat or not.

Our final observation is that for each of the first 99 people, it is EQUALLY LIKELY that they will sit in Steve's seat or your seat. For example, consider Steve himself. There is a 1/100 chance that he will sit in his own seat, and a 1/100 chance that he'll sit in your seat. Consider any other person who has been displaced from their own seat and thus must choose a seat at random...if there are N seats left, then there is a 1/N chance that they'll sit in Steve's seat, and a 1/N chance that they'll sit in your seat.

So because there is always an equal chance of a person sitting in your seat or Steve's seat (and one of these situations is guaranteed to happen within the first 99 people), then there is an equal chance that you will or will not get your seat. So the chance you get to sit in your seat is 50%.

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


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.
If the given tree is

 10     15

56  47   12  42 
Then the output should be
10 15
56 47 12 42


Here is the approach:
  1. Start with a root node. Add it to a new list.
  2. 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 void getLevelOrderInNewLine(TreeNode root)
    List<TreeNode> next = new ArrayList<TreeNode>();
    //actual function
public void levelOrder(List<TreeNode> n) {
    List<TreeNode> next = new ArrayList<TreeNode>();
    for (TreeNode t : n) {
        if (t != null) {
    if(next.size() > 0)levelOrder(next);


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


Given array filled with char elements, can you suggest a most efficient way to find the max length of continuous white space?


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 the answer given here, we can follow following solution:
Scan the array from 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. Skip forwards this max number in the array - if it is not whitespace you know the interval cannot contain the max whitespace. Otherwise search backwards to where whitespace started - find that set your count and continue from where you had previously skipped to.
I believe worst case performance of this would be O(n) and best case would be O(sqrt(n)) for the case where there is a sqrt(n) start of whitespace followed by non-whitespace on every skip point (causing repeated skipping to the end of the array).

Wednesday, June 11, 2014

Monty hall problem - Choose the Correct Door


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 reveals one of the lesser prizes. Monty then gives this contestant the option of staying with their chosen door or switching to the other door which still remains closed. The contestant then decides what to do and is rewarded with whatever prize is behind the door they finally chose. So the question is, should the contestant switch or stay?