## Amazon Interview Question for Software Engineer / Developers

• 0

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

No need to make array copy:

``````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;

for(int i = index;i>=1;i--){
if(sum - i >= 0){
a[arrayIndex] = i;
generateSeq(a, 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 ,

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

<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>

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

Can you explain the logic

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

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

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

The earlier code does not give any duplicates..u can check it out..if u want...

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

yes it does...i checked

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

pardon above call is Split(a,n-i,1,m)...

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

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

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

Saimok . does the above code even compile?

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

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;
}

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

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

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();
}
}``````

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

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);
}
}
}

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

public void Permute(int n, int m, int arr[])
{
if(m==1)
{
arr[m-1] = n;
print(arr); // Print whole array //
}
else
{
for(int i =(n-m+1); i>=(n-m+2)/2; i--)
{
arr[m-1]=i;
permute(n-i,m-1,arr);
}
}
}

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

The next element can be greater than or equal to the previous

PrintPartition(arr,N,M,pos,prev,sum)
{
if sum=N and pos=M then print
if pos=M return
Start from position 1 in array.
Loop from i=prev to N-M+1
{
arr[pos]=i;
PrintPartition(arr,N,M,pos+1,i,sum+i);
}
}

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

My solution would be applying a Greedy algorithm.
If n = 10. We should consider all numbers less than 10.
Every number should be added to sum in each recursive state. If Sum = 10, Store the list; If exceeded just return; If less than sum keep on the recursive process.

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

``````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 ,

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.