## Amazon Interview Question

Software Engineer / Developers//Solution in o(n) time:

void stock_profit(int a[])

{

int i,j;

int time1, time2, sum, max_sum;

j=sum=max_sum=0;

for(i=1; i<SIZE; i++)

{

if(a[j] >= a[i])

{

sum = 0;

j=i;

}

else

{

if((a[i] - a[j]) > sum)

{

sum = a[i] - a[j];

if(max_sum < sum)

{

max_sum = sum;

time1 = j;

time2 = i;

}

}

}

}

printf("Maximum Profit in between interval %d and %d", time1, time2);

}

```
maxProfit = 0
for i 0 to n
{
minHeap.insert(a[i])
if a[i] - minHeap.Minimum > maxProfit {
buy = minHeap.Minimum
sell = a[i]
}
}
return sell - buy;
```

Your minheap is just keeping the running global minimum, a heap isn't necessary. Other than that (& some cleanup) I think this works.

I think a divide-and-conquer approach works here like merge-sort. We recursively divide the range in half:

1) divide steps:

[i] 'buy' and 'sell' lies in 1st half

[ii]'buy' and 'sell' lies in 2nd half

2) merge: 'buy' lies in 1st half and and 'sell' lies in 2nd half -> this takes O(1) time because 'buy' price is the leftmost one in 1st half, and 'sell' price is the rightmost. However, to merge two sorted list, it'll be O(n).

So time complexity is O(nlog n). Plz comment if seems this doesn't work for every input.

[*]'sell' price is the rightmost (replaced by) 'sell' price is the rightmost in the 2nd half as we like to maximize the difference.

Also to keep the original index, we would need a structure to keep track of the index in given sequence. An alternative approach may work without sorting the list (to keep the given sequence unchanged). At that case, merge would be bit different: scan 1st half to find the minimum price, and 2nd half to find the maximum price (as before recursively).

Oh, a basic mistake I did in my previous explanation is that you need to do such recursion to get profit maximized:

max_profit = Max{ find_profit(1st half), find_profit(2nd half), merge(1st half, 2nd half)}.

I guess an O(n) solution may be achievable if we keep the sequence un-sorted, and keep 2 variables to keep min_val and max_val of each sub-lists (as it's recursively during merge we need comparing constant values).

An example to support my approach:

```
3 8 5 1 7 18 16 4
sublist[3,8] => min=3,max=8,profit=5
sublist[5,1] => min=1,max=5,profit=-4
merge [3,8,5,1] => min=1,max=8, profit = MAX {5,-4, (5-3)} = 5
sublist[7,18] => min=7,max=18,profit=11
sublist[16,4] => min=4,max=16,profit=-12
merge [7,18,16,4] => min=4,max=18, profit = MAX {11,-12, (16-7)} = 11
final merge[3,8,5,1,7,18,16,4] => profit = MAX {5, 11, (18-1)} = 17
So it is an O(n) solution, lowest bound for this problem. Plz comment on any catches in this method.
```

@buried

What is we use dynamic programming using recursion like this:

1. divide given array in left and right subarray

2. buy defined as - minimum of left. sell defined as - maximum of right.

3. find minimum of left and maximum of right. Subtract and get the profit and corresponding buy/sell values stored.

4. Further divide both left and right subarrays and repeat step 3 in each of them. If the profit derived is less than current maximum profit in any of the new sub arrays we don't consider it further.

Example:

3 8 5 1 7 18 4

First Recursion:

Left - 3 8 5

Right - 1 7 18 4

P1 = max (Right) - min (Left) = 18 - 3 = 15.

Second Recursion:

LeftLeft - 3

LeftRight - 8 5

P2 = 8 - 3 = 5 (less than P1 don't consider this further)

RightLeft - 1 7

RightRight - 18 4

P3 = 18 - 1 = 17 (greater than P1, we will do more recursion but won't get the max).

Let me know.

could u give us more insight about this?? can u post a link on how it can be achieved in O(n) time?

Take a variable min and ans.ans stores the answer that has been obtained so far and min stores the minimum number encountered so far. start a loop from arr[0] - arr[n], with ans=0 and min = arr[0] as initial vaulues.

here is the code for this:

```
int func(int arr,int n){
if(!n) return 0;
int ans=0,min=ans[0];
for(int i=1;i<n;i++){
if(arr[i]-min > ans) ans = arr[i] - min;
if(arr[i] < min) min = arr[i];
}
return ans;
}
```

Kindly let me know if you find some mistake in the above approach.

int stock[] = {3,8,5,1,7,18,4};

int curMax = 18;

int curMin = stock[0];

int curMaxDiff = curMax-curMin;

for (int i = 0; i<7;i++) {

if (stock[i] < curMin) {

curMin = stock[i];

} else if ((stock[i] - curMin) > curMaxDiff) {

curMaxDiff = stock[i] - curMin;

}

}

std::cout << curMaxDiff <<std::endl;

}

public class Puzzle {

public static void main(String[] args){

int[] a = {3,8,5,1,7,18,4};

int max = 0;

int diff = 0;

for(int i=0; i<a.length-1; i++){

for(int j=i+1; j<a.length; j++){

diff = a[j] - a[i];

max = max > diff ? max : diff;

}

}

System.out.println(max);

}

}

Complexity = O(n * (n-1)) = O(n square)

Here is a solution which takes O(n) in time and O(n) in space.

Go through the array P=(p1,p2,p3,...pn), in reverse and build another array M (max), which has the maximum so far. M=(m1,m2,,3...mn), where mk is the maximum from position k to the end of the array (i.e. mn is pn, m(n-1) is the max between pn and p(n-1)...m3 is the max from p3 to pn. Recursively mk=max(mk+1,pk), and thus traversing the array P backwards constructs M in a single traversal O(n).

Now, go through the array P again, and for each value pk, compute profit=mk-pk. Find the maximum profit. Done.

```
class Deal
{
public int startID, endID, startValue, endValue, deal;
public Deal(int startID, int endID, int startValue, int endValue, int deal)
{
this.startID = startID;
this.endID = endID;
this.startValue = startValue;
this.endValue = endValue;
this.deal = deal;
}
}
public class Test {
public static void main(String []args)
{
int arr[] = new int[] {3,8,5,1,7,18,4};
bestDeal(arr);
}
public static void bestDeal(int arr[])
{
Deal res[] = new Deal[arr.length];
int min = Integer.MAX_VALUE, minID = 0, deal = 0;
for(int i = 0; i < arr.length; i++)
{
if(arr[i] >= 0 && arr[i] <= min)
{
min = arr[i];
minID = i;
}
res[deal++] = new Deal(minID, i, min, arr[i], arr[i] - min);
}
for(Deal x : res)
System.out.println(x.startID + " " + x.startValue + " " + x.endID + " " + x.endValue + " " + x.deal);
}
```

}

```
int MaxStockGain(int arr[], int size)
> {
> if(size <= 0)
> return 0;
>
> int curMin = arr[0];
> int MaxGain = 0;
>
> for(int i = 1; i < size; ++i)
> {
> if (arr[i] < curMin)
> {
> curMin = arr[i];
>
> }
>
>
> int currGain = arr[i] - curMin;
> if(currGain > MaxGain)
> {
> MaxGain = currGain;
> }
> }
>
> return MaxGain;
```

here is what I thought... Traverse whole array and find minimum value...

After min value is found then traverse again and find the max value starting from the index where the min value was found. This will give you min value to buy and maxvalue to sell for particular stock.

Time Complexity O(n)

Space complexity O(1)

```
Take 2 pointers, point first at the start and second to the last of the array of price interval.
Move both the pointers till they collide.
-move first to forward direction to find the least price & store its position.
-move second to backward direction to find highest price & store its position.
Now the profit is highest-lowest
```

Your's solution is wrong. what about if both least and highest price encounter while traversing first pointer.

The solution is correct

1. finding the min and max in the array doesnt guarentee that they are in order in terms of time instance .

eg consider time instances :

t1 t2 t3 t4 t5 t6 t7 t8

8 7 3 4 5 6 1 2

max_element is 8 ; min_elemnt is 1; this doesn't give the profit since you cannot buy shares in the future and sell it in the past :D . Therefore the min_element must occur first .

soln 1:

Move the pointers at both ends until they collide actually solves the problem.

Soln 2 :

Find the longest increasing subsequences ; Subtract the lower index value from higher

What abt creating a profit[i] = ar[i+1]-ar[i]..

- Anonymous July 08, 2010The problem now is to find the subsequence with maximum sum!!