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

Time complexity - O(n)

Reference
http://www.geeksforgeeks.org/reverse-a-doubly-linked-list/

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/