## Amazon Interview Question for Software Engineer / Developers

• 0

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

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

The problem now is to find the subsequence with maximum sum!!

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

This is a great solution!!!

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

Great solution? Are you kidding?

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

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

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

``````maxProfit = 0
for i 0 to n
{
minHeap.insert(a[i])

if a[i] - minHeap.Minimum > maxProfit {
sell = a[i]
}
}
return sell - buy;``````

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

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

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

maxProfit = 0
for i 0 to n
{
minHeap.insert(a[i])

if a[i] - minHeap.Minimum > maxProfit {
maxProfit = a[i] - minHeap.Minimum;
sell = a[i]
}
}
return sell - buy;

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

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.

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

[*]'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).

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

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

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

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

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

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

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

Is'nt this same as finding max(A[j]-A[i]) with j>i . I think this can be done in O(n).

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

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

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

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.

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

To represent it correctly its Max(A[i+1]-Minof(A[i]-- i ranges from 1 to i). First we can calculate all the values Minof(A[i]--i ranges from 1 to i) . Then we can subtract calculated values from A[i+1] and find Max among them

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

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

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

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)

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

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.

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

I think stefan is right. Even I thought of same solution.

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

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

}

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

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

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

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)

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

try for..
10,5,36,2,12

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

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

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

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

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

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

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

longest increasing subsequence will not solve the problem.
consider arraay as 3 8 5 1 7 18 4
here lis is 3 5 7 18
so acc to u max profit is 18-3=15
but ans is 18-1=17

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.