Amazon Interview Question Software Engineer / Developers

  • amazon-interview-questions
    0
    of 0 votes
    20
    Answers

    Given an integer (assume it's smaller than 50), write an algorithm that will generate all possible combinations of integers greater than 1 and they produce a sum equals to this number. The same number can appear more than once in a combination. What's the time complexity of your algorithm?

    For example:
    <=1 -> {}
    2 -> {2},
    3->{3},
    4->{[4], [2, 2]},
    5->{[5], [3, 2]},
    6->{[6], [4, 2], [3, 3], [2, 2, 2]}
    7->{[7], [5, 2], [4, 3], [3, 2, 2]}
    8->{[8], [6, 2], [5, 3], [4, 4], [4, 2, 2], [3, 3, 2], [2, 2, 2, 2]}
    ....

    - chriscareercup on November 12, 2012 in United States Report Duplicate | Flag
    Amazon Software Engineer / Developer Algorithm

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/

- CameronWills on November 12, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

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

}

- chriscareercup on November 12, 2012 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

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

- bharat on November 19, 2012 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

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

- George on November 30, 2012 | Flag
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();
newList.add(i);
findSum(num-i, newList, set);
}

- Anonymous on November 12, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

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

- Anonymous on November 12, 2012 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

I've added clarification to the question, please check again.

- chriscareercup on November 12, 2012 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

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

- Anonymous on November 12, 2012 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

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.

- eugene.yarovoi on November 13, 2012 | Flag
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;
}

- charsyam on November 12, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

I've added clarification to the question, please check again.

- chriscareercup on November 12, 2012 | Flag
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] }

- belligerentCoder on November 12, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

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

- chriscareercup on November 12, 2012 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

maybe to solve it , I think we need DP.

- charsyam on November 12, 2012 | Flag Reply
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);

}

}

}}}

- Arunkumar Somalinga on November 12, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

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

- chriscareercup on November 12, 2012 | Flag
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;
}

- charsyam on November 12, 2012 | Flag Reply
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)))

- arw on November 13, 2012 | Flag Reply
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);
	}
}

- Anonymous on November 30, 2012 | Flag Reply
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)

- tester on December 05, 2012 | Flag Reply


Add a Comment
Name:

Writing Code? Surround your code with {{{ and }}} to preserve whitespace.

Books

is a comprehensive book walking you through getting a job at a top tech company, while focuses on dev interviews and does this for PMs.

Learn More

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.

Learn More

Resume Review

Most engineers make critical mistakes on their resumes -- we can fix your resume with our custom resume review service. And, we use fellow engineers as our resume reviewers, so you can be sure that we "get" what you're saying.

Learn More

Mock Interviews

Our Mock Interviews will be conducted "in character" just like a real interview, and can focus on whatever topics you want. All our interviewers have worked for Microsoft, Google or Amazon, you know you'll get a true-to-life experience.

Learn More