Amazon Interview Question for SDE-2s


Country: India
Interview Type: In-Person




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

It's an NP-complete problem to decide the language of SUBSET-SUM.

- dabuja December 08, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

Thank you for being the first answer here to even understand the question. Yeah, you're pretty much forced to use an exponential algorithm unless you can say something about the largest possible sum, in which case you could also consider the pseudopolynomial subset-sum DP algorithm.

- Anonymous December 10, 2014 | Flag
Comment hidden because of low score. Click to expand.
1
of 1 vote

Hi,
I understand from the description of the problem that we need to return the first
integer that is not possible to obtain by summing different elements in the array;
I suppose that this integer must be at least larger than the smallest element in the
array, otherwise the solution will be just return 1 if the minimum element is larger
than 1. Also, I assume this number cannot be a number contained in the array.

Example 1:
Input array: [3, 2, 2, 2, 9]
Minimum int that is not sum: 8

Example 2:
Input array: [6, 1, 2, 7, 5]
Minimum int that is not sum: 4

Example 3:
Input array: [1, 2, 3, 2]
Minimum int that is not sum: 9

Example 4:
Input array: [8, 9, 3, 1, 1]
Minimum int that is not sum: 6

Example 5:
Input array: [2, 3, 4, 5, 8]
Minimum int that is not sum: 21

To obtain the minimum integer that cannot be formed from the sum of numbers of the array
I generate the powerset of the elements in the array, than compute the sum for each powerset
excluding the empty set; finally I scan the set of the sums of every set in the powerset,
and the minimum int that is not formed by the sum of the element of the array will be the first
missing int in the set of sums (ordered using a TreeSet). If no element is missing in the sequence
the minimum int that cannot be formed will be the maximum sum plus 1;

The time complexity will be O(2^n), time needed to compute all the sets in the powerset.

Here is my code, you can use genList(int n, int range) to generate a random list of n numbers
between 1 and range; int minNotSum(List<Integer> l) will retrieve the minimum number not formed by a sum,
Set<List<Integer>> powerSet(List<Integer> originalSet) computes the powerSet,
Set<Integer> sums(Set<List<Integer>> sets) computes the set of all the possible sums,
int computeSum(List<Integer> l) compute the sum of a single list:

import java.util.*;

public class MinIntNotSum {
	public static Set<List<Integer>> powerSet(List<Integer> originalSet){
		Set<List<Integer>> sets = new HashSet<List<Integer>>();
		if(originalSet.size()==0) {
			sets.add(originalSet);
			return sets;
		}
		int head = originalSet.get(0);
		List<Integer> rest = originalSet.subList(1, originalSet.size());
		for(List<Integer> s: powerSet(rest)) {
			List<Integer> newSet = new ArrayList<Integer>();
			newSet.add(head);
			newSet.addAll(s);
			sets.add(newSet);
			sets.add(s);
		}
		return sets;
	}
	public static List<Integer> genList(int n,int range) {
		List<Integer> l = new ArrayList<Integer>();
		Random r = new Random();
		for(int i=0;i<n;i++) {
			l.add(r.nextInt(range)+1);
		}
		return l;
	}
	public static Set<Integer> sums(Set<List<Integer>> sets) {
		if(sets==null || sets.size()==0) {
			return new TreeSet<Integer>();
		}
		Set<Integer> sums = new TreeSet<Integer>();
		for(List<Integer> l:sets) {
			if(l.size()>0)
				sums.add(computeSum(l));
		}
		return sums;
	}
	public static int computeSum(List<Integer> l) {
		int sum = 0;
		for(Integer i: l) {
			sum+=i;
		} 
		return sum;
	}
	public static int minNotSum(List<Integer> l) {
		if(l==null || l.size()==0) {
			return -1;
		}
		Set<List<Integer>> ps = powerSet(l);
		Set<Integer> sums = sums(ps);
		List<Integer> lsums = new ArrayList<Integer>(sums);
		//System.out.println("List from TreeSet:\n"+lsums);
		for(int i=0;i<lsums.size()-1;i++) {
			if(lsums.get(i)+1!=lsums.get(i+1)) {
				return lsums.get(i)+1;
			}
		}
		return lsums.get(lsums.size()-1)+1;
	}
	public static void main(String[] args) {
		List<Integer> l = genList(5,10);
		/*l = new ArrayList<Integer>();
		l.add(4);
		l.add(4);
		l.add(3);
		l.add(2);
		l.add(4);
		*/
		System.out.println(l);
		/*
		Set<List<Integer>> ps = powerSet(l);
		for(List<Integer> ll: ps) {
			System.out.println(ll);
		}
		System.out.println("Power Sets: "+ps.size());
		*/
		int min = minNotSum(l);
		System.out.println("Min not Sum: "+min);
	}
}

- gigi84 December 08, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
1
of 1 vote

First sort them.

Them calculate cumulative sum.
If some element a[i] is greater than sum + 1 then there is a gap between them. So number sum + 1 cannot be formed - this is the answer.

- glebstepanov1992 December 11, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

I can not upvote this enough, that's precisely it. Easily provable by induction.

- Lenny January 15, 2015 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

what will be your answer for 3,4,6 ? how?

- anamika May 31, 2015 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

first count the sum then check which no is no exists by converting that into string and then check that set's single no contains by which number that number should be the answer.

- Gannu December 07, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

Sort the array and return the minimum element. If there are negative integers in the input array, this won't work. But the question says "Given an array of positive Integers"..

- naren December 07, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
1
of 1 vote

The way the question is worded it does sound like you just need to find the smallest number. So you don't even need to sort the array (O(nlogn). Just find the smallest element (O(n))..

- rizhang December 08, 2014 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

The question is about the SUM of the elements in the array. So if you have an array [1,2,3] you can form sums 1,2,3,5,6 making 4 the sought element, so your answer is wrong

- Anonymous December 08, 2014 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

How exactly [1,2,3] became part of the SUM. If the elements are [1,2,3] then the sums should be [3,4,5] right? There is no missing element?
So, your example may be wrong here.
But with another example [1,3,4] then the SUM could be [4,5,7]. In this example 6 is missing..

- Anonymous December 08, 2014 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

This question is ambiguous. But for the [1,3,4] example, I think the answer should be 2 instead, since 2 isn't in the array nor is it among [4,5,7].

- Sunny December 08, 2014 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

iterate each number at array, let x is a[i], lets do swap(a[x], x) (we should use swap if x less then length of array else continue)
after that lets look throw our array and if a[x] != x return x

int findNumber (vector <int> a) 
{
	for (int i = 0; i < a.size(); i++) {
		int x = a[i];
		if (x > a.size()) continue;
		swap(a[x - 1], x);
	}
	for (int i = 0; i < a.size(); i++) {
		if (a[i] != i + 1) return i + 1;
	}
	return a.size();
}

- Dima December 07, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

find the least two integers and subtract 1 from their sum.

- Anonymous December 08, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

Since elements are positive integers..so find the smallest and subtract 1.

- Anonymous December 08, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

But what if smallest - 1 is zero?

- Anonymous December 09, 2014 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

I don't understand if the question is worded correctly or not, the question says to find "any" smallest positive integer that can not be formed from the sum of numbers from array.

Now let's twist the question a little bit, what is the smallest positive integer ? 0. Is there an array containing only positive integers which can have a sum less than 0 ? No because it needs to have negative numbers then.

So shouldn't the answer always be zero.

- Ashish December 08, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
1
of 1 vote

No. Because 0 is not positive or negative.

- Anonymous December 09, 2014 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

Sort the array and return 0th element from array

- Pradip December 08, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

Given array of positive numbers and Question mentioned to find the smallest positive integer so find the minimum value in the array. If minimum value greater than 1 return 1 else min value.

That means solution is 1 always. Considering 0 as not positive number.

- Anonymous December 08, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

Assuming that the question allows numbers to be used multiple times

You could attempt a brute force search. This search would ultimately be very, very slow because you'd have to effectively decide whether a given number should be in the sum or not. This can also be sped up by using caching of previously computed summations.

public static boolean canBeSummed(int[] arr, int k){
	if(arr == null){
		throw new NullPointerException();
	}
	if(k < 0){
 		throw new IllegalArgumentException();
	}

	HashSet<Integer> cache = new HashSet<Integer>();
	Stack<Integer> stack = new Stack<Integer>();
	stack.put(0);
	cache.add(0);
	while(!stack.isEmpty()){
		int val = stack.pop();
		if(this.cache.contains(k - val){
			return true;
		}
		else{
			for(Integer i : cache){
				int sum = val + i;
				if(sum < this.k){
					if(!this.cache.contains(sum)){
						this.cache.add(sum);
						stack.add(sum);
					}
				}
			}
		}
	}
	return false;
}

If each number can only be used once, then the computation could change significantly. I haven't implemented caching here, but it could potentially be implemented. Complexity is O(2^n):

public static boolean canBeSummed(int[] arr, int k){
	if(arr == null){
		throw new NullPointerException();
	}
	if(k < 0){
		throw new IllegalArgumentException();
	}
	
	Worker worker = new Worker(arr, k);
	return worker.execute();
}

static class Worker{
	int[] arr;
	int k;
	int index;
	int sum;
	
	Worker(int[] arr, int k){
		this.arr = arr;
		this.k = k;
		this.index = 0;
		this.sum = 0;
	}

	boolean execute();
		return executeRecur(0, 0);
	}

	boolean executeRecur(){
		if(this.sum == k){
			return true;
		}
		if(this.index == this.arr.length){
			return false;
		}
		int val = this.arr[this.index];
		this.index++;
		if(executeRecur()){
			return true;
		}
		this.sum += val;
		if(executeRecur()){
			return true;
		}
		this.sum -= val;
		this.index--;
		return false;
	}
}

- zortlord December 08, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

Assuming that "sum of numbers from array" means this positive integer cannot be one of the numbers in the array nor the sum of any of them. Then I am going to create a set that contains all possible sums from the array. If the array has n elements then the set can potentially contain as much as 2^n of them. After that, I will just keep checking which smallest positive integer doesn't exist in this set.

def smallest_missing(arr):
	sums = {0}
	for i in arr:
		sums |= {i+x for x in sums}
	i = 1
	while(i in sums):
		i+=1
	return i

print smallest_missing([1,2,3])

- Sunny December 08, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

The same idea in Ruby, just for contrast.

def smallest_missing(arr)
	sums = Set.new([0])
	for i in arr
		sums += sums.map {|x| x + i}
	end
	i=1
	i+=1 while sums.include?(i)
	return i
end
p smallest_missing([1,2,3])

- Sunny December 08, 2014 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

def find(a):
	sum = 0
	
	for i in range(len(a)):
		sum += a[i]
		 
		if sum < a[i] - 1:
			return sum + 1
	return sum + 1

- glebstepanov1992 December 08, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

This can be solved rather efficiently with dynamic programming.

public int minNotFormable(int[] input) {
	Arrays.sort(input); // O(log n) black-box
	boolean[] memo = new boolean[1000];
	memo[0] = true; 	// base case
	for (int num : input) {
		for (int i = 0; i < memo.length - num; i++) {
			memo[i + num] = true && memo[i];
		}
	}
	// table complete; get the best result out of it
	for (int i = 0; i < memo.length; i++) {
		if (!memo[i]) {
			return i;
		}
	}
	return -1;

The essence of the solution is that we create a memo with some number of boolean variables representing whether we can get to that value. We then iterate through the sorted list and update the memo table accordingly.

We could add a number of heuristics here to make the procedure complete sooner should it be necessary.

- Anonymous December 09, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

We can consider some simple cases.
1. If the smallest number in array is greater than 1 then we can simply report 1 as answer.
2. If this is not the case , then sort the array.
After sorting we can apply more simple cases.
like if our sorted array is
[1 3 4 5] -- so we know that 2 cannot be formed using sum
[1 2 4 9] -- so we know that 8 cannot be formed using sum

so if sum of array A[1- (n-1) ] is smaller than A[n] , then we can report SUM( A[1 - (n-1) ] as answer.

If we complete the complete traversal of array and we could find and answer, we can report SUM(A[1 - n] ) as answer.

- gautamjha.jnu December 09, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

this is a play on words, it's just asking for the smallest number in the array. also, "in the array" is an assumption. If that assumption is false, then the answer is always 1.

- Anonymous December 09, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

Here's the solution with a bit of memory conservation:

private class TempSum
{
    public int Sum;
    public int MaxUsed;

    public TempSum(int sum, int maxUsed)
    {
        Sum = sum;
        MaxUsed = maxUsed;
    }
}

public int ArraySumMinInt(params int[] ar)
{
    Array.Sort(ar);
    int n = ar.Length;
    var queue = new List<TempSum> { new TempSum(0, -1) };
    int seekingFor = 1;
    while (queue.Any())
    {
        var current = queue[0];
        if (current.Sum > seekingFor) return seekingFor;
        queue.RemoveAt(0);
        int j = queue.Count - 1;
        for (int i = n - 1; i > current.MaxUsed; i--)
        {
            var next = new TempSum(current.Sum + ar[i], i);
            while (j >= 0 && queue[j].Sum > next.Sum) j--;
            if (++j < queue.Count) queue.Insert(j--, next);
            else
            {
                queue.Add(next);
                j--;
            }
        }
        seekingFor = current.Sum + 1;
    }
    return seekingFor;
}

The idea is to try to build all possible sums in an increasing way. Each time we take the current smallest sum we add all possible sums, which can be created by adding one of the numbers not used in it (their indices must be greater than the greatest index used before to avoid repeating, that's why the MaxUsed field is introduced). The resulting new sums must be placed in the queue in the way that keeps the queue increasing. I guess this solution has elements of dynamical programming.

In the worst case scenario (the minimum number is the sum of all elements + 1) this algorithm has the complexity O(n*2^n) (the same as bruteforce), while memory comsumption is O(combination(n,n/2)), which is better compared to bruteforce's O(2^n).

In the best case scenario (when there's no 1 in the input array) the answer will be given at once.

- vladimir.grebennikov December 10, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

bool existSum(int sortedA[], int n, int sum){
    int i=0, j=n-1;
    while(i<j){
        int mid = ((i + j)>>1);
        if(sortedA[mid]>sum)
            j = mid-1;
        else
            i = mid+1;
    }
    i = 0;
    while(i<j){
        if(sortedA[i]+sortedA[j] == sum)
            return true;
        if(sortedA[i]+sortedA[j] > sum)
            j--;
        else
            i++;
    }
    return false;
}

int MinIntNotSum(int A[], int n){
    if(A==nullptr || n<1) return 0;
    sort(A, A+n); //O(nlgn)
    int minSum = A[0]+A[1];
    while(existSum(A,n,minSum))
        minSum++;
    return minSum;
}

- simon.zhangsm December 10, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

In order to find the smallest no which can't be formed by sum of numbers of a positive array.
If we sort the array then if we add the 1st two no ,its possible smallest no can be formed.

So the array 1st element -1 would be smallest no which can't be formed.

To find this element,we can do in O(n),as really dont need to sort it.
min = a[0]
for i =1 to i <n
if a[i] < min
min = a[i]

At the end of loop min will contain the minimum value.

- cooldev December 10, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

what if we have the array 1,5. Your solution returns 0, which is not positive (just non-negative), when it should actually return 2.

- Lenny January 15, 2015 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

SO we need to find out the smallest positive integer that can not be formed from the sum of numbers from array​. Now from that we can infer that the number should also be not present in the array unless it is mandatory to add at least two numbers.
E.g. 1,2,4,8,16,32,66,69,80
Here if you see the number is 64
So going with the above assumption, we :
first will sort the array and find out the smallest missing number lets say x.
second we will get the sub set lets call it A of numbers smaller than x
perform apply the sub set sum algorithm in order to find if obtaining x is possible.
Time Complexity = Sum(x*(Number of elements in the subset A)) x start from 0 and can run till the last input in the sorted array (worst case)

- dhruba.work December 11, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

First sort them.

Them calculate cumulative sum.
If some element a[i] is greater than sum + 1 then there is a gap between them. So number sum + 1 cannot be formed - this is the answer.

- glebstepanov1992 December 11, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

public static int smallestNonSum(int[] array)
{
  Set<Integer> sums = new HashSet<>();
  buildSums(array, sums, 0, 0);
  int i = 1;
  while (sums.contains(i))
  {
    i++;
  }
  return i;
}

private static void buildSums(int[] array, Set<Integer> sums, int sumSoFar, int i)
{
  if (i == array.length)
  {
    sums.add(sumSoFar);
  }
  else
  {
    buildSums(array, sums, sumSoFar, i + 1);
    buildSums(array, sums, sumSoFar + array[i], i + 1);
  }
}

- Anonymous December 11, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

object TwoMinimum extends App {
val arr:Array[Int] = Array(12, 1, 12, 2, 32, 5, 3, 10, 11, 34 ,43, 11, 4, 42)
var v2=arr(0)
var v1=arr(0)
for(i <- arr){
if(i < v1){
v2 = v1
v1 = i
}else if(i < v2 && i != v1){
v2 = i
}
}
println("Answer --> " + (v1 + v2 - 1))
}

- Anonymous December 15, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

IIUC, the integer to be found is not in the array. It seems to me it can be done in O(NlgN), where N is the length of the given array:
1. sort the array.
2. let reach r = 0 and index i = 0.
3. If r + 1 < sorted[i] then return r + 1.
4. r = sorted[i] + r. goto 3.

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

//Complexity is -- O(nlogn) + O(n)
	public static int minimumIntegerWhichCannotBeFormed(int[] arr){
		
		//first sort it
		Arrays.sort(arr);
		int result = 1;
		for(int i=0;i<arr.length;i++){
			
			if(arr[i] <= result){
				result = result + arr[i];
			}else{
				break;
			}
			
		}
		
		return result;
	}

- jimmy.sjsu January 26, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

public static void Execute()
{
int[] arr = { 1, 2, 4, 7, 7, 26};
Console.WriteLine(Func(arr, 0, 1));
}

public static int Func(int[] arr, int index, int k)
{
if(index >= arr.Length)
{
return k;
}

if (arr[index] > k)
{
return k;
}

int pivot = arr[index];
int t = k;

for(int i=k-pivot;i<=k-1;i++)
{
if (t == i + pivot)
{
t++;
}
else if (i + pivot > t)
{
return t;
}
}

return Func(arr, index + 1, t);
}

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

A detailed explanation of this algorithm is provided here:
medium.com/dexters-lab/eli5-find-the-smallest-positive-integer-value-that-cannot-be-represented-as-sum-of-any-subset-of-f8ea2488184b

- Dexter July 17, 2019 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

A detailed explanation of this algorithm is provided here:
"ELI5: Find the smallest positive integer value that cannot be represented as sum of any subset of a given array" in medium.com/dexters-lab

- Dexter July 17, 2019 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

A detailed explanation of this algorithm is provided here:
"ELI5: Find the smallest positive integer value that cannot be represented as sum of any subset of a given array" on
medium<dot>com/dexters-lab/eli5-find-the-smallest-positive-integer-value-that-cannot-be-represented-as-sum-of-any-subset-of-f8ea2488184b

- Dexter July 17, 2019 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

a/b/c

- Dexter July 17, 2019 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

a/b/c

- Dexter July 17, 2019 | 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