Interview Question
Country: India
Interview Type: In-Person
first : sorting will take O(nlogn) ...and secondly after sorting think about the worst case which will be O(N^2).
I think we can do it in O(N) time.
int min_sofar = -1;
int max_profit = -1;
for (i = 0; i < n; i++) {
min_sofar = min(min_sofar, v[i]);
max_profit = max(max_profit, v[i]-min_sofar);
// If max_profit changes we can note down v[i],t[i] to separate variables to print later
}
return max_profit;
If I am understanding the question correctly
The main point is find out the time t1 having average value as MAX(Sell Point) and t2 having average value as MIN(Buy Point).
who ever is not agreeing with my comment please let me know that where I am wrong. In the whole question Its no where written that the data is from one day. else it will be simple question finding the time of min and max value and publish it.
there is possibility that data is from few days and we have to find out at which time the market is trading at low (buy point) and at which time market is trading at high, (sell point) If I was interviewed with this question then I will have asked this question. but with my understanding of the question my answer is correct. else give the whole question.
This question has been answered a few days ago. After sorting you can find the maximum profit in O(n).
- Rayden January 17, 2012