## Amazon Interview Question for Software Engineer / Developers

Country: United States

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

Its a variation on integer partition:
en.wikipedia.org/wiki/Partition_(number_theory)

And code to generate partitions here:
chinmaylokesh.wordpress.com/2011/01/26/partition-number-theory-ferrers-diagram/

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

``````public class Partition {
public static List<String> partition(int n) {
List<String> partitions = new ArrayList<String>();
partition(n, n, "", partitions);
return partitions;
}

public static void partition(int n, int max, String prefix, List<String> partitions) {
if (n == 0) {
return;
}

for (int i = Math.min(max, n); i > 1; i--) {
partition(n-i, i, prefix + " " + i, partitions);
}
}

public static void main(String[] args) {
for(String partition: partition(7)){
System.out.println(partition);
}
}``````

}

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

@chriscareercup : r u taking care of duplicates ? I mean [5,3] and [3,5 ].

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

Yes, by inducing an ordering on the sequences. Note the max argument in the partition function.

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

public void findSum(int num, ArrayList<Integer> list, HashSet<HashMap<Integer, Integer>> set)
1. If num == 1, return
2. If num == 0, build a hashmap which records each number in list and its corresponding frequency. If this map is contained in set, return; else add the map into the set, and print each element of the list
3. for(int i = 2; i <= num; ++i)
{
ArrayList<Integer> newList = (ArrayList<Integer>) list.clone();
findSum(num-i, newList, set);
}

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

Sorry, found two bugs:
1. should be if num == 1 || num < 0, return;
2. after print the list, a return statement should be added.

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

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

I think it works. The time complexity is O(n^2), where n is the given number.

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

I think the number of partitions of a number is at least exponential in the size of the number. An O(n^2) runtime won't be possible, since you have an exponential amount of printouts to do.

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

``````#include <stdio.h>
#include <iostream>

using namespace std;

int cont(int k){
int j = k/2;
if( k%2 == 0 ){
j = k/2-1;
}

return j;
}

int main( int argc, char *argv[] )
{
int j;
cin >> j;

if( j == 2 || j == 3 ){
printf("K: {%d}\n", j);
return 0;
}

int t = cont(j);
for( int k = j; k >= 2 && k > t; k-- ){
if( k == j ){
printf("K: {%d}\n", j);
} else {
if( j-k > 1 )
printf("K: {%d,%d}\n", j-k, k );
}
}

return 0;
}``````

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

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

Just to clarify the question,

shouldn't 6 be,
6 --> { [6], [4,2], [3,3], [2,2,2] }

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

Absolutely, thanks for spotting it. I've updated the question.

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

maybe to solve it , I think we need DP.

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

Here is a recursive solution in java..i checked the solution till 8
public class combinations {

/**
* @param args
*/
int findcomb(int n)
{
if(n==0)
return 0;
for(int i=2;i<=n;i++)
{
if((n-i)>1||(n-i)==0)
{
System.out.print(i+" ");
findcomb(n-i);

}

}
System.out.println("\n");
return 0;
}
public static void main(String[] args) {
// TODO Auto-generated method stub
combinations x=new combinations();
x.findcomb(12);

}

}

}}}

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

Your algorithm is basically Fibonacci, you have completely ignored the data structure to store the results and de-duplication.

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

somewhat strange solution but it works. just using combination. not DP
not elegant.

``````#include <stdio.h>
#include <iostream>

using namespace std;

void print_array( int *b, int q, int sum ){
int tmp = 0;
for( int i = q-1; i >= 0; i-- )
{
tmp += b[i];
}

if( tmp == sum ) {
printf("[");
for( int i = q-1; i >= 0; i-- )
{
printf("%d ", b[i]);
}
printf("]\n");
}
}

void H_combi( int *a, int *b, int n, int r, int q, int sum )
{
if( r == 0 )
print_array(b, q, sum);
else if( n == 0 )
return;
else
{
if( a[n-1] == 0 ){
printf("n: %d, r: %d\n", n, r );
}

b[r-1] = a[n-1];
H_combi( a, b, n, r-1, q, sum );
H_combi( a, b, n-1, r, q, sum );
}
}

int main( int argc, char *argv[] ){
int num;
cin >> num;

if( num < 2 ){
return 0;
}

if( num == 2 || num == 3 ){
printf("[%d]\n", num);
return 0;
}

int maxsize = num / 2;
printf("[%d]\n", num);
for( int i = 2; i <= maxsize; i++ ){
int limit = num - (i-1)*2;
int *k = new int[limit-1];
for( int j = 2; j <= limit; j++ ){
k[j-2] = j;
}
int *r = new int[i];
H_combi( k, r, limit-1, i, i, num );
}
return 0;
}``````

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

``````def partitions(n):
if n<1:
yield ()
else:
for p in partitions1(n,n):
yield p

def partitions1(n,m):
#print "p1", (n,m)
assert m<=n
if n<1:
yield ()
else:
for i in range(1,m+1):
rem = n-i
m2 = min(i, rem)
for p in partitions1(rem, m2):
yield (i,)+p

def tp(n):
print ":::", n
for p in partitions(n):
print p

for i in range(7):
tp(i)
print
for i in range(35):
print i, len(list(partitions(i)))``````

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

``````public class a {
static void print(int i,String prefix,int min){
System.out.println(prefix +i);
if(min==0)	min=2;
for(int j=min;j<=(i-j);j++)
print(i-j,prefix+j,j);
}

public static void main(String[] args) {
print(18,"",0);
}
}``````

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

``````def gensum_helper(s,t):
if t<=0:
yield [s]
else:
for i in range(s,t+1):
for j in gensum_helper(i,t-i):
yield [s] + j

def gensum(n):
for i in range(1,n+1):
for j in gensum_helper(i,n-i):
yield j

#test
for i in gensum(8):
print(i)``````

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.