Max gain from given stock values

Given ticker value for a stock, for next n days, given what is the max profit that you can make ?
Eg - the max profit you can make is buy at time t1 @ 5 and sell @ t2 when stock was 12, to get max Profit of 7 dollars.

time - Stock Price
t0 - 10
t1 - 5
t2 - 12
t3 - 7
t4 - 12

Also - you can only trade once i.e you can buy and sell only 1 time.
so here is the solution of that problem .that problem is nothing just think like that if we have only one day stock values so we can buy or sell on that day only , so for general we can find the for up to kth day and we can find out for the k+1'th day ..

so algo is that maintain the 3 things first two pointer of buy and sell and one pointer of minimum values .we can make it in O(n) only


Just make a new array which contains the "lookahead" view, where we can see, which potential highest value we can gaini in future.
Another array just contains the lowest value so far. When the difference between the two arrays is max, there is the buying point. Selling point is, when the falling edge of the max array is reached.

    public void highestGain(int[] prices) {
        int[] maxPrices = new int[prices.length];
        int[] minPrices = new int[prices.length];
        maxPrices[maxPrices.length-1] = prices[prices.length-1];
        minPrices[0] = prices[0];
        for(int i = 1; i<prices.length; i++) {
            int right = prices.length-i-1;
            minPrices[i] = Math.min(minPrices[i-1], prices[i]);
            maxPrices[right] = Math.max(maxPrices[right+1], prices[right]);
        }
        System.out.println("MaxPrices: " + Arrays.toString(maxPrices));
        System.out.println("MinPrices: " + Arrays.toString(minPrices));

        // find when to buy (when the difference of min/max is highest)
        int maxDifference = maxPrices[0] - minPrices[0];
        int maxDifferencePos = 0;
        for(int i=0; i<minPrices.length; i++) {
            int difference = maxPrices[i] - minPrices[i];
            if(maxDifference < difference) {
                maxDifference = difference;
                maxDifferencePos = i;
            }
        }
        // Now find the falling edge of max prices - there was the last peak
        int sellPos = maxDifferencePos+1;
        int lastPrice = maxPrices[maxDifferencePos];
        for(; sellPos < maxPrices.length; sellPos++) {
            if(lastPrice > maxPrices[sellPos]) {
                sellPos --;
                break;
            }
        }

        System.out.println("Ideal to buy/sell: " + maxDifferencePos + ":" + sellPos);
    }

Alien Chef

A new programming Problem.....


//http://www.codechef.com/problems/DOWNLOAD
/*


The aliens living in outer space are very advanced in technology, intelligence and everything, except one, and that is Cooking. Each year they spend millions of dollars in research, to crack famous recipes prepared by humans.
Recently they came to know about Khana-Academy, a non-profit organization streaming free cooking lesson videos on earth. There are N recipes, numbered 1 to N, and the video of the ith recipe is live in the time interval [Si, Ei]. An alien can visit earth but can not survive for more than just a small moment (earth is so advanced in pollution). An alien visits the earth at an integer time t and instantly downloads the complete video of all the lessons that are live at that moment of time t and leaves earth immediately. You are given the visiting times of a small group of K aliens. Find the number of different recipes aliens can learn by watching the downloaded videos. Not just one group of aliens, there are Q such groups, so you have to find the answer for each of these Q groups.
Input

The first line has an integer N. Each of the following N lines has two integers Si Ei. The next line has an integer Q, the number of groups. Each of the following Q lines has information of a group of aliens. The first integer is K, the number of aliens in that group, followed by K integers in the same line, the integer visiting times t of the aliens.

1 ≤ N ≤ 100000 (105)
1 ≤ Q ≤ 5000 (5 103)
1 ≤ K ≤ 20
1 ≤ Si, Ei, t ≤ 1000000000 (109)
Si < Ei

Output

For each of the Q groups, output the number of different recipes that group of aliens can learn by watching the downloaded videos.
Example

Input:
4
1 4
3 10
2 6
5 8
3
1 5
2 2 6
3 1 10 9

Output:
3
4
2

Explanation:
Given videos of 4 recipes in the following closed intervals.
1. [ 1 , 4 ]
2. [ 3 , 10 ]
3. [ 2 , 6 ]
4. [ 5 , 8 ]

In the first query, only one alien arrives at t = 5 and can download 3 recipes 2, 3, 4.

In the second query, two aliens arrive at t = 2 and 6. They can learn all the 4 recipes.

In the third query, three aliens arrive at t = 1, 10 and 9. They can learn only two recipes, 1 and 2.

*/



import java.util.*;
import java.lang.*;
/*public class Array
{
int num[]  = new int[20];



}
*/
public class AlienChefs
{
static int aaa[] = new int[100000];
static int end ;
//leng = 1;
static int start ;
public static void main(String [] args)
{

Scanner sc = new Scanner(System.in);
int n = sc.nextInt();
if((0<n) && (n<= 100000))
{
int a[] = new int[2*n];
int add = 10;
for(int i = 0 ; i<(2*n) ; ++i)
{
//System.out.println("Inside");

a[i] = sc.nextInt();
if( (0<a[i])&&(a[i]< 1000000000) )
{
if((i%2) == 1   )
{
//System.out.println("Inside");
if((a[i-1] > a[i]))
System.exit(0);
}

}
else 
System.exit(0);
}
int groups = sc.nextInt();
//System.out.println("********************");
//int address[] = new int[groups];
for(int i = 0 ; i< groups; ++i)
{
int count = 0 ;
int alen = 0 ;
int times = sc.nextInt();
for(int j =0 ;j<times ; j++)
{

alen = sc.nextInt();
if((0<alen)&&(alen<=20))
{
//System.out.println(alen);
count = count+ cc(a , alen);

}

}
start = end - start;
start = start +end + add ;
end = start;
aaa[start] = 1000;
System.out.println(count);

}
}

}
static int cc(int a [] , int val)
{
int count = 0 ;

for(int i = 0 ; i< a.length; i++)
{ //static int a;
int abc =0;


if((a[i] <= val)&& (val <= a[i+1] ))
{
//System.out.println("***************************************");
abc = check(aaa , i);
if( abc == 0)
{
++count;
}

}
++i;

}
//System.out.println("Count Returned :"+count);

return count;
}
static int check(int qw [], int i)
{
//System.out.println("Check Function is called ");
//System.out.println(start+":"+end);
//System.out.println("i = "+i);
for(int j = start ; j<=end ; j++)
{
if(qw[j] == i)
return 1;
}
qw[end] = i;
//System.out.println(qw[end]+"   :::::::Value Added");
++end;
return 0;

}
}

How Many Ip Address !!!

Hi Friends new problem


Given a string containing only digits, restore it by returning all possible valid IP address combinations.
For example:
Given "25525511135",
return ["255.255.11.135", "255.255.111.35"]{hint:recursion,backtrack}


Here is the Solution ...... 
it was taken me about 5 hours to solve see !!!

//cc Arun Kumar Gupta


import java.util.*;
public class AllIpAddress
{
    public static void main (String [] args)
    {
        Scanner sc = new Scanner(System.in);
        String input = sc.next();
        int[] intArray = new int[input.length()];
        int length = input.length();

        for (int i = 0; i < input.length(); i++) {
        intArray[i] = Character.digit(input.charAt(i), 10);
        //System.out.println(intArray[i]);
        }
        int i = 0 , j = 1 , k = 2;
        AllIpAddress ip = new AllIpAddress();
        ip.Ipaddress(intArray , i , j , k , length-1);   
       
       
       
    }
    void Ipaddress(int [] intArray , int i , int j , int k , int length)
    {
        try{
        int where = 0 ,change = 0;
        int p1 =createIP( intArray , -1 , i);
        int p2 =createIP( intArray , i ,  j );
        int p3 =createIP( intArray ,  j , k );
        int p4 =createIP( intArray ,  k ,  length );
        //System.out.println("**********Garbage"+p1+"."+p2+"."+p3+"."+p4);
        //System.out.println("i = "+i+"j = "+j+"k = "+k);
        if((p1<=255)&&(p2<=255)&&(p3<=255)&&(p4<=255)&&(p4>0))
        {
            System.out.println(p1+"."+p2+"."+p3+"."+p4);
        }
        if(p4 >255)
        {
            //if(k != j)
            //++k;
            where =4;
            //System.out.println("Problem at P4");
        }
        else if(p3>255)
        {
            //if(j != i)
            //++j;
            //--k;
            where = 3;
            //System.out.println("Problem at P3");
        }
        else if(p2>255)
        {
            //++i;
            where = 2;
            //System.out.println("Problem at P2");
        }
        else if(p1>255)
        {
           
            //System.out.println("Problem at P1");
            System.exit(0);
        }
       
        if((k == length) && (j+1 == k))
        {
            //System.out.println("if((k == length) && (j+1 == k))");
            //System.out.println(i+"_"+j+"_"+k);
            ++i;
            j = i+1;
            k = j+1;
            change = 1;
            //System.out.println(i+"_"+j+"_"+k);
           
        }
        if((k == length) &&(change == 0) )
        {
            //System.out.println("if((k == length) &&(change == 0) )");
            ++j;
            k = j+1;
            change = 0;
        }
        else if(change == 0)
        {
            if( (k) < length )
            ++k;       
        }
        /*if(where ==4)
        {
            ++k;           
        }
        if(where ==3)
        {
            ++j;
            --k;
        }
        if(where ==2)
        {
            ++i;
            --j;
        }
        /*if(k==length)
        {
            --k;
            --j;
        }*/
        Ipaddress(intArray , i , j , k , length);   
        }
        catch(ArrayIndexOutOfBoundsException e){
                 //System.out.println("Exception thrown  :" + e);
                      }
    }
    static int createIP(int [] intArray , int start , int end)
        {
            //System.out.println("I am at createIP()start = "+start+"\tend = "+end);
            int val = 1 , fina = 0;
            for(int e =end ; e>start ; --e)
            {
                 fina = intArray[e]*val + fina; 
                 val = val*10;
            }
            return fina;
        }
}
 

Write a program to find if a tree is symmetric.

Solution #1: A symmetric binary tree is one where if you draw a vertical line passing through the root node then the left half should be the mirror image of the right half. Here is the recursive code,

int isSymmetric(struct node* l, struct node* r)
{
    if((l == NULL) && (r == NULL))
        return 1;

    if(((l == NULL) && (r != NULL)) || 
            ((l != NULL) && (r == NULL)))
        return 0;

    return isSymmetric(l->left, r->right) && isSymmetric(l->right, r->left);
}

Print a n*n matrix in spiral order

Print a n*n matrix in spiral order and what will be the consequences(if u use recursion) in case of larger matrices like 10000*10000

we can not use the recursion b'coz stack overflow may occur.
so we can not use the recursion !!!
cc to Arun Kumar Gupta !!

import java.util.*;
import java.lang.*;
public class MatrixWithRotation_In_Java
{
    public static void main (String [] args)
    {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        System.out.println(n+"\n");
       
        int [][] a = new int[n][n];
        String stat = "RR";
        int i=0 , j = 0 , el = 0 , c= 0 ,eu = 1 , cb = n-1 , rb = n-1 , change = 1 ;
        System.out.println("cb :"+cb+"\n");
        System.out.println("rb :"+rb+"\n");
        for(int k = 0 ; k<(n*n + 20) ; ++k)
        //while(a[i][j] == 0)
        {
            if(change == 1)
            {
            System.out.println(i+"\t" + j +"\n");
            ++c;
            a[i][j] = c;
            }
           
           
            if(stat.equals("RR"))   
            {
                System.out.println("RR\n");
                if(j+1<=cb)
                {
                change = 1;
                ++j;}   
               
                else
                {
                    stat = "CD";
                    --cb;   
                    change = 0;       
                }
            }
           
            if(stat.equals("CD"))   
            {
                System.out.println("CD\n");
                if(i+1<=rb)
                {
                ++i;
                change = 1;
                }   
                else
                {
                    stat = "RL";
                    --rb;   
                    change = 0;       
                }
            }
            if(stat.equals("RL"))   
            {
                System.out.println("RL\n");
                if(j-1>=el)
                {
                --j;
                change = 1;
                }   
                else
                {
                    stat = "CU";
                    change = 0;   
                    ++el;       
                }
            }
            if(stat.equals("CU"))   
            {
                System.out.println("CU\n");
                if((i-1>=eu) )
                {
                --i;
                change = 1;
                }   
                else
                {
                    stat = "RR";
                    ++eu;   
                    change = 0;   
                }
            }
           
        }
        for(int k = 0 ; k<n ; ++k)
        {
            for(int l = 0 ; l<n ; ++l)
            {
                System.out.print(a[k][l]+"\t");
            }
            System.out.print("\n");
        }
           
   
    }
}

Hi Guys Sleeping !!!!

I have a New question !!!!! try to solve it !!!!

Chef is very fond of horses. He enjoys watching them race. As expected, he has a stable full of horses. He, along with his friends, goes to his stable during the weekends to watch a few of these horses race. Chef wants his friends to enjoy the race and so he wants the race to be close. This can happen only if the horses are comparable on their skill i.e. the difference in their skills is less.

There are N horses in the stable. The skill of the horse i is represented by an integer S[i]. The Chef needs to pick 2 horses for the race such that the difference in their skills is minimum. This way, he would be able to host a very interesting race. Your task is to help him do this and report the minimum difference that is possible between 2 horses in the race.

Input:

First line of the input file contains a single integer T, the number of test cases.
Every test case starts with a line containing the integer N.
The next line contains N space separated integers where the i-th integer is S[i].

Output:

For each test case, output a single line containing the minimum difference that is possible.

Constraints:

1 ≤ T ≤ 10
2 ≤ N ≤ 5000
1 ≤ S[i] ≤ 1000000000

Example:

Input:

1
5
4 9 1 32 13

Output:

3

Explanation: The minimum difference can be achieved if we pick horses with skills 1 and 4 for the race.


//Here is the Code cc to  Arun Kumar Gupta!!!!
import java.util.*;

public class MinDistance
{

public static void main (String [] args)
{
Scanner sc = new Scanner(System.in);
int cases = sc.nextInt();
double min =1000000000 , min_next = 1000000000 , temp = 0 ;
int array_size = 0;
int  finale[]  = new int[cases];
double  array[] ;
int tt =0;
int w  =0 ;

//System.out.println(cases);
if(cases <= 10)
{
for(int i = 0 ; i<cases ; ++i)
{

array_size = sc.nextInt();

 array = new double[array_size];
 
double diff = 1000000000;
if((array_size <= 5000) && (array_size >= 2))
{
for(int j = 0 ; j < array_size  ; ++j)
{
array[j] = (double)sc.nextInt();
}
Arrays.sort(array);
for(int j =0 ; j < array_size-1  ; ++j)
{
//System.out.println("hi");
if (array[j] <= 1000000000 &&  array[j] > 0  )
{
//System.out.println("::::::");
//System.out.println(min +":"+ min_next);
if(diff > (array[j+1] -array[j]))
diff = array[j+1] -array[j];
//System.out.println(diff);
}
}

tt = (int)(diff);
//w =0;
//System.out.println(tt);
finale[w] = tt;
tt =0;
diff = 0;
//System.out.println(finale[w]);
//System.out.println(w);
++w;

}

}
for(int j = 0 ; j < cases  ; ++j)
{
System.out.println(finale[j]);
}


}


}
} 

Invitation to connect on LinkedIn

From Arun Gupta Teaching Assistant at DA-IICT Satna Area, India I'd like to add you to my professional network on LinkedIn. - Arun Confirm that you know Arun You are receiving Invitation to Connect emails. Unsubscribe © 2012, LinkedIn Corporation. 2029 Stierlin Ct. Mountain View, CA 94043, USA