## Amazon Interview Question for Software Engineer / Developers

Comment hidden because of low score. Click to expand.
1
of 1 vote

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:

``````A:     1 2 3 4 50 47 35 22 48 10 34 11
AMin:  1 2 3 4 10 10 10 10 10 10 11 11
Loss:  0 0 0 0 40 37 25 12 38 00 23 00``````

Linear solution in time

Comment hidden because of low score. Click to expand.
0
of 0 vote

Go 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.

Comment hidden because of low score. Click to expand.
0

1) when array is in decreasing order i.e A[i] > A[i+1]
2) when array is in increasing order i.e. A[i] <A[i+1]

Comment hidden because of low score. Click to expand.
0
of 0 vote

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;
}

Comment hidden because of low score. Click to expand.
0

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

Comment hidden because of low score. Click to expand.
0

@sachinsaner
I think this is what assumed in solution. In each decreasing interval you will buy at high price and sell it at low price.

If we can sell first then buy . I think we have to find increasing interval...

Comment hidden because of low score. Click to expand.
0
of 0 vote

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.

Comment hidden because of low score. Click to expand.
0

what if the diffrence is between the max of the first decresing order and minimum of the second one. we need to maintain a separte list of max and min and check if the min are occuring after the max.

Comment hidden because of low score. Click to expand.
0
of 0 vote

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.

Comment hidden because of low score. Click to expand.
0
of 0 vote

go through the list
for each value
if it is greater than current max, update current max,
if it is smaller than current max, find difference and update current max difference

Comment hidden because of low score. Click to expand.
0
of 0 vote

``````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;
}``````

Name:

Writing Code? Surround your code with {{{ and }}} to preserve whitespace.

### Books

is a comprehensive book on getting a job at a top tech company, while focuses on dev interviews and does this for PMs.

### Videos

CareerCup's interview videos give you a real-life look at technical interviews. In these unscripted videos, watch how other candidates handle tough questions and how the interviewer thinks about their performance.