Amazon Interview Question
Software Engineer / Developers<pre lang="" line="1" title="CodeMonkey82183" class="run-this">/*C++ code*/
#include<iostream>
using namespace std;
void generate(int sum,int count,int* b,int l,int y)
{
if(count==1)
{
b[l]=sum;
for(int i=0;i<=l;i++)cout<<b[i]<<" ";
cout<<endl;return;
}
for(int i=y;i<=sum-count+1;i++)
{
b[l]=i;generate(sum-i,count-1,b,l+1,i);
}
return;
}
int main()
{
int* b=NULL;
int sum,count;
cin>>sum>>count;
b=new int[count];
generate(sum,count,b,0,1);
delete [] b;
}
</pre><pre title="CodeMonkey82183" input="yes">10 4</pre>
The above code throws duplicates.BTW here is the logic which should get u right ans
Below is the function
it accepts 4 args an array whose size is m,req is the n,pos is the current pos which is to be filled,tot is m
Split(int[] a,int req,int pos,int tot){
if pos==tot-1//ie last item to be filled
if req<=a[pos-1]//this is required to remove duplicates
a[pos]=req
print a
else{
int k=minimum((req+pos-tot+1),a[pos-1])//again required to remove dups
for (k;k>0;k--){
a[pos]=k
Split(a,req-a[pos],pos+1,tot);
}
}
}
above fn shall b called by
for (i=n-m+1;i>0;i--)
a[0]=k;
Split(a,n-i,1,j);
It turns out that for eg to fill 10 in 4 places maximum no: in a slot can be 7...which is this piece req+pos-tot+1...I m calculating the minimum fn so the series never increases avoiding dups...If this is not done u will get 2 o/ps say 5311 and 3511 which are the same
Another JAVA alternative. This solution is derived from solving a concrete example. When do you one you can observe 2 rules; 1) the ith element <= the i-1th element (to avoid duplicate) 2) when residue < number of available slot --> don't waste your time.
public static void main(String args[]){
int sum = 10;
partition = 4;
int[] array = new int[partition];
partitionImpl(array,0,sum,sum);
}
private static void print_array(int arr[]){
/* You know how to do it */
}
private static void partitionImpl(int[] array, int pos, int residue,int upBound){
//base case...
if(pos == partition){
if(residue == 0) print_array(array);
}else{
//recursive case
for(int i=residue-(partition-pos-1);i>0;i--) //rule#2 residue >= blank position
{
//rule#1 the ith element <= its previous element
if(i <= upBound){
array[pos] = i;
partitionImpl(array,pos+1,residue-i,i);
}//endif
}//endfor
}//endif
}//end method
Brief info
I printed the values in non-decreasing order.. It avoids duplicate value..
-----------------------
#include<stdio.h>
#define NUMOFPART 3
#define PSIZE 7
void print(int *arr, int s)
{
int i=0;
for(i=0;i<NUMOFPART;++i)
{printf("%d",arr[i]);}
printf("\n");
}
void partition(int size, int numofpart, int *arr,int startval, int startindex)
{
if(numofpart == 1)
{
arr[startindex] = size;
print(arr,numofpart);
return;
}
int val=startval;
for(val=startval;val<=size/numofpart;++val)
{
arr[startindex] = val;
partition(size-val,numofpart-1,arr,val,startindex+1);
}
}
int main()
{
int arr_val[NUMOFPART];
partition(PSIZE,NUMOFPART,arr_val,1,0);
return 0;
}
similar to above methods...hopefully easier to understand?
the idea is to store the elements of partition in a vector and sum of the partition so far in sum. to avoid permutations of the same partition, we make sure to add elements that are atleast as big as the biggest number in the partition so far.
start the algorithm with empty partition and sum=0;
Partition(int n, int m, vector<int> part, int sum)
{
if(part.size() == m)
{
if(sum == n) print(part);
return;
}
// part.back() returns the max element of the partition
// initially when partition is empty we start with 1
int minval = part.size() > 0 ? part.back() : 1;
for(int i=minval; sum+i <= n; i++)
{
part.push_back(i);
Partition(n,m,part,sum+i);
part.pop_back();
}
}
public void printPar(int n, int m, int pos, int array[]){
if(pos == array.length) System.out.println(Arrays.toString(array));
else {
for(int i=0;i<=n-m-n/m+1;++i){
array[pos] = n-m-i+1;
if(pos>0){
if(array[pos] <= array[pos-1])
printPar(n-array[pos],m-1,pos+1,array);
else continue;
} else printPar(n-array[pos],m-1,pos+1,array);
}
}
}
package recursion;
import java.util.Arrays;
/**
* N = 10 M = 4
* Output: 7 1 1 1, 6 2 1 1, 5 3 1 1,...
* @author Gopal
*
*/
public class GenerateUniquePartition {
private static int Array_Length;
public static void generateSeq(int n,int m){
Array_Length = m;
generateSeq(new int[m],n,0,n-1);
}
private static void generateSeq(int[] a,int sum,int arrayIndex,int index){
if(arrayIndex == Array_Length && sum == 0){
for(int i: a){
System.out.print(i + " ");
}
System.out.print(" , ");
return;
}
if(arrayIndex == Array_Length)
return;
int[] temp;
for(int i = index;i>=1;i--){
if(sum - i >= 0){
temp = Arrays.copyOf(a,Array_Length);
temp[arrayIndex] = i;
generateSeq(temp, sum - i, arrayIndex + 1,i);
}
}
}
public static void main(String[] args){
generateSeq(10,4);
}
}
Output: 7 1 1 1 ,6 2 1 1 ,5 3 1 1 ,5 2 2 1 ,4 4 1 1 ,4 3 2 1 ,4 2 2 2 ,3 3 3 1 ,3 3 2 2 ,
No need to make array copy:
Output: 7 1 1 1 ,6 2 1 1 ,5 3 1 1 ,5 2 2 1 ,4 4 1 1 ,4 3 2 1 ,4 2 2 2 ,3 3 3 1 ,3 3 2 2 ,
- Anonymous March 10, 2011