Google Interview Question Software Engineers
Country: United States
Interview Type: In-Person
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.
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.
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.
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[0][n - 1];
}
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.
@shoumikhin: Please explain your solution in more detail, preferably with an argument justifying its correctness. Why do we want to burst smallest balloons first?
@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 ?
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?
@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?
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.
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
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)
list.add(num);
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;
}
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)
list.add(num);
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;
}
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).
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.
//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[0]=1;//Used for computing value after bursting arr[0]
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[4];//results[0]--max gain from popping balloon at index i, results[1]--max gain from not popping balloon at index i
results[2]=1;//updated balloon if balloon at index i is popped
results[3]=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[0];
int pop_i_pop_i_1=(arr[i]*arr[i+1]*results[2])+results[0]//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[3])+results[1]//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[0]=pop_i_pop_i_1;
}
else
{
results[0]=pop_i_not_i_1;
results[2]=results[3];//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[1]=Math.max(i_1_pop,resultsp[1]);//Maximum of popping or not popping balloon i_1
results[3]=arr[i];
}
return Math.max(results[0],results[1]);
}
//Time complexity O(N) space complexity O(N) where N is the size of the input array
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);
balloons.add(i, balloonToPop);
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;
}
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)
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)
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.
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);
}
}
}
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);
}
}
}
public int maximum(int[] balloons){
int coins[] = new int[balloons.length+2];
int i =1;
for(int n : balloons){
coins[i++]= n;
}
coins[0]=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[1][coins.length-2];
}
#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[0][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;
}
#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[0]=1;
arr[n+1]=1;
int p=score(arr,0,n+1,n);
cout<<p<<endl;
}
}
dynamic programming, O(n^3)
- lepeisi November 26, 2015