Re: [algogeeks] DE Shaw written test
@ashgoel :- Thanx for pointing it out, my earlier approach doesn't work.
Please check if this works.
We can apply this:-
For every element, find the highest element to the right of it.
For e.g:
I/P:- 35 4015 35 10 20
Highest to Right:- 40 3535 20 20-
Now at every point, we will find the difference of both and keep track of
the buy and sell dates.
This can be done in linear time without any space.
void getDates( int price[] ) {
int maxSel l, maxBuy , maxGain= INT_MIN;
int Sell,Buy,curGain;
Sell = n;
for(int i=n-1;i=0;i--)
{
curGain = price[Sell] - price[i];
if(curGain maxGain){ // buying today gives more gain
that previous gain found, update the maxgain and buy,sell dates
maxGain = curGain;
maxBuy = i;// today
maxSell = Sell;
}
if( price[i]price[Sell] ) // here selldate is
updated
Sell = i ;
}
}
--
You received this message because you are subscribed to the Google Groups
Algorithm Geeks group.
To view this discussion on the web visit
https://groups.google.com/d/msg/algogeeks/-/BrQFNo1PKTIJ.
To post to this group, send email to algogeeks@googlegroups.com.
To unsubscribe from this group, send email to
algogeeks+unsubscr...@googlegroups.com.
For more options, visit this group at
http://groups.google.com/group/algogeeks?hl=en.
Re: [algogeeks] DE Shaw written test
This is maximum sub-array problem. Nice explaination is given in CLRS -
Introduction to algorithms Pg 68, ch-4 3rd edition
On Tue, Aug 7, 2012 at 11:00 AM, Navin Gupta navin.nit...@gmail.com wrote:
@ashgoel :- Thanx for pointing it out, my earlier approach doesn't work.
Please check if this works.
We can apply this:-
For every element, find the highest element to the right of it.
For e.g:
I/P:- 35 4015 35 10 20
Highest to Right:- 40 3535 20 20-
Now at every point, we will find the difference of both and keep track of
the buy and sell dates.
This can be done in linear time without any space.
void getDates( int price[] ) {
int maxSel l, maxBuy , maxGain= INT_MIN;
int Sell,Buy,curGain;
Sell = n;
for(int i=n-1;i=0;i--)
{
curGain = price[Sell] - price[i];
if(curGain maxGain){ // buying today gives more gain
that previous gain found, update the maxgain and buy,sell dates
maxGain = curGain;
maxBuy = i;// today
maxSell = Sell;
}
if( price[i]price[Sell] ) // here selldate is
updated
Sell = i ;
}
}
--
You received this message because you are subscribed to the Google Groups
Algorithm Geeks group.
To view this discussion on the web visit
https://groups.google.com/d/msg/algogeeks/-/BrQFNo1PKTIJ.
To post to this group, send email to algogeeks@googlegroups.com.
To unsubscribe from this group, send email to
algogeeks+unsubscr...@googlegroups.com.
For more options, visit this group at
http://groups.google.com/group/algogeeks?hl=en.
--
With Regards
Manish Patel
BTech Final year
Computer Science And Engineering
National Institute of Technology -Allahabad
--
You received this message because you are subscribed to the Google Groups
Algorithm Geeks group.
To post to this group, send email to algogeeks@googlegroups.com.
To unsubscribe from this group, send email to
algogeeks+unsubscr...@googlegroups.com.
For more options, visit this group at
http://groups.google.com/group/algogeeks?hl=en.
Re: [algogeeks] DE Shaw written test
The problem boils down to this:
http://www.geeksforgeeks.org/archives/6463
On Tue, Aug 7, 2012 at 1:59 PM, manish patel manispatel...@gmail.comwrote:
This is maximum sub-array problem. Nice explaination is given in CLRS -
Introduction to algorithms Pg 68, ch-4 3rd edition
On Tue, Aug 7, 2012 at 11:00 AM, Navin Gupta navin.nit...@gmail.comwrote:
@ashgoel :- Thanx for pointing it out, my earlier approach doesn't work.
Please check if this works.
We can apply this:-
For every element, find the highest element to the right of it.
For e.g:
I/P:- 35 4015 35 10 20
Highest to Right:- 40 3535 20 20-
Now at every point, we will find the difference of both and keep track
of the buy and sell dates.
This can be done in linear time without any space.
void getDates( int price[] ) {
int maxSel l, maxBuy , maxGain= INT_MIN;
int Sell,Buy,curGain;
Sell = n;
for(int i=n-1;i=0;i--)
{
curGain = price[Sell] - price[i];
if(curGain maxGain){ // buying today gives more gain
that previous gain found, update the maxgain and buy,sell dates
maxGain = curGain;
maxBuy = i;// today
maxSell = Sell;
}
if( price[i]price[Sell] ) // here selldate
is updated
Sell = i ;
}
}
--
You received this message because you are subscribed to the Google Groups
Algorithm Geeks group.
To view this discussion on the web visit
https://groups.google.com/d/msg/algogeeks/-/BrQFNo1PKTIJ.
To post to this group, send email to algogeeks@googlegroups.com.
To unsubscribe from this group, send email to
algogeeks+unsubscr...@googlegroups.com.
For more options, visit this group at
http://groups.google.com/group/algogeeks?hl=en.
--
With Regards
Manish Patel
BTech Final year
Computer Science And Engineering
National Institute of Technology -Allahabad
--
You received this message because you are subscribed to the Google Groups
Algorithm Geeks group.
To post to this group, send email to algogeeks@googlegroups.com.
To unsubscribe from this group, send email to
algogeeks+unsubscr...@googlegroups.com.
For more options, visit this group at
http://groups.google.com/group/algogeeks?hl=en.
--
You received this message because you are subscribed to the Google Groups
Algorithm Geeks group.
To post to this group, send email to algogeeks@googlegroups.com.
To unsubscribe from this group, send email to
algogeeks+unsubscr...@googlegroups.com.
For more options, visit this group at
http://groups.google.com/group/algogeeks?hl=en.
RE: [algogeeks] DE Shaw written test
The sequence of price is make more sense if buy price is less than next
value then you can buy even its not the min and next day you can sell all
and
Buy again when min price stock come.
Eg 6, 10, 5, 7, 2,7.
There are many case need to consider the above is the only one scenario.
Other like random order profits and loss so need to decide min n max for a
interval.
Here is no profit
9 8 7 6 5 4 3 2 1 :(.
Sent from my Windows Phone
--
From: Mukul Gupta
Sent: 08/05/2012 8:47 PM
To: algogeeks@googlegroups.com
Subject: Re: [algogeeks] DE Shaw written test
Thanks for pointing out the mistake.Though my code will correctly calculate
the max_profit but I must keep track of the buying_day.I have made some
modification in my code.Hope it works fine now.
int min = a[0]; // initialized to first element
int max_profit = 0; //when you buy and sell on same day
int buying_day = a[0];
for ( int i = 1; i n; i++ ){
if ( max_profit (a[i] - min ) ){
max_profit = a[i] - min;
buying_day = min;
}
if ( a[i] min )
min = a[i];
}
Finally. I'll have buying_day and max_profit, so if you need to find the
selling day you can easily calculate :
Selling day = buying_day+max_profit;
Correct me if I'm wrong.
On Sun, Aug 5, 2012 at 5:43 PM, Arun Kindra arunkin...@gmail.com wrote:
@harsha : yes, the problem is if u r finding only min and max value, it
might happen that u sell the stock before buying. Ex- int a [ ] = { 5, 10,
4, 6, 7 }; the min value is 4 and max is 10 and 10 comes before 4, means u
sell the stock before buying.
and i think the sol given by mukul does the same mistake.we need to keep
track this case also whether the day(array index) i m buying is not more
than the day(array index) we are selling the stock.
*correct me if m wrong*.
--
You received this message because you are subscribed to the Google Groups
Algorithm Geeks group.
To post to this group, send email to algogeeks@googlegroups.com.
To unsubscribe from this group, send email to
algogeeks+unsubscr...@googlegroups.com.
For more options, visit this group at
http://groups.google.com/group/algogeeks?hl=en.
--
You received this message because you are subscribed to the Google Groups
Algorithm Geeks group.
To post to this group, send email to algogeeks@googlegroups.com.
To unsubscribe from this group, send email to
algogeeks+unsubscr...@googlegroups.com.
For more options, visit this group at
http://groups.google.com/group/algogeeks?hl=en.
--
You received this message because you are subscribed to the Google Groups
Algorithm Geeks group.
To post to this group, send email to algogeeks@googlegroups.com.
To unsubscribe from this group, send email to
algogeeks+unsubscr...@googlegroups.com.
For more options, visit this group at
http://groups.google.com/group/algogeeks?hl=en.
Re: [algogeeks] DE Shaw written test
As i understand the question says, one time buy and one time sell, buy
preceeds sell...
if multiple such transactions allowed, we may need DP
Best Regards
Ashish Goel
Think positive and find fuel in failure
+919985813081
+919966006652
On Mon, Aug 6, 2012 at 7:16 AM, umesh kewat umesh1...@gmail.com wrote:
The sequence of price is make more sense if buy price is less than next
value then you can buy even its not the min and next day you can sell all
and
Buy again when min price stock come.
Eg 6, 10, 5, 7, 2,7.
There are many case need to consider the above is the only one scenario.
Other like random order profits and loss so need to decide min n max for a
interval.
Here is no profit
9 8 7 6 5 4 3 2 1 :(.
Sent from my Windows Phone
--
From: Mukul Gupta
Sent: 08/05/2012 8:47 PM
To: algogeeks@googlegroups.com
Subject: Re: [algogeeks] DE Shaw written test
Thanks for pointing out the mistake.Though my code will correctly
calculate the max_profit but I must keep track of the buying_day.I have
made some modification in my code.Hope it works fine now.
int min = a[0]; // initialized to first element
int max_profit = 0; //when you buy and sell on same day
int buying_day = a[0];
for ( int i = 1; i n; i++ ){
if ( max_profit (a[i] - min ) ){
max_profit = a[i] - min;
buying_day = min;
}
if ( a[i] min )
min = a[i];
}
Finally. I'll have buying_day and max_profit, so if you need to find the
selling day you can easily calculate :
Selling day = buying_day+max_profit;
Correct me if I'm wrong.
On Sun, Aug 5, 2012 at 5:43 PM, Arun Kindra arunkin...@gmail.com wrote:
@harsha : yes, the problem is if u r finding only min and max value, it
might happen that u sell the stock before buying. Ex- int a [ ] = { 5, 10,
4, 6, 7 }; the min value is 4 and max is 10 and 10 comes before 4, means u
sell the stock before buying.
and i think the sol given by mukul does the same mistake.we need to keep
track this case also whether the day(array index) i m buying is not more
than the day(array index) we are selling the stock.
*correct me if m wrong*.
--
You received this message because you are subscribed to the Google Groups
Algorithm Geeks group.
To post to this group, send email to algogeeks@googlegroups.com.
To unsubscribe from this group, send email to
algogeeks+unsubscr...@googlegroups.com.
For more options, visit this group at
http://groups.google.com/group/algogeeks?hl=en.
--
You received this message because you are subscribed to the Google Groups
Algorithm Geeks group.
To post to this group, send email to algogeeks@googlegroups.com.
To unsubscribe from this group, send email to
algogeeks+unsubscr...@googlegroups.com.
For more options, visit this group at
http://groups.google.com/group/algogeeks?hl=en.
--
You received this message because you are subscribed to the Google Groups
Algorithm Geeks group.
To post to this group, send email to algogeeks@googlegroups.com.
To unsubscribe from this group, send email to
algogeeks+unsubscr...@googlegroups.com.
For more options, visit this group at
http://groups.google.com/group/algogeeks?hl=en.
--
You received this message because you are subscribed to the Google Groups
Algorithm Geeks group.
To post to this group, send email to algogeeks@googlegroups.com.
To unsubscribe from this group, send email to
algogeeks+unsubscr...@googlegroups.com.
For more options, visit this group at
http://groups.google.com/group/algogeeks?hl=en.
[algogeeks] DE Shaw written test
there is a stock company whose stock prices are known to u for next 365 days. u have to write the code on which day u should buy and sell the stock. U cannot sell a stock until you haven't bought any stock. my approach was to buy the stock when the stock prices are the lowest and sell them when they are the highest. But i think am missing something because this question was for a considerable amount of marks but the solution is too obvious! any thoughts ? -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To view this discussion on the web visit https://groups.google.com/d/msg/algogeeks/-/Qw0NRAP_TtwJ. To post to this group, send email to algogeeks@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
Re: [algogeeks] DE Shaw written test
This can be done in O(n) time complexity and O(1) space complexity using
dynamic programming.Consider a situation in which I have been given an
array of stock values for N days (in your case N=365) which looks like:
int a [ ] = { 5, 10, 4, 6, 7 };
Now,use two variables min (which will keep track of minimum element found
upto some index i) and max_profit (keeps track of maximum profit that can
be obtained ).
int min = a[0]; // initialized to first element
int max_profit = 0; //when you buy and sell on same day
for ( int i = 1; i n; i++ ){
if ( max_profit (a[i] - min ) )
max_profit = a[i] - min;
if ( a[i] min )
min = a[i];
}
Finally. I'll have min and max_profit, so if you need to find the buying
and selling day you can easily calculate using min and max_profit.
Buying day = min;
Selling day = min+max_profit;
I hope it's clear.Even if something is wrong or difficult to understand you
can check this link :
http://stackoverflow.com/questions/7086464/interview-question-maximum-single-sell-profit
Thanks.
On Sun, Aug 5, 2012 at 10:07 AM, harsha harshacoo...@gmail.com wrote:
there is a stock company whose stock prices are known to u for next 365
days. u have to write the code on which day u should buy and sell the
stock. U cannot sell a stock until you haven't bought any stock.
my approach was to buy the stock when the stock prices are the lowest and
sell them when they are the highest. But i think am missing something
because this question was for a considerable amount of marks but the
solution is too obvious! any thoughts ?
--
You received this message because you are subscribed to the Google Groups
Algorithm Geeks group.
To view this discussion on the web visit
https://groups.google.com/d/msg/algogeeks/-/Qw0NRAP_TtwJ.
To post to this group, send email to algogeeks@googlegroups.com.
To unsubscribe from this group, send email to
algogeeks+unsubscr...@googlegroups.com.
For more options, visit this group at
http://groups.google.com/group/algogeeks?hl=en.
--
You received this message because you are subscribed to the Google Groups
Algorithm Geeks group.
To post to this group, send email to algogeeks@googlegroups.com.
To unsubscribe from this group, send email to
algogeeks+unsubscr...@googlegroups.com.
For more options, visit this group at
http://groups.google.com/group/algogeeks?hl=en.
Re: [algogeeks] DE Shaw written test
@harsha : yes, the problem is if u r finding only min and max value, it
might happen that u sell the stock before buying. Ex- int a [ ] = { 5, 10,
4, 6, 7 }; the min value is 4 and max is 10 and 10 comes before 4, means u
sell the stock before buying.
and i think the sol given by mukul does the same mistake.we need to keep
track this case also whether the day(array index) i m buying is not more
than the day(array index) we are selling the stock.
*correct me if m wrong*.
--
You received this message because you are subscribed to the Google Groups
Algorithm Geeks group.
To post to this group, send email to algogeeks@googlegroups.com.
To unsubscribe from this group, send email to
algogeeks+unsubscr...@googlegroups.com.
For more options, visit this group at
http://groups.google.com/group/algogeeks?hl=en.
Re: [algogeeks] DE Shaw written test
Thanks for pointing out the mistake.Though my code will correctly calculate
the max_profit but I must keep track of the buying_day.I have made some
modification in my code.Hope it works fine now.
int min = a[0]; // initialized to first element
int max_profit = 0; //when you buy and sell on same day
int buying_day = a[0];
for ( int i = 1; i n; i++ ){
if ( max_profit (a[i] - min ) ){
max_profit = a[i] - min;
buying_day = min;
}
if ( a[i] min )
min = a[i];
}
Finally. I'll have buying_day and max_profit, so if you need to find the
selling day you can easily calculate :
Selling day = buying_day+max_profit;
Correct me if I'm wrong.
On Sun, Aug 5, 2012 at 5:43 PM, Arun Kindra arunkin...@gmail.com wrote:
@harsha : yes, the problem is if u r finding only min and max value, it
might happen that u sell the stock before buying. Ex- int a [ ] = { 5, 10,
4, 6, 7 }; the min value is 4 and max is 10 and 10 comes before 4, means u
sell the stock before buying.
and i think the sol given by mukul does the same mistake.we need to keep
track this case also whether the day(array index) i m buying is not more
than the day(array index) we are selling the stock.
*correct me if m wrong*.
--
You received this message because you are subscribed to the Google Groups
Algorithm Geeks group.
To post to this group, send email to algogeeks@googlegroups.com.
To unsubscribe from this group, send email to
algogeeks+unsubscr...@googlegroups.com.
For more options, visit this group at
http://groups.google.com/group/algogeeks?hl=en.
--
You received this message because you are subscribed to the Google Groups
Algorithm Geeks group.
To post to this group, send email to algogeeks@googlegroups.com.
To unsubscribe from this group, send email to
algogeeks+unsubscr...@googlegroups.com.
For more options, visit this group at
http://groups.google.com/group/algogeeks?hl=en.
