Amazon Interview Question: Given the daily stock prices ... | Glassdoor.co.in

## Interview Question

Senior Software Engineer Interview Bengaluru

# Given the daily stock prices of a share during last

30 days, write a program to find out best buying and selling dates for maximum gain. The program should run with O(n) complexity.

0

find the difference of price change on everyday and store it in an array. i.e., something like: [2,0,-3,6,-1]
Now find the sub array which has the more sum. http://en.wikipedia.org/wiki/Maximum_subarray_problem

devsathish on 05-May-2012
1

@devsathish, I do not think so!

Consider : {1,-4,5,6,-3,9,1,7}

Maximum_subarray_problem would select {5,6,-3,9,1,7} where as the logical index for buying should be 1 and 5 respectively.

Ashish on 14-May-2012
2

Much much simpler in O(n)
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 maxPrices[sellPos]) {
sellPos --;
break;
}
}

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

Stefan on 19-May-2012
0

sdgdfsh

saf on 18-Apr-2016