Saturday, April 18, 2015

Reverse the doubly linked list

Problem

Reverse the doubly linked list

Input
10 - 8 - 4 - 2

Output
2 - 4 - 8 - 12

Solution


Method 1 - Reversing the prev and next references
Reversing a doubly linked list is much simpler as compared to reversing a singly linked list. We just need to swap the prev & next references  in all the nodes of the list and need to make head point to the last node of original list (which will be the first node in the reversed list).

void reverseDLL(Node head)
 {
    while(head!=null)
    {
       // Swapping the prev & next pointer of each node
       Node t = head.prev;
       head.prev = head.next;
       head.next = t;
 
       if(head.prev != NULL)
          head = head.prev;  // Move to the next node in original list
       else
          break;              // reached the end. so terminate
    }
 }


Doubly linked list ADT

A doubly-linked list is a linked data structure that consists of a set of sequentially linked records called nodes. Each node contains two  fields, called links, that are references to the previous and to the next node in the sequence of nodes.

The beginning and ending nodes previous and next  links, respectively, point to some kind of terminator, typically a sentinel node or null, to facilitate traversal of the list. If there is only one sentinel node, then the list is circularly linked via the sentinel node. It can be conceptualized as two singly linked lists formed from the same data items,  but in opposite sequential orders.

ADT

    class Node {
        E element;
        Node next;
        Node prev;
 
        public Node(E element, Node next, Node prev) {
            this.element = element;
            this.next = next;
            this.prev = prev;
        }
    }


Operations

  • Insert
  • Delete
  • Update
  • Find

Java usage

java.util.LinkedList is a doubly-linked list.


Reference

Friday, April 17, 2015

Find the largest subarray with sum of 0 in the given array

Problem
An array contains both positive and negative elements, find the largest subarray whose sum equals 0.

Example
int[] input = {4,  6,  3, -9, -5, 1, 3, 0, 2}
int output = {4,  6,  3, -9, -5, 1} of length 6

Solution

Method 1 - Brute force

Method 2 - Storing the sum in temp array
Given an int[] input array, you can create an int[] tmp array where  
tmp[i] = tmp[i - 1] + input[i];

Each element of tmp will store the sum of the input up to that element.
Example
int[] input = {4,  6,    3, -9, -5, 1, 3, 0, 2}
int[] tmp =   {4, 10, 13,  4, -1, 0, 3, 3, 5}

Now if you check tmp, you'll notice that there might be values that are equal to each other.For example, take the element 4 at index 0 and 3, element 3 at index 6 and 7. So, it means sum between these 2 indices has remained the same, i.e. all the elements between them add upto 0. So, based on that we get {6, 3, -9} and {0}.

Also, we know tmp[-1] = 0. When we have not started the array we have no element added to it. So, if we find a zero inside the tmp array, that means all the numbers starting 0th index to 5th index(where 0 exists in temp) are all 0s, so our subarray becomes {4,6,3, -9,-5,1}.

Out of {6, 3, -9}, {0} and {4,6,3, -9,-5,1}, last one is our answer as it is the largest sub array.

To sum it up
We notice that some values are same in tmp array. Let's say that this values are at indexes j an k with j < k, then the sum of the input till j is equal to the sum till k and this means that the sum of the portion of the array between j and k is 0! Specifically the 0 sum subarray will be from index j + 1 to k.
  • NOTE: if j + 1 == k, then k is 0 and that's it! ;)
  • NOTE: The algorithm should consider a virtual tmp[-1] = 0;
  • NOTE: An empty array has sum 0 and it's minimal and this special case should be brought up as well in an interview. Then the interviewer will say that doesn't count but that's another problem! ;)

Here is the code
    public static string[] SubArraySumList(int[] array, int sum)
    {
        int tempsum;
        List<string> list = new List<string>();

        for (int i = 0; i < array.Length; i++)
        {
            tempsum = 0;

            for (int j = i; j < array.Length; j++)
            {
                tempsum += array[j];

                if (tempsum == sum)
                {
                    list.Add(String.Format("[{0}-{1}]", i, j));
                }
            }
        }
        return list.ToArray();
    }


References

Einsteen's 5 house riddle

Problem

Einstein wrote this riddle early during the 19th century. He said 98% of the world could not solve it. 

"There are 5 houses in 5 different colors. In each house lives a person with a different nationality. The 5 owners drink a certain type of beverage, smoke a certain brand of cigar, and keep a certain pet. No owners have the same pet, smoke the same brand of cigar, or drink the same beverage."
The question is: Who owns the fish?

Hints:
  1. The Brit lives in the red house.
  2. The Swede keeps dogs as pets.
  3. The Dane drinks tea.
  4. The green house is on the left of the white house.
  5. The green homeowner drinks coffee.
  6. The person who smokes Pall Mall rears birds.
  7. The owner of the yellow house smokes Dunhill.
  8. The man living in the center house drinks milk.
  9. The Norwegian lives in the first house.
  10. The man who smokes Blend lives next to the one who keeps cats.
  11. The man who keeps the horse lives next to the man who smokes Dunhill.
  12. The owner who smokes Bluemaster drinks beer.
  13. The German smokes prince.
  14. The Norwegian lives next to the blue house.
  15. The man who smokes Blend has a neighbor who drinks water.

 Solution
a) We know that Norwegian lives in the 1st house (Hint: #9) and next to him lives a  guy who stays in a blue house (Hint: #14). So far we have the following:
1st House 2nd House
Norwegian Blue House

b) We know that the green house is on the left of the white house (Hint: 4), therefore we can form a new group with the Green and White house next to each other.
Green House White House



c) Now think carefully the combination of (a) and (b). We should reach to the conclusion that the Norwegean guy who lives in the first house, he either lives in the Red or Yellow house since the Green & White houses group can only have a position of either 3-4 or 4-5.
d) Since the Brit is the guy who lives in the Red house (Hint: 1), now we definitely know that the Norwegian lives in the Yellow house. So far we have the following information:
1st House 2nd House
Norwegian
Yellow
Blue

British
Red

Group:
Green House White House



e) Next, we know that the owner of the Green house drinks coffee (Hint: 5) and the man living in the center house drinks milk (Hint: 8). As a result, we conclude that the group of Green and Yellow house are the 4th and 5th house in order and that the center house (number 3) is the Brit.
1 2 3 4 5
Norwegian
British

Yellow Blue Red Green White


Milk Coffee






f) Hint 7 gives us another information on the first house (The owner of the yellow house smokes Dunhill). In-addition, the man who keeps the horse lives next to the man who smokes Dunhill (Hint 11), therefore the man living in house #2 keeps horses.
House 1 2 3 4 5
Nation Norwegian
British

Color Yellow Blue Red Green White
Drink

Milk Coffee
Pet
 Horses


Smoke Dunhill




g) Hint 15 states that "The man who smokes Blend has a neighbor who drinks water."  We conclude that only 2 people can have a neighbor who drinks water (House 1&2), but since House #1 already smokes Dunhill that means that House #2 smokes Blend and House #1 drinks water.
House 1 2 3 4 5
Nation Norwegian
British

Color Yellow Blue Red Green White
Drink Water
Milk Coffee
Pet
 Horses


Smoke Dunhill  Blend



h) Hint 12 states "The owner who smokes Bluemaster drinks beer." See the table above and you will notice that we are missing the drink only for houses 2 and 5 but since we already know that the owner of house 2 smokes Blend, then the combination of Hint 12 applies to house #5.

House 1 2 3 4 5
Nation Norwegian
British

Color Yellow Blue Red Green White
Drink Water
Milk Coffee Beer 
Pet
 Horses


Smoke Dunhill  Blend

 Bluemaster

 i) Hint 3 states that "The Dane drinks tea.". We are missing only the drink for house #2 therefore this applies to house #2.
House 1 2 3 4 5
Nation Norwegian  Danish British

Color Yellow Blue Red Green White
Drink Water Tea  Milk Coffee Beer 
Pet
 Horses


Smoke Dunhill  Blend

 Bluemaster

j) Hint 10 states "The man who smokes Blend lives next to the one who keeps cats." As a result, house #1 keeps cats since house #2 has the owner who smokes Blend.

House 1 2 3 4 5
Nation Norwegian  Danish British

Color Yellow Blue Red Green White
Drink Water Tea  Milk Coffee Beer 
Pet Cats  Horses


Smoke Dunhill  Blend

 Bluemaster

k) Hint #13 states that "The German smokes prince". We are missing the nationalities of the owners who live in house #4 and #5 but since the owner of house #5 smokes Bluemaster, this hint applies to house #4.
House 1 2 3 4 5
Nation Norwegian  Danish British German
Color Yellow Blue Red Green White
Drink Water Tea  Milk Coffee Beer 
Pet Cats  Horses


Smoke Dunhill  Blend
Prince   Bluemaster

l) Hint #6 states that "The person who smokes Pall Mall rears birds". We are only missing the tabacco of House #3 therefore:
House 1 2 3 4 5
Nation Norwegian  Danish British German
Color Yellow Blue Red Green White
Drink Water Tea  Milk Coffee Beer 
Pet Cats  Horses Birds 

Smoke Dunhill  Blend  Pall Mall Prince   Bluemaster

m) Finally hint #2 states that "The Swede keeps dogs as pets". This combination can only be applied to house #5.
House 1 2 3 4 5
Nation Norwegian  Danish British German Swedish
Color Yellow Blue Red Green White
Drink Water Tea  Milk Coffee Beer 
Pet Cats  Horses Birds 
Dogs 
Smoke Dunhill  Blend  Pall Mall Prince   Bluemaster

n) Now who owns the fish? The German owns the fish!!!
Congratulations, according to Einstein you now belong to the 2% of the people who can solve this riddle!!!
House 1 2 3 4 5
Nation Norwegian  Danish British German Swedish
Color Yellow Blue Red Green White
Drink Water Tea  Milk Coffee Beer 
Pet Cats  Horses Birds  FISH Dogs 
Smoke Dunhill  Blend  Pall Mall Prince   Bluemaster


Reference

Find the maximum distance covered using n bikes

Problem

There are n bikes and each can cover 100 km when fully fueled. What is the maximum amount of distance you can go using n bikes? You may assume that all bikes are similar and a bike takes 1 litre to cover 1 km.

Solution

There are couple of ways. Lets find the right solution. Say n = 50.

Naive Solution:
The most naive solution would be to just make all the bikes go together. Hence, the maximum distance travelled will be 100km.

Better Solution:
Move all the bikes 50km, so that each bike has half tank empty.
Now pour the fuel of 25 bikes (whose tanks are half filled) into other 25 bikes. Now we have 25 bikes will full tanks and these 25 bikes can go upto 100km each
Repeat the same after next 50 km.
Hence the number of bikes will go down after every 50 km, like:
50 -> 25 -> 12 -> 6 -> 3 -> 1
Total distance covered will be 5*50 + 100= 350 kms (At the end you have a bike filled with 100km fuel).
Note: You can further optimize few more km, because we are ignoring one bike’s (50 km fuel) when 25->12 and 3->1.. Since it is not the best solution, I have ignored that.

Best Solution (Actual solution) :
In this solution we will vacate the tank of a bike as soon as there is capacity in other bikes (not waiting for 50 km). Lets do it by breaking into the cases. 
Case 1 - Only 1 bike - The biker will drive for 100 km
Case 2 - Only 2 bikes -  Both bikers will drive to the point such that first biker can transfer the fuel to the other guy. So, for the 1st 50km they will go together, and then the fuel in both will be 50L and then 1st biker will give fuel to the other biker, and that biker will cover the rest with 100L of fuel.
So, Distance = Distance covered together + distance covered by fuel transfer = 50 + 100 = 150 km
Case 3 - Only 3 bikes - All the bikers will travel together to the point where fuel of the 1st biker can fill the oil in other 2 bikes. So, first distance will be 33.3 km. After this other 2 bikers will take fuel from 1st one and it will become like the old case of 2 bikes. Answer = 33.3 + 150 = 100/3 + 100/2 + 100 /1 = 183.3 km.

So empty one bike into rest 49 bikes. (49*2 = 98).
Again travel a distance of 100/49km, that is sufficient to vacate the fuel of one more bike in other 48 bikes.
The actual number of km traveled will be:
= 100/50 + 100/49 +......+100/1 = 
= 449.92 km



References
http://www.geeksforgeeks.org/find-maximum-distance-covered-100-bikes/
http://www.ritambhara.in/maximum-distance-with-50-bikes-each-having-fuel-capacity-of-100-kms/

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.

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

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?

Solution

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. 

References
http://classic-puzzles.blogspot.in/2011/11/fox-and-duck-interview-puzzle.html