Monday, May 25, 2015

K reverse a linked list with increasing K

Problem
Reverse k elements in the linked list such that k goes on increasing

Example
Eg.        1 - 2 - 3 - 4 - 5 - 6 - 7
output - 1 - 3 - 2 - 6 - 5- 4 - 7

Solution

You can take this problem here. Here we are just increasing k.

   public static ListNode<Integer> reverseSubLinkLists(ListNode<Integer> headerNode) {
        
        ListNode<Integer> nextNode = headerNode.next;
        ListNode<Integer> startNode = null;
        ListNode<Integer> endNode = null;
        
        int k = 2;
        while (nextNode != null) {
            
            startNode = nextNode;
            endNode = nextNode;
            
            for (int i = 1; i < k; i++) {
                endNode = endNode.next;
                if (endNode == null) {
                    break;
                }
            }



            if (endNode != null) {
                // Save the node next to endNode
                nextNode = endNode.next;
                // Unlink the endNode
                endNode.next = null;
                // Reverse the list starting from startNode

                startNode = reverseListIterative(startNode);
                k++;
            } else {
                nextNode = null;
//              // Save the node next to endNode
//              nextNode = endNode.next;
//              // Unlink the endNode
//              endNode.next = null;
                // Reverse the list starting from startNode

                startNode = reverseListIterative(startNode);
            }

            if (headerNode == null) {
                headerNode = startNode;
            } else {
                headerNode.next = startNode;
                ListNode<Integer> temp = startNode;
                while(temp!=null){
                    if(temp.next==null){
                        break;
                    }
                    temp = temp.next;
                }
                headerNode = temp;
            }
        }

        return headerNode;
    }

    public static ListNode<Integer> reverseListIterative(ListNode<Integer> headerNode) {
        ListNode<Integer> prevNode = null;
        ListNode<Integer> currNode = headerNode;
        ListNode<Integer> nextNode = null;

        while (currNode != null) {
            nextNode = currNode.next;
            currNode.next = prevNode;
            prevNode = currNode;
            currNode = nextNode;
        }

        return prevNode;
    }
    

Time complexity - O(n)

Saturday, May 16, 2015

Convert Binary Tree to Doubly linked list in level order

Question: write an algorithm to convert a binary tree into a double linked list. For example, if the input is the binary tree below:


The output will be a double linked list like this:


Solution: there are two tasks in converting a binary tree to a linked list. First of all, we must traverse the tree and visit all the nodes. Second of all, we must break each node from the tree and add it into the linked list.
For traversing the tree, we'll use level / order traversal a.k.a breadth first search.

To construct the linked list, each node will have its left pointer point to the node in front of it and its right pointer point to the node behind it in the linked list. For instance, if node 1 is in front of node 2 and node 3 is behind node 2 in the linked list, we'll set left pointer of node 2 to node 1 and right pointer of node 2 to node 3 (see picture above)
#include<iostream>
#include<queue>
using namespace std;
struct Node
{
  int data;
  struct Node* left;
  struct Node* right;
};
struct Node* bt2DoubleLinkedList(struct Node* root)
{
  if (root == NULL)
    return NULL;
  queue nodeQueue;
  struct Node* head = root; //reference to head of the linked list
  struct Node* listIT = NULL; //current node being processed
  struct Node* prevNode = NULL; //previous node processed
  //initialize the stack
  nodeQueue.push(root);
  //convert to double linked list
  while (!nodeQueue.empty())
  {
    //process next node in stack
    prevNode = listIT;
    listIT = nodeQueue.front();
   
    nodeQueue.pop();
    //add left child to stack
    if (listIT->left != NULL)
      nodeQueue.push(listIT->left);
    //add right child to stack
    if (listIT->right != NULL)
      nodeQueue.push(listIT->right);
    //add current node to linked list
    if (prevNode != NULL)
      prevNode->right = listIT;
    listIT->left = prevNode;
  }
 
  //connect end node of list to null
  listIT->right = NULL;
  return head;
}

Explanation: the method accepts a pointer to the tree's root as argument and returns the pointer to the head node of the linked list:
  1. If the root node is null, we return null because the tree is empty.
  2. If the root is not null, we proceed by first creating a queue to store the the nodes. Why do we use queue? That is how we traverse the tree by level. Every time we reach a node, we store its children in the queue for later processing. Thus, the queue will always have something in it as long as there are still unvisited node in the tree.
  3. Next, we create three pointers. head points to the head node of the linked list. listIT is our list iterator which used to build the list one node at a time. prevNode is the last node added into the list. We need to keep track of such node because we have to change the right pointer of that node to the node immediate after it, which is the node that listIT will point to.
  4. We initialize the queue by adding the root into it. The reason is that we will use the condition of empty queue to end the while loop.
  5. The while loop will run until no node left in queue to process. For each node in the queue, we do the following:

    prevNode = listIT gets reference to the last processed node because we are about to process a new node

    listIT = nodeQueue.front() gets reference to the top in the queue because we're going to add it into the list.

    nodeQueue.pop() removes the top node out of the queue.

    We then add the left and right child of the top node into the queue, so we can process them later. Notice that we only add the children if they are not null.

    Finally, we connect the top node to the linked list. First, we set the right pointer of the previous node (prevNode) to the top node. Then, we set the left pointer of the top node to the previous node. As the result, the top node becomes the end node of the linked list and the previous node completely breaks off the tree.

  6. When the last node is added into the linked list and the while loop exits, we have a double linked list. The only thing left is to set the end node's right pointer (pointed to by listIT) to null because there is no more node to add into the list.

Sunday, May 3, 2015

Number of steps required to convert string 1 to string2 when only bring character to first index operation is giving

Problem
Given 2 strings - s1 and s2, when only 1 operation is allowed - Moving character at a time but only to the first position.

Example
Example 1
Input
s1 = abcd
s2 = bacd

Output
Ans = 1
Reason, just move b forward and we get it.

Example 2
Input
A = (a)b(cd)e(f)g(hij)
B = ahdjcifbeg
Output
Ans =7
Explanation
A = (a)b(cd)e(f)g(hij)
B = ahdjcifbeg
Characters b,e,g are in the order, rest characters have to brought first.


Solution

This is a DP problem,  LCS of the 2 strings is adf, and rest of the character are moved forward, and rest of the characters will be moved forward.

Maximize the number of magical gems by passing through array of house

Problem
There was a thief, he has to pass through colored house - which can be red or blue, and contain 0 or more gems. The property of these gems is they multiply the previous gems by the current gems in the house. The houses are in array and thief can only visit once to steal the gems, with the goal of maximizing the gems. Find the range of house where he can maximize the gems in such a way that number of red houses are even.

Example
Gem array = 1 2 0 4 5 6 2 3
color array = 0 0 1 1 1 0 0 1 (r=1,b=0)
o/p = 20 (4*5)

Solution

This is similar to maximum product subarray, but there is another condition of red color.

Here is the code below:
int maximumMoney(int n, int[] colour, int[] gems) {
    int max = 1;
    int red = 0;
    int start = 0, end = 0;
    int actualMax=1;
    for(int i=0;i<gems.length;i++){
        if(gems[i]>0)
        {
            max = max*gems[i];
            end++;
            if(colour[i] == 1)
               red++;
            
               
        }else{
            if(actualMax < max){
                if(red%2==0)
                {
                    actualMax = max;

                }else{
                    int temp = max;
                    int startRed = -1, endRed = -1;
                    for(int i=start;i<end;i++){
                        if(colour[i]==1 && startRed==-1){
                           startRed = i;
                           endRed = i;
                        }else if(colour[i]==1)
                            endRed = i;
                    }
                    int tempProdStart = 1; tempEndProd = 1;
                    for(int i=start;i<=startRed;i++){
                        tempProdStart = a[i]*tempProdStart ;
                        
                    }
                    
                     for(int i=endRed;i<=end;i++){
                        tempEndProd= a[i]*tempEndProd;
                        
                    }
                    int minProd = Math.min(tempProdStart, tempEndProd);
                    
                    max = temp/minProd;
                    if(max > actualMax){
                        actualMax = max;
                    }
                        
                    
                }
                   
            }
              
            start = end+1;
            end = end + 1;
            
        }
    }
}

Time complexity - O(n)



Find the least wastage in cutting the Trees?

Problem
You are given n Trees with their heights in an array. and you are given a value k units , that much wood you need to collect. You can have an axe of any height you want but you can use only 1 axe when you choose.

Assume height to be integral value.

Solution

So, if height of the tree is H, and you cut it at height X from the ground then H-X will be used will be used. If there is only 1 tree, we will cut it at height X, such that H-X = k.

It is always possible to choose an axe height such that chopping all trees above this height will result in zero waste.
To see this, just sort the trees in descending order of height, and consider moving the axe height gradually down from the top of the tallest tree.

Suppose the tallest tree has height h. Notice that the function:

f(x) = total amount of wood cut by using an axe of height h - x to
       chop all trees of at least this height

  • Sort the trees by their height in descending order
  •  starts at 0 when x = 0, and is an increasing piecewise linear function of x, with no discontinuities. Every time x increases past the point when one or more trees just start to become choppable, the rate of change of f(x) increases, but this doesn't cause problems. 
  • So for any desired level of wood y, just (conceptually) intersect a horizontal line of height y with the graph f(x), and drop a vertical line from this point down to the x axis to find its value. (How to actually do this in a program I leave as an exercise, but here's a hint: consider trees in decreasing height order to find the pair of adjacent x values x1, x2 such that chopping at h - x1 produces too little wood, and h - x2 produces too much.)

Reference




Implement a function similar to diff command in linux

Problem

Give logic for implementing "diff" command in Linux.
Consider various test cases and explain what will happen in each. The two files are source code and are huge..
For e.g.
File 1: 1-2-3-4
File 2: 1-3-4-2

Solution

The operation of diff is based on solving the longest common sub-sequence problem.
In this problem, you have two sequences of items:
a b c d f g h j q z
a b c d e f g i j k r x y z
and you want to find a longest sequence of items that is present in both original sequences in the same order. That is, you want to find a new sequence which can be obtained from the first sequence by deleting some items, and from the second sequence by deleting other items. You also want this sequence to be as long as possible. In this case it is
a b c d f g j z
From a longest common subsequence it's only a small step to get diff-like output: if an item is absent in the subsequence but present in the original, it must have been deleted. (The '–' marks, below.) If it is absent in the subsequence but present in the second sequence, it must have been added in. (The '+' marks.)
e h i q k r x y
+ - + - + + + +


Resource



Thursday, April 30, 2015

Maximum single sell profit from stock

Problem
Suppose we are given an array of n integers representing stock prices on a single day. We want to find a pair (buyDay, sellDay), with buyDay ≤ sellDay, such that if we bought the stock on buyDay and sold it on sellDay, we would maximize our profit.

OR

Given an array arr[] of integers, find out the difference between any two elements such that larger element appears after the smaller number in arr[].


Example
Input = {5        10         4         6        7}
Output = 5,10 => buy at 5 and sell at 7


Solution


Method 1 - Brute force
Clearly there is an O(n2) solution to the algorithm by trying out all possible (buyDay, sellDay) pairs and taking the best out of all of them. However, is there a better algorithm, perhaps one that runs in O(n) time?

int maxDiff(int arr[], int arr_size)
{     
  int max_diff = arr[1] - arr[0];
  int i, j;
  for(i = 0; i < arr_size; i++)
  {
    for(j = i+1; j < arr_size; j++)
    {        
      if(arr[j] - arr[i] > max_diff)   
         max_diff = arr[j] - arr[i];
    }    
  }          
  return max_diff;
}    

Method 2 - Divide and Conquer
If we have a single day, the best option is to buy on that day and then sell it back on the same day for no profit. Otherwise, split the array into two halves. If we think about what the optimal answer might be, it must be in one of three places:
  1. The correct buy/sell pair occurs completely within the first half.
  2. The correct buy/sell pair occurs completely within the second half.
  3. The correct buy/sell pair occurs across both halves - we buy in the first half, then sell in the second half.
We can get the values for (1) and (2) by recursively invoking our algorithm on the first and second halves. For option (3), the way to make the highest profit would be to buy at the lowest point in the first half and sell in the greatest point in the second half. We can find the minimum and maximum values in the two halves by just doing a simple linear scan over the input and finding the two values. This then gives us an algorithm with the following recurrence:
T(1) <= O(1)
T(n) <= 2T(n / 2) + O(n)
Using the Master Theorem to solve the recurrence, we find that this runs in O(n lg n) time and will use O(lg n) space for the recursive calls. We've just beaten the naive O(n2) solution!

Method 3 - Optimized divide and conquer
But wait! We can do much better than this. Notice that the only reason we have an O(n) term in our recurrence is that we had to scan the entire input trying to find the minimum and maximum values in each half. Since we're already recursively exploring each half, perhaps we can do better by having the recursion also hand back the minimum and maximum values stored in each half! In other words, our recursion hands back three things:
  1. The buy and sell times to maximize profit.
  2. The minimum value overall in the range.
  3. The maximum value overall in the range.
These last two values can be computed recursively using a straightforward recursion that we can run at the same time as the recursion to compute (1):
  1. The max and min values of a single-element range are just that element.
  2. The max and min values of a multiple element range can be found by splitting the input in half, finding the max and min values of each half, then taking their respective max and min.
If we use this approach, our recurrence relation is now
T(1) <= O(1)
T(n) <= 2T(n / 2) + O(1)
Using the Master Theorem here gives us a runtime of O(n) with O(lg n) space, which is even better than our original solution!

Method 4 - Use the difference between adjacent element
First find the difference between the adjacent elements of the array and store all differences in an auxiliary array diff[] of size n-1. Now this problems turns into finding the maximum sum subarray of this difference array.
int maxDiff(int arr[], int n)
{
    // Create a diff array of size n-1. The array will hold
    //  the difference of adjacent elements
    int diff[n-1];
    for (int i=0; i < n-1; i++)
        diff[i] = arr[i+1] - arr[i];
 
    // Now find the maximum sum subarray in diff array
    int max_diff = diff[0];
    for (int i=1; i<n-1; i++)
    {
        if (diff[i-1] > 0)
            diff[i] += diff[i-1];
        if (max_diff < diff[i])
            max_diff = diff[i];
    }
    return max_diff;
}

Example
input = 
Time Complexity: O(n)
Auxiliary Space: O(n)

Method 5 - Optimizing the diff approach
We can modify the above method to work in O(1) extra space. Instead of creating an auxiliary array, we can calculate diff and max sum in same loop. Following is the space optimized version.
int maxDiff (int arr[], int n)
{
    // Initialize diff, current sum and max sum
    int diff = arr[1]-arr[0];
    int curr_sum = diff;
    int max_sum = curr_sum;
 
    for(int i=1; i<n-1; i++)
    {
        // Calculate current diff
        diff = arr[i+1]-arr[i];
 
        // Calculate current sum
        if (curr_sum > 0)
           curr_sum += diff;
        else
           curr_sum = diff;
 
        // Update max sum, if needed
        if (curr_sum > max_sum)
           max_sum = curr_sum;
    }
 
    return max_sum;
}

Time Complexity: O(n), Auxiliary Space: O(1)

Method 6 -  Dynamic programming (Preferred and easy :))
But wait a minute - we can do even better than this! Let's think about solving this problem using dynamic programming. The idea will be to think about the problem as follows. Suppose that we knew the answer to the problem after looking at the first k elements. Could we use our knowledge of the (k+1)st element, combined with our initial solution, to solve the problem for the first (k+1) elements? If so, we could get a great algorithm going by solving the problem for the first element, then the first two, then the first three, etc. until we'd computed it for the first n elements.
Let's think about how to do this. If we have just one element, we already know that it has to be the best buy/sell pair. Now suppose we know the best answer for the first k elements and look at the (k+1)st element. Then the only way that this value can create a solution better than what we had for the first k elements is if the difference between the smallest of the first k elements and that new element is bigger than the biggest difference we've computed so far. So suppose that as we're going across the elements, we keep track of two values - the minimum value we've seen so far, and the maximum profit we could make with just the first k elements. Initially, the minimum value we've seen so far is the first element, and the maximum profit is zero. When we see a new element, we first update our optimal profit by computing how much we'd make by buying at the lowest price seen so far and selling at the current price. If this is better than the optimal value we've computed so far, then we update the optimal solution to be this new profit. Next, we update the minimum element seen so far to be the minimum of the current smallest element and the new element.

Since at each step we do only O(1) work and we're visiting each of the n elements exactly once, this takes O(n) time to complete! Moreover, it only uses O(1) auxiliary storage. This is as good as we've gotten so far!
As an example, on your inputs, here's how this algorithm might run. The numbers in-between each of the values of the array correspond to the values held by the algorithm at that point. You wouldn't actually store all of these (it would take O(n) memory!),

Time - O(n), Space - O(1) solution:

public static int findMaxProfit(int[] stockPriceSamples) {
 int maxProfit = 0;
 int minTillNow = stockPriceSamples[0];
 for (int i = 0; i < stockPriceSamples.length; i++) {
  int profit = stockPriceSamples[i] - minTillNow;
  maxProfit = Math.max(profit, maxProfit);
  minTillNow = Math.min(stockPriceSamples[i], minTillNow);
 }
 return maxProfit;
}

Example
input = {5        10         4         6        7}
i = 0, maxProfit = 0, minTillNow=5
i = 1, maxProfit=5, minTillNow=5
i= 2, maxProfit = 5,minTillNow=4
i=3,maxProfit=5,minTillNow=4
i= 4,maxProfit=5,minTillNow=5


References

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
This is simple. Will write later (incomplete)

Method 2 - Storing the sum upto ith element 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();
    }

Here is the solution using Hashmap, iterate over it again to get the max subarray:

public static void subArraySumsZero() {
    int [] seed = new int[] {1,2,3,4,-9,6,7,-8,1,9};
    int currSum = 0;
    HashMap<Integer, Integer> sumMap = new HashMap<Integer, Integer>();
    for(int i = 0 ; i < seed.length ; i ++){
        currSum += seed[i];
        if(currSum == 0){
            System.out.println("subset : { 0 - " + i + " }");
        }else if(sumMap.get(currSum) != null){
            System.out.println("subset : { " + (sumMap.get(currSum) + 1) + " - " + i + " }");
            sumMap.put(currSum, i);
        }else
            sumMap.put(currSum, i);
    }
    System.out.println("HASH MAP HAS: " + sumMap);
}


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.

Problem

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.

Examples


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

Solution


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. 


Method 2 - Using recursion
here is the pseudocode:

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

bool isMirrorItselfIteratively(BinaryTreeNode *root) 
{
    /// use single queue
    if(!root) return true;
    queue<BinaryTreeNode> q;
    q.push(root.left);
    q.push(root.right);
    BinaryTreeNode 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 || l.data!=r.data) return false;
        q.push(l.left);
        q.push(r.right);
        q.push(l.right);
        q.push(r.left);
    }

    return true;
}


Thanks.

References 

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