Tuesday, February 17, 2015

Angular JS interview questions

Friday, November 21, 2014

Foldable Binary Trees - Given a binary tree, find out if the tree can be folded or not.

Question: Given a binary tree, find out if the tree can be folded or not.
A tree can be folded if left and right subtrees of the tree are structure wise mirror image of each other. An empty tree is considered as foldable.
Consider the below trees:
(a) and (b) can be folded.
(c) and (d) cannot be folded.

     /    \
    7      15
     \    /
      9  11

       /  \
      7    15
     /      \
    9       11

       /  \
      7   15
     /    /
    5   11


       /   \
      7     15
    /  \    /
   9   10  12
Method 1 (Change Left subtree to its Mirror and compare it with Right subtree)
Algorithm: isFoldable(root)
1) If tree is empty, then return true.
2) Convert the left subtree to its mirror image
    mirror(root->left); /* See this post */
3) Check if the structure of left subtree and right subtree is same
   and store the result.
    res = isStructSame(root->left, root->right); /*isStructSame()
        recursively compares structures of two subtrees and returns
        true if structures are same */
4) Revert the changes made in step (2) to get the original tree.
5) Return result res stored in step 2. 


Saturday, October 18, 2014

Given a node in binary tree - Check if left and right subtree are mirror of each other


A binary tree is a mirror image of itself if its left and right subtrees are identical mirror images i.e., the binary tree is symmetrical. This is best explained with a few examples.


 / \
2   2
  / \
 2   2
   /   \
  2     2
 / \   / \
4   3 3   4
     /   \
    2     2 
   / \   / \
  3   4 3   4
     /   \
    2     2
   /       \
  3         3


Method 1 - Recursiion mirrorEquals(BTree left , BTree right)
Basically compare the left subtree and inverted right subtree, drawing an imaginary line of inversion across root.
boolean mirrorEquals(BTree left, BTree right) {
  if (left == null || right == null) return left == null && right == null;
  return left.value == right.value 
         && mirrorEquals(left.left, right.right) 
   && mirrorEquals(left.right, right.left);

Method 2 - Iterative solution using queue
Insert 2 elements at a time and then pop and compare the values, and continue to do with the children.

bool isMirrorItselfIteratively(BTree root) 
    /// use single queue and initial push
    if(!root) return true;
    queue<btree> q;
    BTree l, r;
    while(!q.empty()) {
        l = q.front();
        r = q.front();
        if(l==NULL && r==NULL) continue;
        if(l==NULL || r==NULL ) return false;
  if(l.data!=r.data) return false;
  //not the push ordering

    return true;


Friday, October 17, 2014

Queue ADT

Definition :-
A queue is a collection of same type of entities, which ensures that all entities in collection will have a sequential storage structure that permits access only at the two ends of the sequence.  We refer to the ends of the sequence as the front and rear.  The first element in queue have the position as front and value or pointer or front changes according to the solution of the given problem. Rear is the terminal position of the queue, this can be the position of the last element or last point of the queue. A queue inserts new elements at the rear and removes elements from the front of the sequence, to maintain the sequential storage structure.  You will note that a queue removes elements in the same order in which they were stored, and hence a queue provides FIFO (first-in / first-out), or FCFS (first-come, first-served), ordering.

Example :-  Consider that you and your family went zoo. First you have to buy a ticket, so you or one of member of your group have to join the line for ticket counter. every person in that line will get the ticket in same sequence, in which they join that line. So this is one of the common example of queue.

Advanced Data Structure of Queue:- 

Advanced data structure involve the following steps:
  • how to define a data structure type,
  • create a data structure to implement the function performed by or associated to the new type
  • implement the above two in any programming language.
There are many operations which we can perform with a queue to solve any problem. Basic operations or function of queue are as follows:
  • queue() creates a new queue that is empty. It needs no parameters and returns an empty queue.
  • enqueue(item) adds a new item to the rear of the queue. It needs the item and returns nothing.
  • dequeue() removes the front item from the queue. It needs no parameters and returns the item. The queue is modified.
  • isEmpty() tests to see whether the queue is empty. It needs no parameters and returns a boolean value.
  • size() returns the number of items in the queue. It needs no parameters and returns an integer.

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?


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.