## Amazon Interview Question

Software Engineer / DevelopersGo through the array in order, keeping track of the lowest stock price

and the best deal you've seen so far. Whenever the current stock price minus the

current lowest stock price is better than the current best deal, update the best deal

to this new value.

This is not my solution. A previous Question asked in Bloomberg section some what resembles the Question......

Maximum loss when we will buy at highest price and sell it at lowest price.

So Find decreasing intervals..If you couldn't find any such interval then maximum loss is zero....

int MAX_LOSS( int A[]){

int i=0;

int max_loss = 0;

for( i =0 to n){

int local_maxima = A[i];

while( A[i] > A[i+1]){

local_minima = A[i+1];

++i;

}

temp_max_loss = local_maxima - local_minima;

if(max_loss < temp_max_loss){

max_loss = temp_max_loss;

}

}

return max_loss;

}

In this case u will have to consider the time frame also . You can sell the stock only after you have bought it first . So the date highest price of stock should come before the date of selling stock at lowest price

Pretty simple....Imagine it to be a graph chart...Maintain a curr_max which stores the value of the spike above x-axis. A decreasing interval is present until a value higher than this occurs. FInd the min in that interval, the diff of which with curr_max will be our curr_max_loss. Do this for every decreasing interval updating curr_max_loss if necessary.

Did a similar problem with finding the HighestGainPossible.

```
static void FindHighestGain(int[] dailyStockValues)
{
int low, hi, possibleLow;
low = hi = possibleLow = dailyStockValues[0];
int lowIndex = 0, hiIndex = 0, possibleLowIndex = 0;
Console.Write("Stock Values are: ");
for (int i = 0; i < dailyStockValues.Length; i++)
{
Console.Write(dailyStockValues[i] + " ");
// Update the hi value as we go forward.
if (dailyStockValues[i] > hi)
{
hi = dailyStockValues[i];
hiIndex = i;
}
// Track the possible low value.
if (dailyStockValues[i] < possibleLow)
{
possibleLow = dailyStockValues[i];
possibleLowIndex = i;
}
// Compare the possible max value with the current max.
if ((dailyStockValues[i] - possibleLow) > (hi - low))
{
// Set the new low
low = possibleLow;
lowIndex = possibleLowIndex;
// Set the new high
hi = dailyStockValues[i];
hiIndex = i;
}
}
Console.WriteLine();
Console.WriteLine("The maximum gain possible is: " + (hi - low));
Console.WriteLine("LowIndex={0} HighIndex={1}", lowIndex, hiIndex);
}
```

Finding maximum loss is doing the above going backwards in the array.

```
int[] a = {1,2,3,4,5,6,7,7};
int maxdiff=a[0]-a[1];
int local_maximum= a[0];
int diff =0;
for(int i=0; i < a.length -1 ; i++){
for(int j=a[i+1];j< a.length;j++){
if(a[j]>local_maximum){
local_maximum = a[j];
i=j;
}else{
diff = a[i] - a[j];
if(diff > maxdiff){
maxdiff = diff;
}
}
}
}
return maxdiff;
}
```

Let A be the input array.

Maintain another array AMin such that AMin[i] = min(A[i] ... A[n]), which can be done in linear time working backwards on A.

Now max(A[i] - AMin[i]) will be the maximum loss.

Ex:

Linear solution in time

- Mahesh October 18, 2010