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.

(a)
       10
     /    \
    7      15
     \    /
      9  11

(b)
        10
       /  \
      7    15
     /      \
    9       11

(c)
        10
       /  \
      7   15
     /    /
    5   11

(d)

         10
       /   \
      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.
    mirror(root->left);
5) Return result res stored in step 2. 

References 
http://www.geeksforgeeks.org/foldable-binary-trees

Saturday, October 18, 2014

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

Problem

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.

Example


  1
 / \
2   2
TRUE
   1
  / \
 2   2
  \
   3
FALSE
     1
   /   \
  2     2
 / \   / \
4   3 3   4
TRUE
       1
     /   \
    2     2 
   / \   / \
  3   4 3   4
FALSE
       1
     /   \
    2     2
   /       \
  3         3
TRUE

Solution

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;
    q.push(root.left);
    q.push(root.right);
 
    BTree l, r;
    while(!q.empty()) {
        l = q.front();
        q.pop();
        r = q.front();
        q.pop();
        if(l==NULL && r==NULL) continue;
        if(l==NULL || r==NULL ) return false;
  if(l.data!=r.data) return false;
  //not the push ordering
        q.push(l.left);
        q.push(r.right);
        q.push(l.right);
        q.push(r.left);
    }

    return true;
}

References 

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

Problem

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 ?

Solution

43

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

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