Interview Question
Country: United States
Actually, F(sequence)= max over all i ( F(part of sequence indexed from 0 to i-1) + F(part of sequence indexed from i+1 to end) + 1).
isn't this pivot i supposed to be the first i for which corresponding weight is non zero?? because if you start punching any of the other bags you decrease the weight of its *two* neighbours. but if you start by punching the leftmost nonzero bag and proceed rightways successively eliminating the bags to the left, you should get the maximum punches as with every punch you decrease the weight of only *one* bag, namely the bag's right neighbour . correct me if i'm wrong.
@kubrick its wrong bcoz if the i/p is
3 2 3 2 1
then there can be max 5 punches but according to u it has just 4...
#include<stdio.h>
#include<string.h>
#include<conio.h>
int solve(int*,int);
int main()
{
int n,i,ans;
char a[50];
gets(a);
n=strlen(a);
int b[n];
for(i=0;i<n;i++)
{b[i]=a[i]-'0';}
ans=solve(b,n);
printf("%d\n",ans);
getch();
return 0;
}
int solve(int *a,int n)
{ int flag=0;
int i;
int temp,check,max=0;
for(i=0;i<n;i++)
{ if(a[i]>0)
{ flag=1; break;}
}
if(flag==0)
{ return 0;} // still we have to thin
for(i=0;i<n;i++)
{ if(a[i]<=0)
{continue;}
temp=a[i];
a[i]=0;
if(i>0)
a[i-1]--;
if(i<n-1)
a[i+1]--;
check=solve(a,n);
a[i]=temp;
if(i>0)
a[i-1]++;
if(i<n)
a[i+1]++;
if(check>max)
{ max=check;}
}
return max+1;
}
Mac, is that supposed to be an implementation of my algorithm, or a different algorithm?
@anonymous: shudn't the answer be 7 punches for your example? here's how you get it :- with 3 punches you destroy the first 2 bags. then with 3 more you destroy bags 3 and 4. with a last punch you destroy the 5th bag which is left. this is exactly what happens if you follow my algo. do i get the question wrong?
@anonymous
for the i/p 3 2 3 2 1 the o/p should be 7
start from left most side
1. 3 punches for first number
2. 0 punch for second number
3. 3 punches for third number
4. 0 punch for fourth number
5. 1 punch for fifth number
here is my code for it
#include<stdio.h>
#include<string.h>
int main()
{
int i,len,s=0;
char str[100]={'\0'};
scanf("%s",str);
len = strlen(str);
for(i=0;i<len-1;i++)
{
s = s+(str[i]-'0');
if((str[i+1]-str[i])>0)
str[i+1] = (str[i+1]-str[i])+'0';
else
str[i+1] = '0';
}
s+=(str[i]-'0');
printf("%d\n",s);
return 0;
}
yeah atul, exactly..here's my code
int max_punches_possible(int * weights, int index, int size)
{
int no_of_punch=0;
if(index>=(size-1))
{
no_of_punch=weights[index];
return no_of_punch;
}
if(weights[index]==0)
{
no_of_punch=max_punches_possible(weights,index+1,size);
return no_of_punch;
}
if(weights[index]<weights[index+1])
{
no_of_punch+=weights[index];
weights[index]=0;
weights[index+1]-=weights[index];
no_of_punch+=max_punches_possible(weights,index+1,size);
return no_of_punch;
}
no_of_punch+=weights[index];
no_of_punch+=max_punches_possible(weights,index+2,size);
return no_of_punch;
}
@kubrick
actually it was a question on code sprint sequoia.
i posted the same solution but my answer was declared wrong.(3 out of 10 test cases passed) i am still confused where i am wrong????
@atul: i don't know exactly why that happened..but i do know from experience that the interviewstreet compiler is sometimes erroneous.
@anonymous
for the i/p 3 2 3 2 1 the o/p should be 7
start from left most side
1. 3 punches for first number
2. 0 punch for second number
3. 3 punches for third number
4. 0 punch for fourth number
5. 1 punch for fifth number
Read the constraints correctly. When you punch a bag, its resistance is immediately set to 0. So then how can you have 3 punches for the 1st number?
file = open("sample.txt")
bags = []
zero_resistance_bags = 0
total_bags = 0
max_punch_bags_available = 0
punch_counter = 0
while 1:
line = file.readline()
if not line:
break
for i in range(0, len(line)):
bags.append( int(line[i]) )
if (int(line[i]) == 0):
zero_resistance_bags += 1
bags.sort()
total_bags = len(bags)
max_punch_bags_available = total_bags - zero_resistance_bags
print "max_punch_bags_available: ", max_punch_bags_available
print "total_bags: ", total_bags
print "zero_resistance_bags:", zero_resistance_bags
print bags
for i in range(0, len(bags)):
if (bags[i] != 0):
bags[i] = 0
punch_counter += 1
if ((i+1) <= len(bags)-1):
bags[i+1] -= 1
print punch_counter
guys i will still stick with my previous algo.... that is right try to read the ques carefully the o/p for 3 2 3 2 1 will be 5 :)
the thing is, it can take max n punches to destroy n bags. let me explain when when number of punches required will be less than n..
suppose there is a series of bags whose weights are like:-
1 2 2 2.... ( m 2's) 1.
it can be proved that max m+1 punches are required to destroy this series of punching bags rather than the normal value of m+2.
thus we'll have to count the number of such patterns and thereby modify the number of punches accordingly. i'm not sure but i think this ultimately boils down to the greedy approach. although time complexity will be better.
@Mac: I haven't inspected your solution for correctness, but that type of brute-force approach will definitely time out.
@ kubrick
@atul
you misunderstood the question. When you punch a bag, it is immediately destroyed regardless of what its resistance was.
@ AbhiMehta: your algorithm is wrong too. I didn't get much past your call to bags.sort(). That destroys the whole structure of the problem.
this works for all the test cases i've come up with..plz tell whether it fails for any..it's O(n)
#include<stdio.h>
#include<string.h>
int all_values(int *weights, int start, int end,int val)
{
while(start<=end)
{
if(weights[start]!=val)
{
return 0;
}
start++;
}
return 1;
}
int count_no_of_zeroes(int * weights, int size)
{
int count=0,i;
for(i=0;i<size;i++)
if(weights[i]==0)
count++;
return count;
}
int count_no_of_patterns(int * weights, int size) // returns no. of patterns 122...221
{
int prev=-1,i=0, count=0;
while(i<size)
{
if(weights[i]==0)
{
prev=-1;
i++;
}
if(weights[i]==1)
{
if(prev!=-1)
{
if(all_values(weights,prev+1,i-1,2))
{
count++;
i++;
prev=-1;
}
}
else
{
prev=i;
i++;
}
}
else
{
i++;
}
}
return count;
}
int max_punches_possible(int * weights, int size)
{
int punch, no_of_zeroes, no_of_patterns;
no_of_zeroes=count_no_of_zeroes(weights, size);
no_of_patterns=count_no_of_patterns(weights, size);
//printf("\n%d %d", no_of_zeroes, no_of_patterns);
punch=size-no_of_zeroes-no_of_patterns;
return punch;
}
int main()
{
int n,i,ans;
char a[50];
gets(a);
n=strlen(a);
int b[n];
for(i=0;i<n;i++)
{b[i]=a[i]-'0';}
ans=max_punches_possible(b,n);
printf("%d\n",ans);
//getch();
return 0;
}
@rukawa: sorry for the bug. here's the corrected code:-
#include<stdio.h>
#include<string.h>
int all_values(int *weights, int start, int end,int val)
{
while(start<=end)
{
if(weights[start]!=val)
{
return 0;
}
start++;
}
return 1;
}
int count_no_of_zeroes(int * weights, int size)
{
int count=0,i;
for(i=0;i<size;i++)
if(weights[i]==0)
count++;
return count;
}
int count_no_of_patterns(int * weights, int size) // returns no. of patterns 122...221
{
int prev=-1,i=0, count=0;
while(i<size)
{
//printf("\ni=%d",i);
if(weights[i]==0)
{
prev=-1;
i++;
}
if(weights[i]==1)
{
if(prev!=-1)
{
if(all_values(weights,prev+1,i-1,2))
{
count++;
i++;
prev=-1;
}
else
{
i++;
}
}
else
{
prev=i;
i++;
}
}
else
{
i++;
}
}
return count;
}
int max_punches_possible(int * weights, int size)
{
int punch, no_of_zeroes, no_of_patterns;
no_of_zeroes=count_no_of_zeroes(weights, size);
no_of_patterns=count_no_of_patterns(weights, size);
//printf("\n%d %d", no_of_zeroes, no_of_patterns);
punch=size-no_of_zeroes-no_of_patterns;
return punch;
}
int main()
{
int n,i,ans;
char a[50];
gets(a);
n=strlen(a);
int b[n];
for(i=0;i<n;i++)
{b[i]=a[i]-'0';}
ans=max_punches_possible(b,n);
printf("%d\n",ans);
//getch();
return 0;
}
@eugene.yarovoi
Dude your algo is correct and has the most efficient approach. But you missed out on one thing. What if there are no 1s in the input, for ex.
222232
or
22222
or
333333
You can keep a counter to check the min resistance in the input and increase it if the current min resistance is not present.
I thought of a greedy approach to the problem stated above. The approach is to hit the bag with the least amount of resistance first reduce the resistance of the corresponding neighbors and keep on iterating till all the resistances are down to 0 or less than 0.
min_resistance = 1
while(all_sandbags_resistance>0)
{
sandbags_destroyed=0
successful_iteration=0 //checks if any min-resistance bags were destroyed
for(i=1;i<=n;i++)
{
if(a[i]==min_resistance)
{
if(i-1>=1)
a[i-1]=a[i-1]-1
if(i+1<=n)
a[i+1]=a[i+1]-1
a[i]=0
punches_possible++
successful_iteration++
}
if(a[i]<=0)
{
sandbags_destroyed++
}
}
if(sandbags_destroyed==n) // all sandbags are destroyed
all_sandbags_resistance = 0;
if(successful_iteration==0) //if all the resistances of the sandbags are greater than min resistance then increase
min_resistance++
else
min_resistance = 1
}
}
I was thinking about a similar greedy approach too, but I couldn't prove it correct either, so I made a DP solution. To prove the correctness of the greedy approach, it would be sufficient to prove that if you have a sequence of 1s and 2s, it is correct to punch all the 1s first. 3s can never be destroyed except by a direct hit, so it's clearly correct to hit them last. 0s partition the input, so it's not necessary to consider them either.
I think the solution by dv is correct (the greedy approach), but I couldn't prove it. dv, do you have a proof for that?
I use a backtracking approach to solve it. First I want to discuss the effect of 0 in the array. Let say the array is 1 2 3 0 3 2 2. The problem can be reduced to two arrays (1 2 3) and (3 2 2). So we obtain the max punchs for two sub arrays and add them, then add by 1.So my approach for a[1..n] is as below:
int maxPunches(int a[], int start, int end)
For i=1 to n
punch a[i]; // this converts a[i] to 0
int p1= maxPunch(a, i+1, n);
int p2= maxPunch(a, 1, i-1)
int totalPunch= p1+p2+1;
if (totalPunch > max)
max=totalPunch
}
I missed a point. After punch a[i] add the following statements:
a[i-1]-=1; a[i+1]-=1;
and after if statement roll back the changes:
a[i-1]+=1; a[i+1]+=1;
I missed a point. After punch a[i] add the following statements:
a[i-1]-=1; a[i+1]-=1;
and after if statement roll back the changes:
a[i-1]+=1; a[i+1]+=1;
@jobseeker Thanks for your comment, I m still working on the proof but according to my approximation the max punches would be calculated at maximum of 6-9 passes/iteration (could be wrong).
I had a look at your algo and have few suggestions to improve it :-
1) For your algo selecting the pivot index is very critical for optimal performance. If a index having a higher resistance is chosen it would degrade the performance of the algo,
2) Also while selecting the pivot index we have to ensure that the pivot index should contain value > 0 other wise the calculation of punches would be inaccurate.
Ex. if a[i]=0, then while breaking up the array, the statement totalPunch= p1+p2+1 would add an extra punch
Looking forward for your thoughts.
@dv Thank you for your reply. Yes you are right. I should check if a[i]=0 or not. Actually the above algorithm just describes my idea and it is not accurate. For example before decreasing a[i-1] I should ensure that it is greater than 0. And the same for a[i+1].
My algorithm exhaustively checks all possibilities and it does not seem to be the best approach.
And about the greedy approach. I couldn't find an example that shows that it is incorrect. The only important thing is always finding the most left or most right minimum. For example if the array is 1 2 1 1 we should select either the first 1 or the last 1 .
Have you taken a look at my solution at all? It's basically this same approach, but using dynamic programming to reduce the complexity from n! to n^3.
@ eugene.yarovoi Yes, you are right. My solution is similar to your's but your's is better. I don't know how I didn't see that. How can I remove my post?
O(n) code. does this fail for any test case?
#include<stdio.h>
#include<string.h>
int all_values(int *weights, int start, int end,int val)
{
while(start<=end)
{
if(weights[start]!=val)
{
return 0;
}
start++;
}
return 1;
}
int count_no_of_zeroes(int * weights, int size)
{
int count=0,i;
for(i=0;i<size;i++)
if(weights[i]==0)
count++;
return count;
}
int count_no_of_patterns(int * weights, int size) // returns no. of patterns 122...221
{
int prev=-1,i=0, count=0;
while(i<size)
{
//printf("\ni=%d",i);
if(weights[i]==0)
{
prev=-1;
i++;
}
if(weights[i]==1)
{
if(prev!=-1)
{
if(all_values(weights,prev+1,i-1,2))
{
count++;
i++;
prev=-1;
}
else
{
i++;
}
}
else
{
prev=i;
i++;
}
}
else
{
i++;
}
}
return count;
}
int max_punches_possible(int * weights, int size)
{
int punch, no_of_zeroes, no_of_patterns;
no_of_zeroes=count_no_of_zeroes(weights, size);
no_of_patterns=count_no_of_patterns(weights, size);
//printf("\n%d %d", no_of_zeroes, no_of_patterns);
punch=size-no_of_zeroes-no_of_patterns;
return punch;
}
int main()
{
int n,i,ans;
char a[50];
gets(a);
n=strlen(a);
int b[n];
for(i=0;i<n;i++)
{b[i]=a[i]-'0';}
ans=max_punches_possible(b,n);
printf("%d\n",ans);
//getch();
return 0;
}
Think of each punch as partitioning the line into disjoint segments that cannot affect each other. That is, if I have 2, 3, 1, 2, 2, 1 and I punch the first "1", I will have 2, 2, 0, 1, 2, 1, which can be thought of as the sum of the answers to 2, 2 and 1, 2, 1. Therefore, F(sequence)= max over all i ( F(part of sequence indexed from 0 to i-1) + F(part of sequence indexed from i+1 to end) ). So, this is recursion. Each call to F(i, j) decomposes to a maximum of O(n) calls to F. We just have to remember that both bags on each end are damaged by 1, unless i = 0 or j = originalLength-1. We can use dynamic programming to avoid computing each value more than once. Since there are O(n^2) pairs of arguments (i, j) and each call takes O(n) time to evaluate, this algorithm is O(n^3). That should be sufficient if n < 100.
- eugene.yarovoi April 15, 2012I'd like to see more efficient algorithms, if anyone can propose one.