Amazon Interview Question
Software Engineer / DevelopersCountry: United States
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) {
partitions.add(prefix);
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);
}
}
}
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();
newList.add(i);
findSum(num-i, newList, set);
}
Sorry, found two bugs:
1. should be if num == 1 || num < 0, return;
2. after print the list, a return statement should be added.
#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;
}
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);
}
}
}}}
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;
}
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)))
Its a variation on integer partition:
- CameronWills November 12, 2012en.wikipedia.org/wiki/Partition_(number_theory)
And code to generate partitions here:
chinmaylokesh.wordpress.com/2011/01/26/partition-number-theory-ferrers-diagram/