Google Interview Question for Software Engineer / Developers


Country: United States
Interview Type: In-Person




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

//O(kn) O(k) space
int maxprofile(vector<int> &prices, int k){
    if(prices.size()<2 || k<1) return 0;
    int global[k+1];
    int local[k+1];
    memset(global, 0x00, sizeof(global));
    memset(local, 0x00, sizeof(local));
    for(int i=1; i<prices.size();i++){
        int diff = prices[i] - prices[i-1];
        for(int j=k; j>0; j--) {
            local[j] = max(global[j-1]+max(diff, 0),local[j]+diff);
            global[j] = max(local[j], global[j]);
        }
    }
    return global[k];
}

- simon.zhangsm December 19, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

yes, this is correct.
Note:: k here is # of buy-wait-sell transaction, while in other interpretations k is total # of buy and sell operations

- 0xF4 December 21, 2014 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

I tested it against my brute force solution (recursive generating all possible ways). it works flawlessly. Still trying to understand how does this work.

voted +1.

- MIG January 09, 2015 | Flag
Comment hidden because of low score. Click to expand.
1
of 1 vote

> Still trying to understand how does this work
It's actually very easy. For simplicity of explanation let's assume that local and global are not arrays but matrices of N*k.
global[i][j] = is a max profit which we can get in first i days with at most j buy+wait+sell transactions.
local[i][j] = is a max profit which we can get in first i days with at most j transactions where we sold
the stock on *last* day where prices were growing.
global[n-1][k] gives the answer.

local[i][j] can be computed as a maximum of profit buy exploring two possible options - we sold the stock on the last diff>=0 day or we don't.

global just acculates the maximum found so far

Those relationships are encoded in C++ as follows:

local[i][j] = max(global[i-1][j-1]+max(diff, 0),local[i-1][j]+diff);
global[i][j] = max(local[i-1][j], global[i-1][j]);

Now, since we're always refering to the previous column [i-1] - we don't need to store whole matrices - and can only track last column, so all that results
into nice O(N*k) time O(k) space algorithm.

This is not the only DP solution. Please find another O(N*k) time and O(k) space algorithm below posted by me - it gives exactly the same result
but it is based on a different recurrent relationships. You will see that those relationship model the same process, but in a different (more generic) representation. You might find them easier to understand (at least I tried to design them with this goal)

- 0xF4 January 09, 2015 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

@ 0xF4 : Thanks for explanation.

- MIG January 09, 2015 | Flag
Comment hidden because of low score. Click to expand.
4
of 4 vote

O(kN) time, O(k) space.

k - is # of total transactions (buy and sell count as separate operations)

int maximizeProfit(const vector<int> &v, int k)
{
	vector<int> s0(k+1), s1(k+1);
	s1[0] = INT_MIN;
	for (int j = 1; j <= k; j++) {
		s1[j] = -v[0];
	}

	for (int i = 1; i < v.size(); i++) {
		for (int j = k; j>=1; j--) {
			s1[j] = max(s1[j], s0[j-1]-v[i]);
			s0[j] = max(s0[j], s1[j-1]+v[i]);
		}
	}
	return s0[k];
}

- 0xF4 December 18, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
1
of 1 vote

Here's detailed explanation how my algorithm works.

Note - in this interpretation k - is number of transactions where sell counts as a separate transaction from buy.
The k is always even here.
This DP solution is based on the following recurrent relationships:
s0[i][j] - max possible ballance on our cash account on ith day when at most j transactions were made and we don't have a stock
s1[i][j] - max possible ballance on our cash account on ith day when at most j transactions were made and we do have a stock

We need to maximize the cash on our account with exit condition: at most k transactions and we don't have a stock.
So our answer is s0[n][k]

We start with the condition where we have 0 transactions - 0$ ballance and we don't have a stock:
s0[0][0] = 0$
The initial condition where we have a stock is impossible - making it unfavorable by setting negatively-infinite ballance:
s1[0][0] = -INFINITY$

Now we can use the following recurrent relationships:
1) If have stock at the end if ith day - this means we either just bought it (cash decreases by v[i]) or we did nothing.
chose maximum of those two options - since we want to maximize
s1[j] = max(s1[j], s0[j-1]-v[i]);

2) If don't have stock at the end if ith day - this means we ether just sold it (cash increases by v[i]) or we did nothing.
chose maximum of those two options - since we want to maximize
s0[j] = max(s0[j], s1[j-1]+v[i]);

Now, if you notice that we always refer to [i-1] which means we don't have to store the whole matrix: we just need the last column.
This gives O(N*k) time, O(k) memory algorithm.

- 0xF4 January 09, 2015 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

@0xF4 your solution is not working for n=10 and k=3
prices = {2 7 3 9 8 7 9 7 1 9}
your algorithm outputs 8 but the correct answer is 19 and Here is explanation
buy on 1st day and sell it on the 2nd day, and then buy another on the 3rd day and sell it on the 4th, finally buys on 9th day and sells on the 10th day.So maximum profit = (7-2)+(9-3)+(9-1) = 19.

- akashchandrakar0 January 16, 2015 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

It's working. See the comment on the top - In my interpretation of the "k", buy and sell counts as a separate transactions..
invoke it with k=6 (i.e. 2*3) and you'll see that it returns 19 exactly as you expect.

- 0xF4 January 16, 2015 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

For the inner loop why is for(j = k; j >=1; j--) instead of for(j = 1; j <=k; j++)?

- Polarcodes February 17, 2015 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

O(k^2 * n)

public static int maxProfit(int[] arr, int k, int initialSum){
	if(arr == null){
		throw new NullPointerException();
	}
	if(k < 1 || initialSum < 1){
		throw new IllegalArgumentException();
	}

	//Create the base Case
	Partition base = findBest(arr, 0, arr.length-1);
	if(base == null){
		return null;
	}
	ArrayList<Partition> partitions = new ArrayList<Partition>();
	if(base.start > 0){
		partitions.add(new Partition(0, base.start, false));
	}
	partitions.add(base);
	if(base.end < arr.length -1){
		partitions.add(new Partition(base[1], arr.length -1, false));
	}
	boolean keepWorking = true;
	k--;
	while(keepWorking && k > 0){
		keepWorking = computePartition(arr, partitions);
		k--;
	}
	return computeValue(arr, partitions, initialSum);
}

static class Partition{
	int start, end;
	boolean counts;
	
	Partition(int start, int end, boolean counts){
		this.start = start;
		this.end = end;
		this.counts = counts;
	}
}

private static Partition findBest(int[] arr, int start, int end){
	//find the lowest value and the highest values
	int lowestVal = Integer.MAX_VALUE;
	int lowestIndex = -1;
	int highestVal = Integer.MIN_VALUE;
	int highestIndex = -1;
	for(int i = start; i <= end; i++){
		int val = arr[i];
		if(val > lowestVal){
			lowestVal = val;
			lowestIndex = i;
		if(val > highestVal){
			highestVal = val;
			highestIndex = i;
		}
	}	
	//if the lowest index is before the highest, return that
	if(lowestIndex < highestIndex){
		return new Partition(lowestIndex, highestIndex, true);
	}
	if(lowestIndex == end && highestndex == start){
		return null;
	}
	//find the lowest index before the Highest
	Partition lower = findBest(arr, start, lowestIndex);
	int lowerScore = Integer.MIN_VALUE;
	if(lower != null){
		lowerScore = computeValue(arr, Collections.asList(lower), 1000);
	}
	//find the highest after the lowest
	Partition higher = findBest(arr, highestIndex, end);
	int higherScore = Integer.MIN_VALUE;
	if(higher != null){
		higherScore = computeValue(arr, Collections.asList(higher), 1000);
	}
	//return the partition with the largest difference
	if(lowerScore > higherScore){
		return lower;
	}
	return higher;
}

private static Partition findWorst(int[] arr, int start, int end){
	//find the lowest value and the highest values
	int lowestVal = Integer.MAX_VALUE;
	int lowestIndex = -1;
	int highestVal = Integer.MIN_VALUE;
	int highestIndex = -1;
	for(int i = start; i <= end; i++){
		int val = arr[i];
		if(val > lowestVal){
			lowestVal = val;
			lowestIndex = i;
		if(val > highestVal){
			highestVal = val;
			highestIndex = i;
		}
	}	
	//if the lowest index is after the highest, return that
	if(lowestIndex > highestIndex){
		return new Partition(lowestIndex, highestIndex, false);
	}
	if(highestIndex == end && lowestIndex == start){
		return null;
	}
	//find the Highest index before the lowest
	Partition lower = findWorst(arr, start, lowestIndex);
	int lowerScore = Integer.MAX_VALUE;
	if(lower != null){
		lowerScore = computeValue(arr, Collections.asList(lower), 1000);
	}
	//find the Lowest after the Highest
	Partition higher = findWorst(arr, highestIndex, end);
	int higherScore = Integer.MAX_VALUE;
	if(higher != null){
		higherScore = computeValue(arr, Collections.asList(higher), 1000);
	}
	//return the partition with the largest difference
	if(lowerScore < higherScore){
		return lower;
	}
	return higher;
}

private static boolean computePartition(int[] arr, ArrayList<Partition> partitions){
	int changeLocation = -1;
	ArrayList<Partition> changes = null;
	int changeScore = 0;
	for(int i = 0; i < partition.size(); i++){
		Partition partition : partitions.get(i);
		ArrayList<Partition> testChanges = new ArrayList<Partition>();
		if(partition.counts){
			Partition testWorst = findWorst(arr, partition.start, partition.end);
			if(testWorst == null){
				continue;
			}
			if(testWorst.start-1 > partition.start){
				testChanges.add(new Partition(partition.start, testWorst.start-1, true);
			}
			testChanges.add(testWorst);
			if(testWorst.end+1 < partition.end){
				testChanges.add(new Partition(testWorst.end+1, partition.end, true);
			}
		}
		else{
			Partition testBest = findBest(arr, partition.start, partition.end);
			if(testBest == null){
				continue;
			}
			if(testBest.start-1 > partition.start){
				testChanges.add(new Partition(partition.start, testWorst.start-1, false);
			}
			testChanges.add(testBest);
			if(testBest.end+1 < partition.end){
				testChanges.add(new Partition(testBest.end+1, partition.end, false);
			}
		}
		int testScore = computeValue(arr, testChanges, 1000);
		if(testScore > changeScore){
			changes = testChanges;
			changeScore = testScore;
			changeLocation = i;
		}
	}
	if(changeLocation > -1){
		partitions.remove(changeLocation);
		for(int i = 0; i < changes.size(); i++){
			partitions.add(changes.get(i), changeLocation + i);
		}
		return true;
	}
	return false;
}

private static int computeValue(int[] arr, ArrayList<Partition> partitions, int initialSum){
	int total = initialSum;
	for(Partition partition : partitions){
		if(partition.counts){
			total /= arr[partition.start];
			total *= arr[partition.end];
		}
	}
	return total - intialSum;
}

- zortlord December 17, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

O(nk) time; O(nk) space.

public class Stock
{
  private static int OWN = 0;
  private static int SOLD = 1;

  public static int maxProfit(int[] v, int k)
  {
    int[][][] profit = new int[v.length][k + 1][2];
    profit[0][0][OWN] = Integer.MIN_VALUE;
    profit[0][0][SOLD] = 0;
    for (int j = 1; j <= k; j++)
    {
      profit[0][j][OWN] = -v[0];
      profit[0][j][SOLD] = 0;
    }
    for (int i = 1; i < v.length; i++)
    {
      profit[i][0][OWN] = profit[i - 1][0][OWN];
      profit[i][0][SOLD] = profit[i - 1][0][SOLD];
      for (int j = 1; j <= k; j++)
      {
        profit[i][j][OWN] = Math.max(profit[i - 1][j][OWN], profit[i - 1][j - 1][SOLD] - v[i]);
        profit[i][j][SOLD] = Math.max(profit[i - 1][j][SOLD], profit[i - 1][j - 1][OWN] + v[i]);
      }
    }
    return profit[v.length - 1][k][SOLD];
  }
}

- Anonymous December 18, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 4 vote

Orignial problem from LeetCode "Best Time to Buy and Sell Stock III"
O(NK)-spacen and time, DP

class Solution {
public:
    int maxProfit(vector<int> &prices) {
        // DP solution from Discussion board
        int n = prices.size();
        if(n<=1) return 0;
        
        double best[3][n];
        for(int i = 0; i<3; i++) best[i][0]=0;
        for(int j = 1; j<n; j++) best[0][j]=0;
        
        for(int i = 1; i<3; i++)
        {
            double tmpMax = best[i-1][0]-prices[0];
            for(int j =1; j<n; j++)
            {
                best[i][j] = max(best[i][j-1], prices[j]+tmpMax);
                tmpMax = max(tmpMax, best[i-1][j]-prices[j]);
            }
        }
        return best[2][n-1];
    }
};

- zzz December 18, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

Can you please explain the algorithm behind it.
Thanks!

- Charu Mehndiratta January 04, 2015 | Flag
Comment hidden because of low score. Click to expand.
1
of 1 vote

Doesn't this do k buy-sells, but not make sure that they do not overlap?

- Anonymous January 07, 2015 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

voting -1 as it doesn't do k transactions. (your solution doesn't have any limit on number of transactions)

- MIG January 08, 2015 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

//O(nlogn)
int maxProfile(vector<int> &prices, int k){
    if(prices.size()<2 || k<1) return 0;
    vector<int> positiveProfile;
    int minp = prices[0];
    for(int i=1; i<prices.size();i++){
        if(prices[i]>=prices[i-1]) continue;
        positiveProfile.push_back(prices[i-1]-minp);
        minp = prices[i];
    }
    positiveProfile.push_back(prices[prices.size()-1]-minp);
    sort(positiveProfile.begin(), positiveProfile.end());
    int maxKprofile = 0;
    for(int i=0; i<k && positiveProfile.size()-i>=0; i++)
        maxKprofile += positiveProfile[positiveProfile.size()-1-i];
    return maxKprofile;
}

- simon.zhangsm December 19, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

this is incorrect.
counter example: 1 2 3 4 k = 2

index expression becomes negative
>maxKprofile += positiveProfile[positiveProfile.size() - 1 - i];

- 0xF4 December 19, 2014 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

Your solution is only correct when K is more than positiveProfile.size(). Keep in mind that the neighbor positive profiles can be combine to a single positive profile. Just as some of contributors of this thread presented the counter examples.

- Peter Tang January 17, 2015 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

The key is to find all maximum increment subsequence. For example, the input is 4 3 2 5 4 6 7 1 7 8 5 6, the possible subsequence are [2 5] [4 6 7] [1 7 8] [5 6]. For these sub sequences, the profit are 3, 3, 7, 1. Find the top K profits from 3, 3, 7, 1. Use a K min heap to keep the results.
In this way, the time is O(N+logK), space is O(K)
Correct me if I'm wrong.

- allen.lipeng47 December 20, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

According to you , for { 100, 180, 260, 310, 295, 535, 695 } and k = 1 , possible subsequence would be : {100, 180, 260, 310} , {295, 535, 695} , profits are = 210, 400 , out of this ans = 400

but maximum profit would be when buy at day 1 and sell at last ie. 695-100 = 595

- Source December 20, 2014 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

Thanks Source. You make sense! Well today, I found out this problem is a kinda complex DP problem. It requires a local[][] and global[][] to restore. Just like what simon.zhangsm showed.
Let me give the code I passed today:

public static int bestTimeToBuySellStockAtMostKTimes(int[] prices, int k){
		if(prices==null || prices.length==0)  
	        return 0;  
	    int[] local = new int[prices.length];  
	    int[] global = new int[prices.length];  
	    for(int i=0;i<prices.length-1;i++)  
	    {  
	    	int diff = prices[i+1]-prices[i];  
	        for(int j=k;j>=1;j--)  
	        {  
	            local[j] = Math.max(global[j-1]+(diff>0?diff:0), local[j]+diff);  
	            global[j] = Math.max(local[j],global[j]);  
	        }  
	    }
	    return global[k];
	}

- allen.lipeng47 December 21, 2014 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

Hi 0xF4, could you please provide an counter-example?

- allen.lipeng47 December 21, 2014 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

I realized, that I was wrong. You algorithm is fine (and in fact identical to simon.zhangsm's solution if you trim the allocation to k+1).
The difference btw (simon's and yours) vs (my and anonymous') solution - we interpret values of k differently - you count buy-wait-and-sell as a single transaction, vs. counting buy and sell as separate
operations, but we do generate same results.

(to avoid confusing others - I deleted original post where I'm saying that your solution is wrong)

- 0xF4 December 21, 2014 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

cheers!

- allen.lipeng47 December 21, 2014 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

Hi Source,
Allen's solution would work with slight change. Here is the discrepancy in your example above,

According to you , for { 100, 180, 260, 310, 295, 535, 695 } and k = 1 , possible subsequence would be : {100, 180, 260, 310} , {295, 535, 695} , profits are = 210, 400. so the answer is k = 2, and profit = 610. as our target is to find the max profit. Unless you tell me that there is a better profit.

but if we buy at day 1 and sell at last ie. 695-100 = 595, which is less than 610 and we are not looking for profit at k =1.

- sk March 05, 2015 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

#include <vector>
using namespace std;

int findMaxProfit( vector<int> &prices, int kTrans )
{
int maxProfit = 0;
int i = 0;
int curBuy = 0;
int trans = 0;

while(i < prices.size)
{
while( (i+1 < prices.size) && prices[i] > prices[i+1] )
{// advance forward until we find a sequence where there is a lower number in front of a larger number
i++;
}

if ( i+1 == prices.size ) // the end
break;

curBuy = prices[i];

// traverse until we find a lower price point(and stop, the current value is the highest price until a transition lower)
while( (i+1 < prices.size) && prices[i] < prices[i+1] )
{
i++;
}

if ( i+1 == prices.size ) // the end
break;

// perform a sell (high - low)
maxProfit += (prices[i] - curBuy);

if ( ++trans >= kTrans )
break;

i++; // advance to the next buying opportunity
}

return maxProfit;
}

- ntf December 21, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

class Solution {
    public:
        int maxProfit(vector<int> &prices) {
            int f[3] = {0};
            int g[3] = {0};

            int n = prices.size() - 1;
            for (int i = 0; i < n; ++i) {
                int diff = prices[i+1] - prices[i];
                int m = min(i+1, 2);
                for (int j = m; j >= 1; --j) {
                    f[j] = max(f[j], g[j-1]) + diff;
                    g[j] = max(g[j], f[j]);
                }
            }
            return max(g[1], g[2]);
        }
    };

- Source January 03, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

Above solutions are in the O(kn) where k can max to n-1 in the worst case. then the complexity becomes O(n^2).

Instead

public int maxProfit(Vector<Integer> prices) {

int accumulatedProfit = 0;

int n = prices.size();

//order n
for (int i=0; i < n-1; i++) {

int diff = prices.get(i+1) - prices.get(i);
if (diff < 0) { //distinguish profitable transactions
if (accumulatedProfit > 0) {
//insert self balanced binary tree like AVL
//order log n
}
accumulatedProfit = 0;
} else {
accumulatedProfit += diff;
}
}

//do reverse in-order traversal
//right,root,left
//push k elements to array
//order log n

int sum = 0;
//sum k elements in the array
//order k (max n-1)

return sum;
}


Here total complexity is O(n log n).

- ramyaa_c_k January 07, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

Above solutions are in the O(kn) where k can max to n-1 in the worst case. then the complexity becomes O(n^2).

Instead

public int maxProfit(Vector<Integer> prices) { 

int accumulatedProfit = 0; 

int n = prices.size(); 

//order n 
for (int i=0; i < n-1; i++) { 

int diff = prices.get(i+1) - prices.get(i); 
if (diff < 0) { //distinguish profitable transactions 
if (accumulatedProfit > 0) { 
//insert self balanced binary tree like AVL 
//order log n 
} 
accumulatedProfit = 0; 
} else { 
accumulatedProfit += diff; 
} 
} 

//do reverse in-order traversal 
//right,root,left 
//push k elements to array 
//order log n 

int sum = 0; 
//sum k elements in the array 
//order k (max n-1) 

return sum; 
}

Here total complexity is O(n log n).

- ramyaa_c_k January 07, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

As some of the contributors pointed out that the main issue of this problem is that when K is less than the buy-selling opportunities. Then all local optimals have to be combined with neighbor opportunities in order to reach higher profit.

When K < N, then it is not that simple as some contributors suggested that simply pick up the most K profitable opportunities from N and then this problem can be solved by heap sort with K top values. Why is it not simple? Because when K < N, the neighbor opportunities can be combined together to become even bigger opportunities, which makes more profit than both individually. For instance, N=2 opportunities (1, 3) and (2, 5), and K=1 transaction. Then the profit we can make is not 5-2=3, but 5-1=4. In this example we need to find global bottom and top to make the most profit. Therefore when K < N, we have to explore all the combinations of all possible merging of neighbor opportunities to get the most profit. For instance N opportunities and K=N-1 transactions, we need to check each combination of 2 neighbor opportunities.
- Merge 0 and 1 to get N-1 opportunities and N-1 transactions
- Merge 1 and 2 to get N-1 opportunities and N-1 transactions
......
- Merge N-2 and N-1 to get N-1 opportunities and N-1 transactions
- Take the maximal value above N-1 combinations.

I have crafted a DP solution. Read more from here: cpluspluslearning-petert.blogspot.co.uk/2015/01/dynamic-programming-stock-best-buy-and.html

- Peter Tang January 17, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

Test:

void TestCases()
{
    {
        std::vector<size_t> ticks = { 1, 2, 3, 4, 5, 6, 7 };
        // BuySellEntries: (1, 7)
        assert(BestBuySell(ticks, 0) == 0);
        assert(BestBuySell(ticks, 1) == 6);
        assert(BestBuySell(ticks, 2) == 6);
    }
    
    {
        std::vector<size_t> ticks = { 1, 2, 3, 4, 2, 6, 7 };
        // BuySellEntries: (1, 4), (2, 7)
        assert(BestBuySell(ticks, 0) == 0);
        assert(BestBuySell(ticks, 1) == 6);
        assert(BestBuySell(ticks, 2) == 8);
        assert(BestBuySell(ticks, 3) == 8);
    }

    {
        std::vector<size_t> ticks = { 1, 2, 3, 4, 2, 6, 7, 2, 4, 6};
        // BuySellEntries: (1, 4), (2, 7), (2, 6)
        assert(BestBuySell(ticks, 0) == 0);
        assert(BestBuySell(ticks, 1) == 6);
        assert(BestBuySell(ticks, 2) == 10);
        assert(BestBuySell(ticks, 3) == 12);
        assert(BestBuySell(ticks, 4) == 12);
    }

    {
        std::vector<size_t> ticks = { 1, 2, 3, 4, 2, 6, 7, 2, 4, 6 , 1, 5, 9};
        // BuySellEntries: (1, 4), (2, 7), (2, 6), (1, 9)
        assert(BestBuySell(ticks, 0) == 0);
        assert(BestBuySell(ticks, 1) == 8);
        assert(BestBuySell(ticks, 2) == 14);
        assert(BestBuySell(ticks, 3) == 18);
        assert(BestBuySell(ticks, 4) == 20);
        assert(BestBuySell(ticks, 5) == 20);
    }

    {
        std::vector<size_t> ticks = { 4, 3, 2, 5, 4, 6, 7, 1, 7, 8, 5, 6 };
        // BuySellEntries: (2, 5), (4, 7), (1, 8), (5, 6)
        assert(BestBuySell(ticks, 0) == 0);
        assert(BestBuySell(ticks, 1) == 7);
        assert(BestBuySell(ticks, 2) == 12);
        assert(BestBuySell(ticks, 3) == 13);
        assert(BestBuySell(ticks, 4) == 14);
        assert(BestBuySell(ticks, 5) == 14);
    }
}

- Peter Tang January 17, 2015 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

Use two dynamic programming equations to solve the problem successfully.

public int solve(int[] v, int t){                                                                                                                                             
        int d = v.length;                                                                                                                                                         
        int[][] b = new int[d + 1][t + 1]; // b[i][j] means jth transcation is buying until ith day                                                                               
        int[][] s = new int[d + 1][t + 1]; // s[i][j] means jth transcation is selling until ith day                                                                              
                                                                                                                                                                                  
        int i, j, k;                                                                                                                                                              
                                                                                                                                                                                  
        for(i = 0; i <= d; i ++)                                                                                                                                                  
            b[i][0] = Integer.MIN_VALUE;                                                                                                                                          
                                                                                                                                                                                  
        for(i = 1; i <= d; i ++){                                                                                                                                                 
            for(j = 1; j <= i && j <= t ; j++){                                                                                                                                   
                int maxSell = Integer.MIN_VALUE;                                                                                                                                  
                int maxBuy = Integer.MIN_VALUE;                                                                                                                                   
                                                                                                                                                                                  
                for(k = j - 1; k <= i - 1; k++){                                                                                                                                  
                    maxBuy = max(maxBuy, s[k][j - 1] - v[i - 1]);                                                                                                                 
                    maxSell = max(maxSell, b[k][j - 1] + v[i - 1]);                                                                                                               
                }                                                                                                                                                                 
                                                                                                                                                                                  
                s[i][j] = maxSell;                                                                                                                                                
                b[i][j] = maxBuy;                                                                                                                                                 
            }                                                                                                                                                                     
        }
	return s[d][t];
    }

- Anonymous January 19, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

Algo:
Strategy: Buy at valley bottom, sell at mountain top of the price curve
check from the beginning of all stock price v[i] till either all are checked or max K is reached
find a valley bottom price, transaction count increments by 1 (one buy)
find a moutain top price, transaction count increments by 1 (one sell)
the delta is summed up to the total profit
move to check next day price

- Kevin February 13, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

int maxim(int* price, int days, int K, int cash, int stock) {
  if (days == 0 || K == 0)
    return cash;
  
  int profit;
  if (stock) { 
    //can sell
    profit = maxim(price + 1, days - 1, K - 1, cash+*price, 0);
  } else {
    //can buy
    profit = maxim(price + 1, days - 1, K - 1, cash-*price, 1);
  }
  
  //do nothing
  int nothing = maxim(price + 1, days - 1, K, cash, stock);
  
  return profit > nothing ? profit : nothing;
}

- benjamin March 19, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

The DP problem seems to be the best solution. I tried it on my own and found another way, but it's not optimal. However, still wanted to post it here.

Say we have stock prices s = 3 4 1 2 3 5 1
s[2] = 1

Now we can use a sorted map with s[i] as key and i as value.

Now we create two pointers a and b. a starts from the front of the sorted map and b starts from the end.
We move a forward and b backward and at each step check if map[a] < map[b] i.e. does a occur before b in the stock prices. As soon as this condition is true, we've found our first pair of prices a, b which gives us maximum profit. If we are allowed k transactions we simply keep moving a and b towards each other until we have satisfied map[a] < map[b] k/2 times (k transactions: k/2 buys and k/2 sells).

What do you guys think?

- tandemfelix March 30, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

Check out my video explaining solution for buy selling stock to maximize profit with at most K transactions.

- Tushar Roy January 10, 2016 | Flag Reply


Add a Comment
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.

Learn More

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.

Learn More

Resume Review

Most engineers make critical mistakes on their resumes -- we can fix your resume with our custom resume review service. And, we use fellow engineers as our resume reviewers, so you can be sure that we "get" what you're saying.

Learn More

Mock Interviews

Our Mock Interviews will be conducted "in character" just like a real interview, and can focus on whatever topics you want. All our interviewers have worked for Microsoft, Google or Amazon, you know you'll get a true-to-life experience.

Learn More