Amazon Interview Question
Applications DevelopersCountry: United States
Good one om, thumbs up!. Yeah, its a solution with O(n) time complexity. I too had thought on similar lines and wrote a small program to check the correctness of the idea and It works.
public static void maxBenefit(int[] values) throws Exception{
if (values.length < 1) throw new Exception("Invalid input");
int cMin = values[0], gMin = values[0], gMax = values[0], gdiff = 0;
for (int i=1; i < values.length; i++) {
if (values[i] < cMin) {
cMin = values[i];
} else if ((values[i] - cMin) > gdiff) {
gMin = cMin;
gMax = values[i];
gdiff = values[i] - cMin;
}
}
System.out.println("Max benefit of $" + gdiff + " happens by buying at $" + gMin + " and selling at $" + gMax);
}
However, there can be many pairs with optimal (maximum) difference, and the above algorithm returns the first or the last of such pairs based on whether we use '>' or '>=' respectively in the condition below.
} else if ((values[i] - cMin) > gdiff) {
You are the man :) ... awesome :) ... It looks simple but very difficult to get the spark ... :)
Why bother with DP, when there is a very simple solution in O(n). The max benefit is the case where you buy at the lowest price and sell at the highest, with the condition that the buy has to be before sell.
public static int getMaxBenefit(int []S) {
int maxBenefit = 0;
int minPrice = Integer.MAX_VALUE;
for (int i = 0; i < S.length; i++) {
maxBenefit = Math.max(maxBenefit, S[i] - minPrice);
minPrice = Math.min(S[i], minPrice);
}
return maxBenefit;
}
@Apostle The solution explained and the code written has nothing to do with DP, but it's a working solution, I give you that. The problem is not asking the "best pairs" and I see that you've added gMin, gMax, etc.
I am just pointing out that this solution does not require DP and it can be implemented in a simple way with less number of codes, to me that's valuable, and I am sure it is for the interviewer too.
@oOZz
I agree that the solution does not require a true DP implementation where the solutions to subproblems are constructed using solutions to sub-subproblems and by using tables for memoization.. etc etc..
This looks more like a max subsequence sum problem, where the solution is obtained by storing values of subproblems in a single variable instead of tables.
Overlapping subproblems and optimal substructure may not be quite apparent in this problem, though, the principles of dynamic programming as to building solution in a bottom-up way and checking 'whether or not the current value contributes to the solution' are still valid here and that is what @om seems to mean by DP
Nonetheless, I see that our implementations conform to @om's idea with mine being a bit more elaborate and instructive and yours short and sweet.
A related problem that is more difficult and requires true DP style approach can be found at: hackerrank.com/challenges/stockmax
@oOZz
Hey, but your solution is O(N^2), while the solution given by om is only O(N). However I totally agree with you that calling om's solution as "DP" is an unfortunate misuse of the language. lol.
There is a very simple solution in O(n). The max benefit is the case where you buy at the lowest price and sell at the highest, with the condition that the buy has to be before sell.
public static int getMaxBenefit(int []S) {
int maxBenefit = 0;
int minPrice = Integer.MAX_VALUE;
for (int i = 0; i < S.length; i++) {
maxBenefit = Math.max(maxBenefit, S[i] - minPrice);
minPrice = Math.min(S[i], minPrice);
}
return maxBenefit;
}
construct two arrays as follow:
F(i)= min(0<x<i)
G(i) = max(i<x<10)
where i [0,10)
so u will get for your test case
F = 5 1 1 1 1 1 1 1 1 1
G = 9 9 9 9 9 9 9 9 9 9
take the difference as follow
diff(i) = G(i+1) - H(i)
and take the max of it
answer = 9-1 = 8
your examples is simple
a good test case should be 8 9 11 12 7 6 4 9 1 4
F = 8 8 8 8 7 6 4 4 1 1
G = 12 12 12 12 9 9 9 9 4 4
diffence
: 4 4 4 1 2 3 5 0 3
so the answer is 5
which you can verify
this is O(n +n +n) = O (n)..wat else you want
F(k) = min(F(k-1),input_array(k))
G(k) = max(G(k+1),input_array(k))
so both of these are n comparisons
so O(n)
and subtraction and max is also O(n)
so total O(n)
Hi,
I think, this will produce incorrect result for array {3, 2, 1}. You will have F = {3, 2, 1}, G = {3, 2, 1}, won't you? And the wise-difference will be 0. But the answer seems to be -1.
By the way, your algorithm is incorrect only for strictly decreasing arrays.
yes i agree @golodnov thanx for point it out
the difference shouldn't be elementwise it
should be
diff(i) = G(i+1) - H(i) because one will sell only aftr he has bought
mn[0]=1e9;
mx[11]=maxx=0;
for(int i=1;i<=10;i++) cin>>arr[i];
for(int i=1;i<=10;i++) mn[i]=min(mn[i-1], arr[i]);
for(int i=10;i>=1;i--) mx[i]=max(mx[i+1], arr[i]);
for(int i=1;i<=10;i++) maxx=max(maxx, mx[i] - mn[i]);
cout<<maxx<<endl;
this is the code, is their any better approach?
This should work in O(n).
#include <stdlib.h>
#include <stdio.h>
int * bestDates(int *prices, int length);
int main(){
int dateArray[] = {-1, 1, 4, 6, 7, 8, 4, 3, 7, 9, 1, 2, 0, 12};
int *returnDates = bestDates(dateArray, 15);
if(!returnDates){
printf("Error\n");
return 0;
}else{
printf("Best Dates:\n");
printf("Buy: %d\n", returnDates[0]);
printf("Sell: %d\n", returnDates[1]);
}
return 0;
}
int * bestDates(int *prices, int length){
if(prices == NULL || length < 2){
return NULL; //error
}
int bestBuyDate = 0; // intialize with first day
int bestSellDate = 1; // intialize with second day
int smallestDate = (prices[0] <= prices[1])?0:1; // initialize with smaller of both days
for(int i = 2; i < length; ++i) {
if( (prices[i] - prices[smallestDate]) > (prices[bestSellDate] - prices[bestBuyDate]) ){
//Better dates found
bestSellDate = i;
bestBuyDate = smallestDate; //smallest was best with this sell date
}
if( prices[i] < prices[smallestDate] ){
//New smallest item found
smallestDate = i;
}
}
int * bestReturn = malloc(sizeof(int) * 2);
if(bestReturn == NULL) return NULL; //error
bestReturn[0] = prices[bestBuyDate];
bestReturn[1] = prices[bestSellDate];
return bestReturn;
}
Build a max heap and min heap data structure which only takes O(n) time (use heapify method). Once done look out the min element and maximum elements in both the heaps . the difference between these value is the answer
Without using Extra memory and in O(n) it's possible
Ex : 5 3 4 6 2 8 4 1 7 9
Calculate the difference with minimum, If the difference becomes -Ve, Change the minimum to index where you are getting -Ve calue.
-4 1 3 -1 6 2 -1 6 7
public static void getMaxProfit(int[] data)
{
int len = data.length;
int profit = Integer.MIN_VALUE;
int s = 0; // sell index
int b = 0; // buy index
for(int i = 1; i < len; i++)
{
if (data[b] > data[i]) // minimizing the buy value
{
b = i;
}
if (data[s] < data[i]) // maximizing the sell value
{
s = i;
}
// updating the profit if sell index if greater than buy index
if (s > b && profit < (data[s] - data[b]))
{
profit = data[s] - data[b];
}
}
System.out.println("Profit :" + profit);
}
Time complexity : O(1)
Straight forward and easy to understand.
Please point out any issue if you get.
They are essentially interested in a case where the difference between the two value is maximum. These values are all positive. So, the difference between the maximum and the minimum is the answer! All we need to do is to find these max and min. They can be found in O(n). Please correct me if I didn't get the question right.
Algorithm:
- om July 24, 2013Dynamic Programing : o(n)
1.for each kth element keep the best pair values and minimum value
2.for k+1 element compare with (k+1, minmum) vs (best pair) and accordingly update the minimum and best pair values