## Google Interview Question for Software Engineers

• 5

Country: United States
Interview Type: In-Person

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

dynamic programming, O(n^3)

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

Unfortunately, any dynamic programming solution will assume trying all combinations of inflated on deflated balloons, and there're 2^N combinations. Though, a brute force approach would require O(N!) operations, so O(2^N) is still an improvement. With a downside of O(2^N) memory, of course.

For this problem you'll need a more clever way. We need to look at the least local minimum and burst it. Plus some corner cases when it happens to appear at one of the ends of the balloon row.

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

Unfortunately, any dynamic programming solution will assume trying all combinations of inflated on deflated balloons, and there're 2^N combinations. Though, a brute force approach would require O(N!) operations, so O(2^N) is still an improvement. With a downside of O(2^N) memory, of course.

For this problem you'll need a more clever way. We need to look at the least local minimum and burst it. Plus some corner cases when it happens to appear at one of the ends of the balloon row.

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

Unfortunately, any dynamic programming solution will assume trying all combinations of inflated on deflated balloons, and there're 2^N combinations. Though, a brute force approach would require O(N!) operations, so O(2^N) is still an improvement. With a downside of O(2^N) memory, of course.

For this problem you'll need a more clever way. We need to look at the least local minimum and burst it. Plus some corner cases when it happens to appear at one of the ends of the balloon row.

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

@lepeisi Would you kindly attach your code or at least the DP recursion formula?

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

``````public int maxCoins(int[] nums) {
int n = nums.length;
int[][] dp = new int[n][n];
for (int k = 2; k < n; ++k) {
for (int left = 0; left < n - k; ++left) {
int right = left + k;
for (int i = left + 1; i < right; ++i)
dp[left][right] = Math.max(dp[left][right], nums[left] * nums[i] * nums[right] + dp[left][i] + dp[i][right]);
}
}

return dp[n - 1];
}``````

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

However, I don't need to look for local minimum.

Note, here 'nums' is already attached with two '1' as boundary.

left and right are boundary indices for subproblems.

i is the balloon you want to burst.

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

@shoumikhin: Please explain your solution in more detail, preferably with an argument justifying its correctness. Why do we want to burst smallest balloons first?

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

@lepeisi can you please explain from where

``Math.max(dp[left][right], nums[left] * nums[i] * nums[right] + dp[left][i] + dp[i][right]);``

came ?

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

@shoumikhin not all dynamic problems have O(k^n) (or higher) complexity. This one definitely can be solved in O(n^3), which is optimal time here.

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

and should the question be if burst ith balloon, then (i-1)th and (i+1)th become adjacent?

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

what happen if you only have two or one element left. Say if there are only A1 A2, do you get A1 * A2 or 0 if burst A1? What about if there is only A1?

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

Are we looking for 3 elements (not necessarily consecutive) in this row of balloons that yield maximum product? So that we can burst some balloons in between them and then burst the middle of those 3 and get the maximum number of coins from single burst?

Or is the goal to find 3 consecutive elements that yield max product and we burst only once?

Or.. Is it about coming up with a strategy to burst all balloons so that accumulated number of coins is maximum?

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

please take some efforts to type q properly....exp doesnt seem to be correct

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

@shoumikhin You seem to understand the requirement quite well :-) Is the goal to maximize the sum of coins collected over all bursts of balloons till no balloon left?

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

I guess so.

Simplest example, given a row of balloons with coins for them:
8, 5, 6, 9, 3, 0, 2, 4, 1, 7

burst 0, get 3*0*2 coins -> 8, 5, 6, 9, 3, 2, 4, 1, 7
burst 1, get 4*1*7 coins -> 8, 5, 6, 9, 3, 2, 4, 7
burst 2, get 3*2*4 coins -> 8, 5, 6, 9, 3, 4, 7
burst 3, get 3*2*4 coins -> 8, 5, 6, 9, 4, 7
burst 4, get 9*4*7 coins -> 8, 5, 6, 9, 7
burst 5, get 8*5*6 coins -> 8, 6, 9, 7
burst 6, get 8*6*9 coins -> 8, 9, 7
burst 9, get 8*9*7 coins -> 8, 7
burst 7, get 8*7*1 coins -> 8
burst 8, get 1*8*1 coins

That's an optimal strategy and you can get (summing up) 1652 coins with it.

At each step you choose the least local minimum among all local minimums.
That helps make the balloons with higher value adjanced, and so gain bigger product later.

More interesting example:

1, 2, 3, 4, 5, 6, 7, 8, 9

There's no local minimum, so you should choose a triple with maximum product and burst the middle balloon:

burst 8, get 7*8*9 coins -> 1, 2, 3, 4, 5, 6, 7, 9
burst 7, get 6*7*9 coins -> 1, 2, 3, 4, 5, 6, 9
burst 6, get 5*6*9 coins -> 1, 2, 3, 4, 5, 9
burst 5, get 4*5*9 coins -> 1, 2, 3, 4, 9
burst 4, get 3*4*9 coins -> 1, 2, 3, 9
burst 3, get 2*3*9 coins -> 1, 2, 9
burst 2, get 1*2*9 coins -> 1, 9
burst 1, get 1*1*9 coins -> 9
burst 9, get 1*9*1 coins

That will bring you 1530 coins total.

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

My code passed these two

>int[] nums = {1, 8, 5, 6, 9, 3, 0, 2, 4, 1, 7, 1};

>1652

>int[] nums = {1, 1, 2, 3, 4, 5, 6, 7, 8, 9, 1};

>1530

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

Can you show that the greedy strategy of bursting highest triples first is optimal?

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

Using the algorithm provided by shoumikhin, here is the code in Java. Time Complexity: O(n^2). Space Complexity: O(n). It works for both the examples mentioned above. The concept is basically either choose the Index the gives minimum product and remove it. However if such index lies at the corners, than choose the Index that gives the maximum product and remove it. This choice has to be made at every iteration.

``````/*
* @author shivam.maharshi
*/
public class BurstBaloons {

public static int maxValue(int[] a) {
int res = 0;
List<Integer> list = new ArrayList<>();
for (int num : a)
while (list.size() > 3) {
int min = getMinValue(list);
int index = findIndexOfValue(list, min);
if (!(index > 0 && index < (list.size() - 1))) {
index = getMaxProductIndex(list);
}
res += list.get(index - 1) * list.get(index) * list.get(index + 1);
list.remove(index);
}
res += list.get(0) * list.get(1) * list.get(2) + list.get(0) * list.get(2) + Math.max(list.get(0), list.get(2));
System.out.println(res);
return res;
}

private static int getMaxProductIndex(List<Integer> list) {
int index = 0;
int maxProd = Integer.MIN_VALUE;
for (int i = 1; i < list.size() - 1; i++) {
if (list.get(i - 1) * list.get(i) * list.get(i + 1) > maxProd) {
maxProd = list.get(i - 1) * list.get(i) * list.get(i + 1);
index = i;
}
}
return index;
}

private static int getMinValue(List<Integer> list) {
int min = Integer.MAX_VALUE;
for (int num : list)
if (num < min)
min = num;
return min;
}

private static int findIndexOfValue(List<Integer> list, int num) {
for (int i = 0; i < list.size(); i++)
if (list.get(i) == num)
return i;
return -1;
}``````

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

Using the algorithm proposed above, here is the code in Java. Time Complexity: O(n^2). Space Complexity: O(n). The logic is:
1. If there exist an index which has the minimum number, than its product and remove the index. However this must not lie in the corner.
2. If 1 is not possible than chose the index that gives maximum product and remove this index.

``````/ *
* @author shivam.maharshi
*/
public class BurstBaloons {

public static int maxValue(int[] a) {
int res = 0;
List<Integer> list = new ArrayList<>();
for (int num : a)
while (list.size() > 3) {
int min = getMinValue(list);
int index = findIndexOfValue(list, min);
if (!(index > 0 && index < (list.size() - 1))) {
index = getMaxProductIndex(list);
}
res += list.get(index - 1) * list.get(index) * list.get(index + 1);
list.remove(index);
}
res += list.get(0) * list.get(1) * list.get(2) + list.get(0) * list.get(2) + Math.max(list.get(0), list.get(2));
System.out.println(res);
return res;
}

private static int getMaxProductIndex(List<Integer> list) {
int index = 0;
int maxProd = Integer.MIN_VALUE;
for (int i = 1; i < list.size() - 1; i++) {
if (list.get(i - 1) * list.get(i) * list.get(i + 1) > maxProd) {
maxProd = list.get(i - 1) * list.get(i) * list.get(i + 1);
index = i;
}
}
return index;
}

private static int getMinValue(List<Integer> list) {
int min = Integer.MAX_VALUE;
for (int num : list)
if (num < min)
min = num;
return min;
}

private static int findIndexOfValue(List<Integer> list, int num) {
for (int i = 0; i < list.size(); i++)
if (list.get(i) == num)
return i;
return -1;
}``````

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

``````public int findMaxCoins(int[] arr)throws NullPointerException
{
if(arr==null)
{
throw new NullPointerException();
}
return maxGain(1,0,arr.length-1,1,arr);
}

private int maxGain(int left, int start,int end, int right, int[] arr)
{
if(s>e)
{
return 0;
}
if(s==e)
{
return arr[s];
}
//result of bursting the left most balloon
int leftEnd=(arr[start]*arr[start+1]*left) + maxGain(left,start+1,end,right,arr);
//result of bursting the right most balloon
int rightEnd=(arr[end]*arr[end-1]*right)+maxGain(left,start,end-1,right,arr);

int midMax=0//result of bursting any balloon other then left most and right most balloons
for(int i=start+1;i<end;i++)
{
int l=maxGain(left,start,i-1,arr[i+1],arr);
int r=maxGain(arr[i-1],i+1,end,right,arr);
midMax=Math.max(midMax,l+r+(arr[i]*arr[i-1]*arr[i+1]));
}

return Math.max(midMax,Math.max(leftEnd,rightEnd));
}

//Time Complexity: Exponential O(2^N). Space complexity: O(N).``````

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

Window Sliding problem.
1. Slide windows of size 3 and find multiplication of n-1*n*n+1.
2. Keep max variable for max multiplication and ptr to n.
3. keep a DP[] array to store individual multiplication.
4. Remove n and use max val. Also update n+1 to n and dp[n+1] only. Find max. MaxHeap can be used but will need to create object to keep relationships.
5. o(n^2) to find max n times => can be reduced to o(nlogn) using heap or sorting.

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

//I spent a little more time on this problem and got a more efficient solution

``````public int maxGain(int[] arr)throws NullPointerException
{
if(arr==null)
{
throw new NullPointerException();
}
int[] tmp=new int[arr.length+2];
tmp=1;//Used for computing value after bursting arr
tmp[tmp.length-1]=1;//Used for computing value of bursting arr[arr.length-1]
Arrays.copy(arr,tmp,0,1,arr.length);
arr=tmp;
int[] results=new int;//results--max gain from popping balloon at index i, results--max gain from not popping balloon at index i
results=1;//updated balloon if balloon at index i is popped
results=1;//update balloon if balloon at index i is not popped
for(int i=1;i<arr.length-1;i++)
{
int i_1_pop=results;
int pop_i_pop_i_1=(arr[i]*arr[i+1]*results)+results//Max gain from popping baloon at index i and balloon at index i_1
int pop_i_not_i_1=(arr[i]*arr[i+1]*results)+results//Max gain from popping baloon at index i and not popping balloon at i_1

//Max gain if balloon i is popped.
if(pop_i_pop_i_1>pop_i_not_i_1)
{
results=pop_i_pop_i_1;
}
else
{
results=pop_i_not_i_1;
results=results;//If i_1 was not popped then i will contain the same value as i_1
}

//Max gain if balloon i is not popped.
results=Math.max(i_1_pop,resultsp);//Maximum of popping or not popping balloon i_1
results=arr[i];
}
return Math.max(results,results);
}

//Time complexity O(N) space complexity O(N) where N is the size of the input array``````

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

Sliding window of size 3. For each window, compute max coins of the remaining balloons after popping the middle balloon in the window.
Track overall max.

``````private static int findMaxCoins(List<Balloon> balloons) {
if (balloons.size() == 1) {
return balloons.get(0).value;
}
else if (balloons.size() == 2) {
return balloons.get(0).value * balloons.get(1).value;
}
else if (balloons.size() == 3) {
return (balloons.get(0).value * balloons.get(1).value * balloons.get(2).value) + (balloons.get(0).value * balloons.get(2).value);
}
else {
int maxCoins = Integer.MIN_VALUE;
for (int i = 1; i < balloons.size()-1; i++) {
Balloon balloonToPop = balloons.get(i);
int coinsFromPop = balloons.get(i-1).value * balloonToPop.value * balloons.get(i+1).value;
balloons.remove(i);
int maxCoinsRemaining = findMaxCoins(balloons);
maxCoins = Math.max(maxCoins, coinsFromPop + maxCoinsRemaining);
}
return maxCoins;
}
}

// Helper class so we can call List.remove(index) and not confuse with the value
private static class Balloon {
int value;
}``````

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

What about going in a groups of 3 items starting with 0 (which gives us -1 (=1), 0 and 1) and ending with n-1 and adding the both value of current element and result of multiplication of those items to the BST (ordering by result of multiplication).

BST elements besides simple left and right fields would have to feature prev and next elements - pointers to other nodes of the BST, that come before and after the elements in balloons list. That would be a mix of BST and a double-linked list.Adding elements to such tree given a list as an input would yield complexity of O(n*log n).

Then with such tree, until the tree is not empty, we would extract minimum element O(log n). If it has both prev and next pointers set (it's not on the boundary) then we would add it's multiplication result to the overall sum, get prev and next elements, remove them from the tree and add them again so that they become adjacent to each other (that means dividing their multiplication result by value of popped element and multiplying it by the value on the element that they're becoming adjacent to. Also we need to change their next and prev fields to point to each other).

If this minimal value in a tree is a boundary value (it has empty prev or next field), we look for maximum value, and pop it with the rules mentioned above.

This process is taking place for n elements and for each of them lookups of minimum/maximum elements take log n time, which gives us complexity of O(n*log n).

The overall time complexity is O(n*log n) and space complexity is O(n)

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

What about going in a groups of 3 items starting with 0 (which gives us -1 (=1), 0 and 1) and ending with n-1 and adding the both value of current element and result of multiplication of those items to the BST (ordering by result of multiplication).

BST elements besides simple left and right fields would have to feature prev and next elements - pointers to other nodes of the BST, that come before and after the elements in balloons list. That would be a mix of BST and a double-linked list.Adding elements to such tree given a list as an input would yield complexity of O(n*log n).

Then with such tree, until the tree is not empty, we would extract minimum element O(log n). If it has both prev and next pointers set (it's not on the boundary) then we would add it's multiplication result to the overall sum, get prev and next elements, remove them from the tree and add them again so that they become adjacent to each other (that means dividing their multiplication result by value of popped element and multiplying it by the value on the element that they're becoming adjacent to. Also we need to change their next and prev fields to point to each other).

If this minimal value in a tree is a boundary value (it has empty prev or next field), we look for maximum value, and pop it with the rules mentioned above.

This process is taking place for n elements and for each of them lookups of minimum/maximum elements take log n time, which gives us complexity of O(n*log n).

The overall time complexity is O(n*log n) and space complexity is O(n)

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

The problem could be solved with dynamic programming O(n^3)
the recursive relation is cost[i][j] = max(cost[i][K - 1] + cost[K+1][j] + nums[i-1]*nums[K]*nums[j+1]
where cost[i][j] means cost taken when all ballons in [i..j] range are burst before ballons at i - 1 and j+1. With other words, cost to burst all ballons in range [i..j] before ballons at i - 1 and j + 1 have been burst is max by K element in range [i..j]:
cost of burst in range[i..K - 1] before burst ballon K and ballon i - 1 +
cost of burst in range[k + 1, j] before burst ballon k and ballon j+ 1 +
cost of burst of K-th ballon (that is nums[K]*nums[i-1]*nums[j+1] because all ballons between K and i and K and j have been already burst and ballons i -1, K and j +1 become adjacent.

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

Test case

input [5,2,3,4,1,9,10]

the solution is 819
if you remove the item in index order 1,4,3,2,5,0,6.

5X2X3
+ 4X1X9
+ 3X4X9
+ 5X3X9
+ 5X9X10
+ 5X10
+ 10

=819

The solutions I tested here doesn't seem to find the solution

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

``````public class BaloonShooting {

public static int findScore(List<Integer> weightages) {

int score = 0;

if (weightages.size() == 0)
return 0;
else if (weightages.size() == 1) {
return weightages.get(0);
} else if (weightages.size() == 2) {
int a = weightages.get(0);
int b = weightages.get(1);
if (a > b)
return (b + 1) * a;
else
return (a + 1) * b;
} else if (weightages.size() == 3) {
score = weightages.get(0) * weightages.get(1) * weightages.get(2);
weightages.remove(1);
return score + findScore(weightages);
} else {

int index = 0;

for (int i = 1; i < 3 && i < weightages.size() - 1; i++) {
int current = weightages.get(i - 1) * weightages.get(i) * weightages.get(i + 1);
if (current > score) {
score = current;
index = i;
}
}
// Shoot the baloon
weightages.remove(index);

return score + findScore(weightages);
}
}
}``````

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

``````public class BaloonShooting {

public static int findScore(List<Integer> weightages) {

int score = 0;

if (weightages.size() == 0)
return 0;
else if (weightages.size() == 1) {
return weightages.get(0);
} else if (weightages.size() == 2) {
int a = weightages.get(0);
int b = weightages.get(1);
if (a > b)
return (b + 1) * a;
else
return (a + 1) * b;
} else if (weightages.size() == 3) {
score = weightages.get(0) * weightages.get(1) * weightages.get(2);
weightages.remove(1);
return score + findScore(weightages);
} else {

int index = 0;

for (int i = 1; i < 3 && i < weightages.size() - 1; i++) {
int current = weightages.get(i - 1) * weightages.get(i) * weightages.get(i + 1);
if (current > score) {
score = current;
index = i;
}
}
// Shoot the baloon
weightages.remove(index);

return score + findScore(weightages);
}
}
}``````

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

``````public int maximum(int[] balloons){
int coins[] = new int[balloons.length+2];
int i =1;
for(int n : balloons){
coins[i++]= n;
}
coins=coins[i] =1;
int dp[][] = new int[coins.length][coins.length];
for(int i = 1; i <coins.length-1 ; ++i ){
for(int j =i ; j>=1 ; --j){
for(int k = i ; k<=j ; ++k){
dp[j][i] = Math.max(dp[j][i], dp[j][k-1]+ dp[k+1][i]+ coins[k]*coins[j-1]* coins[i+1]);
}	}
}
return dp[coins.length-2];
}``````

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

``````#include<iostream>

using namespace std;

int func(int a[],int n){

int mat[n][n];
for (int i = 0;i < n;i++){
for (int j = 0;j <n;j++)
mat[i][j] = 0;
}

for (int len = 1;len <= n;len++){
for (int i = 0;i < n-len+1;i++){
int j = len+i-1;
for (int k = i;k <= j;k++){
int left = 1;
int right = 1;

if(i != 0){
left = a[i-1];
}

if(j != n-1)
right = a[j+1];

int before = 0;
int after = 0;

if(i != k)
before = mat[i][k-1];

if(j != k)
after = mat[k+1][j];

mat[i][j] = max(left*a[k]*right+after+before, mat[i][j]);
}
}
}

cout << mat[n-1];

}

int main () {

int n;
cin >> n;
int a[n];

for (int i = 0;i < n;i++){
cin >> a[i];
}

func(a,n);

return 0;
}``````

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

#include<iostream>
using namespace std;

int score(int arr[], int left, int right, int n){
int max1=0;
int i,j,k;

for(i=left+1;i<=right-1;i++){
int cur=0;
cur=score(arr,left,i,n) + score(arr,i,right,n);
if(left==0 && right==n+1){
cur+=arr[i];
}
else{
cur+=arr[left]*arr[right];
}
if(cur>max1){
max1=cur;
}
}
return max1;
}

int main(){

int t;
cin>>t;
while(t--){

int n,i,j,k;

cin>>n;
int* arr=new int[n+2];

for(i=1;i<=n;i++){
cin>>arr[i];
}

arr=1;
arr[n+1]=1;

int p=score(arr,0,n+1,n);
cout<<p<<endl;
}

}

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

{
++_+_;_;_;_;_

}

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

lepeisi's solution is right.

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.