Re: [algogeeks] Re: DE Shaw written test
Test
{ 30,40,15,35,10,20 } using the logic specified as
Find the min and max element in the array.
If the min comes before max, then return the dates- min to buy and max to
sell.
But if the min comes after max,
find the max element that comes after min i.e. maxRight
find the min element that comes before max i.e. minLeft
Now find the difference (max - minLeft)( maxRight - min)
return the dates for which the difference is higher.
It does not work. The assumption that either one of real max or real min
has to be part to compute max profit does not seem correct.
alternatively
after findiing a profit, if we find a min, save the previous computations
(imagine previous array is not part anymore and apply the same rule of
findling min and then maxProfit.
int minIndex = 0;
int maxProfit = 0;
int maxIndex = -1;
int finalMinIndex = -1;
int finalMaxIndex = -1;
for (int i=1; in;i++)
{
if (a[i] - a[minIndex] maxProfit) { maxProfilt = a[i] - a[minIndex];
maxIndex = i; continue;}
if (a[i] a[minIndex]) {
if (maxIndex ==-1) minIndex = i; //safely ignore previous min as for
upcoming max, the diff will be more now with this new min
else { finalMinIndex = minIndex; finalMaxIndex = maxIndex; maxIndex
= -1;}
}
}
if (maxIndex !=-1) {finalMinIndex = minIndex; finalMaxIndex = maxIndex;}
Best Regards
Ashish Goel
Think positive and find fuel in failure
+919985813081
+919966006652
On Sun, Aug 5, 2012 at 11:36 PM, Navin Kumar navin.nit...@gmail.com wrote:
This is a linear time constant space algorithm.
Assume the stocks prices are given in an array where index represents the
day no . For ex a[365] represents stock price on 365th day of year.
Find the min and max element in the array.
If the min comes before max, then return the dates- min to buy and max to
sell.
But if the min comes after max,
find the max element that comes after min i.e. maxRight
find the min element that comes before max i.e. minLeft
Now find the difference (max - minLeft)( maxRight - min)
return the dates for which the difference is higher.
Code:--
void FindDaytoBuySellStock(int stocks[], int N) // here N = 365
{
int minPos = findMinPos(stocks);
int maxPos = findMaxPos(stocks);
if(minPos maxPos ) { BuyDate = minPos,SellDate = maxPos; }
else{
minLeft = find min in array from 0 to maxPos-1
maxRight = find max in array from minPos+1 to N
int d1 = max - minLeft;
int d2 = maxRight - min;
if(d1 = d2 ) {BuyDate = minLeft,SellDate = max; }
else{ BuyDate = min ,SellDate = maxRight; }
}
}
--
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/-/dSJCOIuUuKUJ.
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] Re: DE Shaw written test
@ harsha : consider a case like this : 3 11 1 7 by your algo 1 is the
minimum stock price, and you will sell it for 7-1=6 whereas the max prize
is 11-3=8,
I have code like this :
double maxProfit = 0, minBuy = 1000;
int minBuyTime = -1, resultBuyTime = -1, resultSellTime = -1;
for (int i=0; iN; i++) {
//consider selling now
double saleProfit = arr[i] - minBuy;
if (saleProfit maxProfit)
{
maxProfit = saleProfit;
resultBuyTime = minBuyTime;
resultSellTime = arr[i];
}
//consider if there's a new minimum buy price
if (arr[i] minBuy)
{
minBuy = arr[i];
minBuyTime = i;
}
}
printf (Buy time: %lf, Sell Time: %lf, Profit: %lf, resultBuyTime,
resultSellTime, maxProfit);
I hope this would work, also could u elaborate on DeShaw's procedure, was
there a separate coding round
On Sunday, August 5, 2012 10:07:21 AM UTC+5:30, harsha 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/-/oFONPkTw7JgJ.
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] Re: DE Shaw written test
This is a linear time constant space algorithm.
Assume the stocks prices are given in an array where index represents the
day no . For ex a[365] represents stock price on 365th day of year.
Find the min and max element in the array.
If the min comes before max, then return the dates- min to buy and max to
sell.
But if the min comes after max,
find the max element that comes after min i.e. maxRight
find the min element that comes before max i.e. minLeft
Now find the difference (max - minLeft)( maxRight - min)
return the dates for which the difference is higher.
Code:--
void FindDaytoBuySellStock(int stocks[], int N) // here N = 365
{
int minPos = findMinPos(stocks);
int maxPos = findMaxPos(stocks);
if(minPos maxPos ) { BuyDate = minPos,SellDate = maxPos; }
else{
minLeft = find min in array from 0 to maxPos-1
maxRight = find max in array from minPos+1 to N
int d1 = max - minLeft;
int d2 = maxRight - min;
if(d1 = d2 ) {BuyDate = minLeft,SellDate = max; }
else{ BuyDate = min ,SellDate = maxRight; }
}
}
--
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/-/dSJCOIuUuKUJ.
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.
