## Google Interview Question for Software Engineers

Country: United States

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

``````public int maxProfit(int[] prices) {
int sell = 0, prev_sell = 0;
for (int price : prices) {
prev_sell = sell;
sell = Math.max(prev_buy + price, prev_sell);
}
return sell;
}``````

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

Looks like you understood the question pretty well. Can you please explain the question ?

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

Does this take care of the restriction "after you sell your stock, you cannot buy stock on next day" ?

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

Does this take care of the restriction "after you sell your stock, you cannot buy stock on next day." ?

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

public int maxProfit(int[] prices) {
int sell = 0, prev_sell = 0;
for (int price : prices) {
prev_sell = sell;
sell = Math.max(prev_buy + price, prev_sell);
}
return sell;
}

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

public int maxProfit(int[] prices) {
int sell = 0, prev_sell = 0;
for (int price : prices) {
prev_sell = sell;
sell = Math.max(prev_buy + price, prev_sell);
}
return sell;
}

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

``````int main() {
int a[] = {30,30,15,18,20,25,80};
int n = sizeof(a)/sizeof(a[0]);
int profit[n];
int mn[n];
mn[n-1] = a[n-1];
int minVal = a[0];
profit[0] = 0;
for(int i=1;i<n;i++) {
profit[i] = max(profit[i-1],a[i]-minVal);
minVal = min(minVal,a[i]);
}
for(int i=n-2;i>=0;i--) {
mn[i] = min(mn[i+1],a[i]);
}

for(int i=4;i<n;i++) {
profit[i] = max(profit[i],profit[i-1]);
for(int j=i-3;j>=1;j--) {
profit[i] = max(profit[i],(max(a[i]-mn[0], profit[j]+(a[i]-mn[j+2]))));
}
}
for(int i=0;i<n;i++)
cout<<profit[i]<<" ";
cout<<profit[n-1]<<endl;
return 0;
}``````

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

``````int main() {
int a[] = {30,30,15,18,20,25,80};
int n = sizeof(a)/sizeof(a[0]);
int profit[n];
int mn[n];
mn[n-1] = a[n-1];
int minVal = a[0];
profit[0] = 0;
for(int i=1;i<n;i++) {
profit[i] = max(profit[i-1],a[i]-minVal);
minVal = min(minVal,a[i]);
}
for(int i=n-2;i>=0;i--) {
mn[i] = min(mn[i+1],a[i]);
}

for(int i=4;i<n;i++) {
profit[i] = max(profit[i],profit[i-1]);
for(int j=i-3;j>=1;j--) {
profit[i] = max(profit[i],(max(a[i]-mn[0], profit[j]+(a[i]-mn[j+2]))));
}
}
for(int i=0;i<n;i++)
cout<<profit[i]<<" ";
cout<<profit[n-1]<<endl;
return 0;
}``````

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

We might want to use DP for this problem because of its subproblem nature for maximum profit.

``````#include    <iostream>
#include    <stdlib.h>
using namespace std;

int maxProfitRec(int a[],int i,int n) {
if(i >= n)  return 0;
int mx1 = maxProfitRec(a,i+1,n);
return max(mx1, a[i]+maxProfitRec(a,i+2,n));
}
int maxProfit(int a[],int n) {
int table[n+1];
table[0] = table[1] = 0;

for(int i=2;i<=n;i++) {
int mx = table[i-1];
for(int j=i-2;j>=0;j--) {
mx = max(table[j]+a[i-1],mx);
}
table[i] = mx;
}
return table[n];
}
int main() {
int a[] = {3,5,2,5,60,12,5,234,5,223,123};
int n  = sizeof(a)/sizeof(a[0]);

cout<< "DP Algo :"<<maxProfit(a,n) <<endl;
cout<< "Rec Algo:"<<maxProfitRec(a,0,n) <<endl;
return 0;
}``````

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

2 pm est :)

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.