Amazon Interview Question for Software Engineer / Developers


Country: India
Interview Type: Phone Interview




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

Refer: Subset_sum_problem on wiki

- ashwanilabs January 03, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
1
of 1 vote

this problem can be solved with recursion. here are the codes
import java.util.ArrayList;
import java.util.Arrays;

public class Test {

public static void main(String[] args){
int[] theArray={1,2,4,5,6,1,2,4,3,5,7,2,1};
ArrayList<ArrayList<Integer>> allpairs=getPairs(theArray,0,4);
System.out.println(allpairs.size());
for(ArrayList<Integer> pair:allpairs){
System.out.println(Arrays.toString(pair.toArray()));
}
}

public static ArrayList<ArrayList<Integer>> getPairs(int[] theArray, int start, int sum){

if(sum==0){
ArrayList<ArrayList<Integer>> pairs=new ArrayList<ArrayList<Integer>>();
ArrayList<Integer> pair=new ArrayList<Integer>();
pairs.add(pair);
return pairs;
}

if(start>=theArray.length){
return null;
}

ArrayList<ArrayList<Integer>> pairs=new ArrayList<ArrayList<Integer>>();
//situation 1 include the start element;
ArrayList<ArrayList<Integer>> subpairs=getPairs(theArray,start+1,sum-theArray[start]);
if(subpairs!=null){
for(ArrayList<Integer> subpair:subpairs){
ArrayList<Integer> pair=new ArrayList<Integer>();
if(pair!=null){
pair.add(theArray[start]);
pair.addAll(subpair);
pairs.add(pair);
}
}
}

//situation 2 do not include the start element;
ArrayList<ArrayList<Integer>> otherpairs=getPairs(theArray,start+1,sum);
if(otherpairs!=null){
for(ArrayList<Integer> otherpair:otherpairs){
pairs.add(otherpair);
}
}
return pairs;

}
}

- alpha (Xiaolin Xie) January 04, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

A "Pair" always contain 2 elements. I am not sure whether you want the set of all pairs (pairs of 2 elements ofcourse) or you want the set of sets (may contain 2 or more elements). Because the solution of first case i.e., finding pairs that sum up to a certain value is trivial and this problem can be solved in O(n^2). In fact it can be solved in O(n) using hash table.

- Apurva January 03, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

Yes. Any pair.
- It's standard sub set sum problem. You can find in google. but I need software implementation.

- amitnagar21 January 03, 2012 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

Can you please explain how will you solve this problem using hash table

- Suman January 03, 2012 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

@Suman: Use elements in the array as keys. In first pass, for all the keys, set value = 1 (or you may increment this value if you encounter the same no. again in the array). In the second pass for each element 'elt' in array check whether there exists a value for key = (sum-elt). If there is one value then output 'elt' and "sum-elt" else move ahead. A little care must be taken in case of duplicates, still the logic remains the same. However, as I have mentioned above, this solution is good only if we want pairs of 2 elements. If we want a subset whose sum is equal to given value, we'll have to use dynamic programming.

- Apurva January 03, 2012 | Flag
Comment hidden because of low score. Click to expand.
0
of 2 vote

hey..i can tell u the logic that works out for o(n) complexity..

and also assumption here is that pair of 2 elements((1,2)(0,3)..) is the output and input array is sorted

-->take two pointers where one starts from the beginning and other starts from the last element of the array
--> check sum of first and last pointers pointing elements sum if it is equal then print pair of element
--> else move the first pointer to next element and repeat the second statement

and here if u find the sum in the second statement then move the last pointer towards the first pointer and repeat the logic

hope this helps and this algorithm complexity is o(n)

- shivacherukuri January 03, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

It's not only 2 pair, Need to find n number of pairs whose sum is target integer.
Example { 1,1,2}, {3,0,1} etc

- amitnagar21 January 03, 2012 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

int a,b,c;
      a=0;b=1;c=1;
    //for n>=3
   for(int i=3;i<=n;i++)
  { 
    c = a+b;
    a=b;
    b=c;
   a%=1000000;
   b%=1000000;
   c%=1000000;
  }
  return c;

- Dad January 03, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 2 vote

if in output looking more than 2 elements(sets) then

- create a[2][3] array
- scan the integer array (only one pass is required) to get all 1,2 and 3 in integer array(input array). Set a[0][1],a[1][1] and a[2][1] to respective number of 1, 2 and 3 in input array.
- Do while loop for a[2][3] array.
if (a[2][1]>0 && a[0][1] >0) /* To print {3,1}*/
{
print(3,1);
--a[2][1];
--a[0][1];
}

if (a[1][1]>0 && a[0][1] >0) /* To print {1,2,1}*/
{
print(1,2,1);
--a[1][1];
a[0][1] = a[0][1] -2;
}
if (a[1][1]>1 ) /* To print {2,2}*/
{
print(2,2);
a[1][1] = a[1][1] -2;
}
if (a[0][1]>1 ) /* To print {1,1,1,1}*/
{
print(1,1,1,1);
a[0][1] = a[0][1] -4;
}

- Anonymous January 03, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

Great answer!
Thanks.

- Jason Fried January 04, 2012 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

This will fail if input is {1,2,4,5,6,2,2,4,3,5,7,2,2} ie 1,2,1 case is still printed while it is not possible. BUG! You should rather compare the number of occurences of the numbers. I have tried to correct it somewhat.
Also, you always use a[][1] so i guess you dont need a 2d array!
Further, you dont need to decrement the a[].
I believe it should be:

int num[] =  {1,2,4,5,6,2,2,4,3,5,7,2,2};
int a[3]={0,0,0};
int i;
for(i=0; i<13; i++)	{
	if(num[i]<4 && num[i]>0)	
		a[num[i]-1]=a[num[i]-1]+1;

if (a[2] >0 && a[0]  >0) /* To print {3,1}*/
     printf("\n3,1"); 

if (a[1] >0 && a[0]  >1) /* To print {1,2,1}*/
     printf("\n1,2,1"); 
 if (a [1]>1 ) /* To print {2,2}*/
     printf("\n2,2"); 
 if (a[0] >3 ) /* To print {1,1,1,1}*/
     printf("\n1,1,1,1");

- abhityagi85 January 04, 2012 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

Good catch, thnx.

- Jason Fried January 04, 2012 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

this answer doesn't match the expectation of this program well. This is a N-Subset problem, the number can be used repeatedly in different sub-sets.
Say,
input : {1,2,4,5,6,1,2,4,3,5,7,2,1} only three '2'
output : {1,1,2}, {2,2}, {3,1}, {1,2,1}... with four '2'.
I have a stupid solution, just calculate all the possible combinations first, then just track each possibility if this combination can be fulfilled.

- Haojian.Jin January 04, 2012 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

@Haojian Jin
Agree. Just tried to improve the above code even i did smell bad in the very begining

- abhityagi85 January 05, 2012 | Flag
Comment hidden because of low score. Click to expand.
0
of 2 vote

This comment has been deleted.

- Administrator January 03, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

As far as I know, this problem is one of the well known NP-Complete problems named "Subset-Sum", how can you solve it in O(NlgN). Note that the question does not only ask about tuples, it is a different problem which can be solved using the binary search logic.

- Emrah January 03, 2012 | Flag
Comment hidden because of low score. Click to expand.
-1
of 1 vote

Looks like somebody changed the question itself... :)
My solution is for different question

- loveCoding January 03, 2012 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

This is a well known NP complete problem. I think that is what the interviewer was expecting you to know. This problem does not have a linear time solution.

- Sushant January 04, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

This could be a Dynamic Programing problem. Or it is a memorization problem?

- gowtham.n.mail January 04, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

Below is a program, I have written in C# that will solve this in exponential time (brute force through recursion). It would be helpful, if someone could think of how to memonize it:


// Wrapper around SubsetSum method
public static void SubsetSum(int[] arr, int sum)
{
SubsetSum(arr, 0, 0, sum, new Stack<int>());
}

private static void SubsetSum(int[] arr, int i, int sumSoFar, int sum, Stack<int> parts)
{
if (sumSoFar == sum)
{
while (parts.Count > 0)
Console.Write(parts.Pop().ToString() + ", ");
Console.WriteLine();
return;
}
if (i >= arr.Length) return;

Stack<int> allParts = new Stack<int>(parts);
allParts.Push(arr[i]);
SubsetSum(arr, i + 1, sumSoFar + arr[i], sum, allParts);
if (allParts.Count > 0) allParts.Pop();
SubsetSum(arr, i + 1, sumSoFar, sum, allParts);
}

- Anonymous January 04, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

I would say we can sort this array first, taking 4 as center node, anything less than 4 we can keep in left side, in this way all the lesser number than 4 will come in one side and then we can easily pick up and make combination of 4.. hope it helps.

- manikesh.verma January 05, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

#include <cstring>
#include <cstdlib>
#include <cstdio>
#include <bitset>
#incluce <vector>
int* sequence;
bool* flag;
int n;
void getPermutaion(vector<int> & array, int sum, int part_sum, int d)
{
if (part_sum> sum)
return;
if (part_sum ==sum)
{
if (d==0)
return;
printf("{");
for (int i=0;i<d-1;i++)
{
printf("%d,"sequence[i]);
}
printf("%d}\n", sequence[d-1]);
return;
}
for (int i=0;i<n;i++)
{
if (!flag[i])
{
flag[i] =true;
sequence[d] =array[i]
getPermutaion(sum, part_sum + array[i], d+1);
flag[i] =false;
}
}
}
void solve(vector<int> & array, int sum)
{
sequence =new int[array.size()];
n =array.size();
free(sequence);
}

- bo hou January 11, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

function subset_sum($input, $sum, $included=array()) {
        if (count($input) == 0) {
                return ($sum == 0) ?
                                array("{" . implode(",", $included) . "}") :
                                array();
        } else {
                $elem = array_pop($input);
                $solutions_without_elem = subset_sum($input, $sum, $included);
                array_push($included, $elem);
                $solutions_with_elem = subset_sum($input, $sum - $elem, $included);
                return array_merge($solutions_with_elem, $solutions_without_elem);
        }
}

print implode(", ", subset_sum(array(1,2,4,5,6,1,2,4,3,5,7,2,1), 4)) . "\n";

- Chad Parry November 29, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

<?php
$want = 7;
$arr = array (
1,
2,
4,
5,
6,
1,
2,
4,
3,
5,
7,
2,
1
);
sort ( $arr );
$result = array ();
for($j = 0; $j < count ( $arr ); $j ++)
for($n = 0; $n < count ( $arr ); $n ++) {
$part = array_slice ( $arr, $j, $n + 1 );
// var_dump($part);echo '<br>';
$sum = array_sum ( $part );
// echo $sum.'<br>';
if (in_array ( $want - $sum, $arr ) && in_array ( $want - $sum, array_diff_assoc ( $arr, $part ) )) {
array_push ( $part, ($want - $sum) );
sort ( $part );
$result [] = implode ( ',', $part );
}
}
foreach ( array_unique ( $result ) as $value ) {
echo $value . '<br>';
}

- Wayne October 25, 2013 | Flag Reply
Comment hidden because of low score. Click to expand.
-1
of 3 vote

<REMOVED>

- V.Krestyannikov January 03, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

<REMOVED>

- V.Krestyannikov January 03, 2012 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

<REMOVED>

- V.Krestyannikov January 03, 2012 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

<REMOVED>

- V.Krestyannikov January 03, 2012 | Flag
Comment hidden because of low score. Click to expand.
-1
of 3 vote

<REMOVED>

- V.Krestyannikov January 03, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

<REMOVED>

- V.Krestyannikov January 03, 2012 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

<REMOVED>

- V.Krestyannikov January 03, 2012 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

Could you just explain the algo with example given in the question?

Thanks

- Anonymous January 04, 2012 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

what the fish is this? Totally unrelated to the problem.

- Anonymous January 04, 2012 | Flag
Comment hidden because of low score. Click to expand.
-1
of 1 vote

public static int LSBFibbonacci(int n){
		if(n <= 1)
			return n;
		int a1 = 1;
		int a2 = 1;
		int res = 1; 
		for(int i=3;i<=n;i++){
			res = (a1 + a2)%1000000;
			a1 = a2 % 1000000;
			a2 = res % 1000000;
		}
		return res;
		
	}

- loveCoding January 03, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

@Manan.
Can you pleas remove your solution?
Something went wrong, seeing as the question itself has been changed for some weird reason.

- Jason Fried January 12, 2012 | Flag
Comment hidden because of low score. Click to expand.
-1
of 3 vote

<SPAM>

- Jason Fried January 04, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
-1
of 1 vote

import java.util.ArrayList;
import java.util.Arrays;

public class Test {

	public static void main(String[] args){
		int[] theArray={1,2,4,5,6,1,2,4,3,5,7,2,1};
		ArrayList<ArrayList<Integer>>  allpairs=getPairs(theArray,0,4);
		System.out.println(allpairs.size());
		for(ArrayList<Integer> pair:allpairs){
			System.out.println(Arrays.toString(pair.toArray()));
		}
	}
	
	public static ArrayList<ArrayList<Integer>> getPairs(int[] theArray, int start, int sum){
		
		if(sum==0){
			ArrayList<ArrayList<Integer>> pairs=new ArrayList<ArrayList<Integer>>();
			ArrayList<Integer> pair=new ArrayList<Integer>();
			pairs.add(pair);
			return pairs;
		}
		
		if(start>=theArray.length){
			return null;
		}
		
		ArrayList<ArrayList<Integer>> pairs=new ArrayList<ArrayList<Integer>>();
		//situation 1 include the start element;
		ArrayList<ArrayList<Integer>> subpairs=getPairs(theArray,start+1,sum-theArray[start]);
		if(subpairs!=null){
			for(ArrayList<Integer> subpair:subpairs){
				ArrayList<Integer> pair=new ArrayList<Integer>();
				if(pair!=null){
					pair.add(theArray[start]);
					pair.addAll(subpair);
					pairs.add(pair);
				}
			}
		}
		
		//situation 2 do not include the start element;
		ArrayList<ArrayList<Integer>> otherpairs=getPairs(theArray,start+1,sum);
		if(otherpairs!=null){
			for(ArrayList<Integer> otherpair:otherpairs){
				pairs.add(otherpair);
			}
		}
		return pairs;
		
	}
}

- alpha(Xiaolin Xie) January 04, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
-1
of 1 vote

public static HashSet<ArrayList<Integer>> getSumPairs(int [] arr, int num)  {
		HashSet<ArrayList<Integer>> combination = new HashSet<ArrayList<Integer>>();
		for (int i = 0; i < arr.length; ++i) {
			ArrayList<Integer> combo = new ArrayList<Integer>();
			int sum = arr[i];
			combo.add(arr[i]);
			for (int j = 0; j < arr.length; ++j) {
				if (i == j) {
					continue;
				}
				int localSum = sum + arr[j];
				if (localSum < num) {
					combo.add(arr[j]);
					sum = localSum;
				} else if (localSum == num) {
					combo.add(arr[j]);
					combination.add(combo);
					combo = new ArrayList<Integer>();
					combo.add(arr[i]);
					sum = arr[i];
				}
			}
		}
		return combination;
	}

- donsem January 05, 2012 | Flag Reply


Add a Comment
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.

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