Google Interview Question
Software Engineer / DevelopersCountry: United States
Interview Type: In-Person
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
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.
> 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)
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];
}
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 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.
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.
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;
}
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];
}
}
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];
}
};
//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;
}
this is incorrect.
counter example: 1 2 3 4 k = 2
index expression becomes negative
>maxKprofile += positiveProfile[positiveProfile.size() - 1 - i];
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.
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
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];
}
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)
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.
#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;
}
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]);
}
};
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).
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).
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
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);
}
}
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];
}
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
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;
}
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?
- simon.zhangsm December 19, 2014