## Google Interview Question for Software Engineer / Developers

• 2

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

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

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

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

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.

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.

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)

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

@ 0xF4 : Thanks for explanation.

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

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.

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.

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

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

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

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.

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

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

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){
}
if(base.end < arr.length -1){
}
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){
}
if(testWorst.end+1 < partition.end){
}
}
else{
Partition testBest = findBest(arr, partition.start, partition.end);
if(testBest == null){
continue;
}
if(testBest.start-1 > partition.start){
}
if(testBest.end+1 < partition.end){
}
}
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++){
}
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];
}
}
}``````

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

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

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

Can you please explain the algorithm behind it.
Thanks!

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?

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

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

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

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

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

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

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

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.

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.

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

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

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

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

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

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

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

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)

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

cheers!

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

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.

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

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

if ( ++trans >= kTrans )
break;

}

return maxProfit;
}

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

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

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

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

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

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.

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

Test:

``````void TestCases()
{
{
std::vector<size_t> ticks = { 1, 2, 3, 4, 5, 6, 7 };
}

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

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

{
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)
}

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

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;

for(k = j - 1; k <= i - 1; k++){
maxSell = max(maxSell, b[k][j - 1] + v[i - 1]);
}

s[i][j] = maxSell;
}
}
return s[d][t];
}``````

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

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

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?

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.

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.