Wednesday, June 25, 2014

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      6
0

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

Solution

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

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:
  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>();
    next.add(root);
    //actual function
    levelOrder(next);
}
public void levelOrder(List<TreeNode> n) {
    List<TreeNode> next = new ArrayList<TreeNode>();
    for (TreeNode t : n) {
        if (t != null) {
            System.out.print(t.getValue());
            next.add(t.getLeftChild());
            next.add(t.getRightChild());
        }
    }
    System.out.println();
    if(next.size() > 0)levelOrder(next);
}

References

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

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,
  e2.emp_id
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
Query:
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

References

Tuesday, May 13, 2014

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?
 

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.
 

Monday, May 12, 2014

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

Solution
 

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 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?


Solution



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.

References

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

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

SQL Query interview questions - Set 1

Consider the employee table
>SELECT * FROM Employee;
+--------+----------+---------+--------+
| emp_id | emp_name | dept_id | salary |
+--------+----------+---------+--------+
| 1      | James    | 10      |   2000 |
| 2      | Jack     | 10      |   4000 |
| 3      | Henry    | 11      |   6000 |
| 4      | Tom      | 11      |   8000 |


Question 1: SQL Query to find second highest salary of Employee

Answer : There are many ways to find second highest salary of Employee in SQL, you can either use SQL Join or Subquery to solve this problem. Here is SQL query using Subquery :

select MAX(Salary) from Employee 
     WHERE Salary NOT IN (select MAX(Salary) from Employee );


See How to find second highest salary in SQL for more ways to solve this problem.

Question 2: SQL Query to find Max Salary from each department.


SELECT DeptID, MAX(Salary) FROM Employee GROUP BY DeptID

Question 3:Write SQL Query to display current date.

SQL has built in function called GetDate() which returns current timestamp.

SELECT GetDate();

Question 4:Write an SQL Query to check whether date passed to Query is date of given format or not.

SQL has IsDate() function which is used to check passed value is date or not of specified format ,it returns 1(true) or 0(false) accordingly.

SELECT ISDATE('1/08/13') AS "MM/DD/YY";

It will return 0 because passed date is not in correct format.

Question 5: Write a SQL Query to print the name of distinct employee whose DOB is between 01/01/1960 to 31/12/1975.

SELECT DISTINCT EmpName FROM Employees
          WHERE DOB BETWEEN ‘01/01/1960’ AND ‘31/12/1975’;


Question 6:Write an SQL Query find number of employees according to gender whose DOB is between 01/01/1960 to 31/12/1975.


SELECT COUNT(*), sex from Employees
      WHERE DOB BETWEEN ‘01/01/1960 ' AND ‘31/12/1975’ GROUP BY sex;


Question 7:Write an SQL Query to find employee whose Salary is equal or greater than 10000.

SELECT EmpName FROM Employees 
         WHERE Salary>=10000;


Question 8:Write an SQL Query to find name of employee whose name Start with ‘M’

Ans: SELECT * FROM Employees WHERE EmpName like 'M%';


Question 9: find all Employee records containing the word "Joe", regardless of whether it was stored as JOE, Joe, or joe.


SELECT * from Employees WHERE upper(EmpName) like upper('joe%');


Question 10: Write a SQL Query to find year from date.

SELECT YEAR(GETDATE()) as "Year";


Hope this article will help you to take a quick practice whenever you are going to attend any interview and not have much time to go into the deep of each query.