Tuesday, September 23, 2014

Maximum number of chickens you cannot order


There is a non vegetarian restaurant which sells chicken in orders of 6, 9 and 20.

Calculate the maximum number of chicken pieces you cannot order from that restaurant ?



If you analyze, then you will find that all the 6 numbers divisible by 3 can be ordered. Why? Because you can break them own as the sum of 6 and 9.
Now after 26, all the numbers that are divisible by 3 if subtracted by 40 can be obtained.
After 46, all the numbers will fit into one of the above categories and thus all such numbers can be obtained. But 43 will be last number that will not fall into one of the above categories.
44 = 20 + 6 * 4, 45 = 6 * 6 + 9

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);

Thursday, June 12, 2014

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

Thursday, May 15, 2014

Skiplist - TOC

Following are the topics on skiplist:

Wednesday, May 14, 2014

Sql Query Interview Questions - Set 2

Here we will discuss most of the questions from the infibeam.

Q1 - How to get the employees with their managers ?

 Given the following columns, list the employees with the manager:
| emp_id | emp_name | mgr_id |

Where mgr_id is also an emp_id, i.e. every manager is employee. Here is the sql query:
select e1.emp_id , e1.emp_name,
from employees e1
inner join employees e2
  on e1.mgr_id = e2.emp_id

This is a self join. Here is sqlfiddle demo.and reference here.

Q2 - Count of positive and negative numbers in a column
select sum (case when acolumn >= 0 then 1 else 0 end) as positive,
       sum (case when acolumn < 0 then 1 else 0 end) as negative
from table

Here is the reference for the same.

Q3 - Can trigger be used with select statement?
Answer - No. We can not use trigger with select statement. It can only be used with insert/update/delete

Q4 - Given two tables
1. Candidate:  Id , Name
2. Vote: Id, CandidateId

Give query to give the name of the winning candidate

Here is the query:
select c.Name, count(c.Name) as Votes from Candidate c
join Vote v on c.Id = v.CandidateId
group by c.Name
order by COUNT(c.Name) desc

Q5 - Given 3 column table 

Id Key Value
-- --- -----
1 name hulk
2 age 22
3 name ironman
4 age 35

Write an efficient SQL Query to fetch the id of all users whose name starts with h and having age between 22 and 35. 

Note that column 2 is like a metadata, which is sometime name,sometime age. Also, column 3 i.e. Value is dependent on key column. This is again the example of self join. Here is the query :
SELECT t1.Id, t2.Id FROM
Users as t1 INNER JOIN Users as t2 ON t1.Id + 1=t2.Id AND t1.Key='name' AND t2.Key='age'
WHERE t1.Value LIKE 'h%' AND t2.Value >= 22 AND t2.Value <=35 

If the IDs has gaps, you need to Select RowNumber two and Compare based on RowNumber instead of Id


Tuesday, May 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?

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.

Monday, May 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%.