Amazon Interview Question for Senior Software Development Engineers


Country: India
Interview Type: In-Person




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

This task can be solved by a recursive algorithm. Let assume that the input array 'a' contains unique integers 1-9 and we are give a target value 'x'. Notice that when we use one number from 'a', lets say number 'y = a[j]', we have to solve exactly the same problem with the new target value 'x_new = x - y'.

Hence, we can solve the task recursively while checking for two basecases: (i) target value is zero which means sums to original target value or (ii) target value is less than zero which means does not sum to the original target value. The last thing is to keep track of the values used so far and if the basecase (i) occurs push the string on the stack. Finally, we return th stack of strings to the client.

A sample code is shown below:

private static Stack<String> out;

public static Iterable<String> sumsTo(int[] a, int x) {
	out = new Stack<String>();
	sumsTo(a, x, "");
	return out;
}

private static void sumsTo(int[] a, int x, String accum) {
	if (x == 0)	 		out.add(accum);
	if (x <= 0) 		return;

	for (int k = 0; k < a.length; k++)
		sumsTo(a, x-a[k], accum + a[k]);
}

One should clarify with the interviewer how the code should behave if zero is contained in 'a' which may yield an infinite numer of permutations. If the numbers in a[] are not unique one can handle duplicate permutations via symbol table (Hash or Tree Map).

- autoboli April 27, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
1
of 1 vote

Memoization is probably helpful here since subproblems overlap.
Ex. Map from int to all the permutations of strings making up that int.

- JW April 28, 2015 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

out needs to passed to second sumsTo function

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

import java.util.HashSet;
import java.util.Set;

public class TargetSum {
public static void main(String[] args) {
int[] arr = {5, 2, 3};
int sum = 10;
Set<String> set = findCombinations(arr, sum);
System.out.println(set);
}

public static Set<String> findCombinations(int[] array, int targetSum){
return findCombinations("", array, targetSum);
}

public static Set<String> findCombinations(String pre, int[] array, int targetSum){
Set<String> stringSet = new HashSet<String>();
if(targetSum == 0){
stringSet.add(pre);
} if(targetSum > 0){
for (int num : array) {
Set<String> stringSubSet = findCombinations(pre+String.valueOf(num), array, targetSum-num);
stringSet.addAll(stringSubSet);
}
}
return stringSet;
}
}

- Shrek April 27, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

import java.util.HashSet;
import java.util.Set;

public class TargetSum {
public static void main(String[] args) {
int[] arr = {5, 2, 3};
int sum = 10;
Set<String> set = findCombinations(arr, sum);
System.out.println(set);
}

public static Set<String> findCombinations(int[] array, int targetSum){
return findCombinations("", array, targetSum);
}

public static Set<String> findCombinations(String pre, int[] array, int targetSum){
Set<String> stringSet = new HashSet<String>();
if(targetSum == 0){
stringSet.add(pre);
} if(targetSum > 0){
for (int num : array) {
Set<String> stringSubSet = findCombinations(pre+String.valueOf(num), array, targetSum-num);
stringSet.addAll(stringSubSet);
}
}
return stringSet;
}
}

- Shrek April 27, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

Can be as simple as 1 single function like this

static List<String> permute(int[] arr, int sum) {
		if(sum <=0)
			return Collections.emptyList();
		
		ArrayList<String> result = new ArrayList<String>();
		
		for(int i : arr) {
			if(i == sum) {
				result.add(String.valueOf(i));
				return result;
			}
		}
				
		for(int i : arr) {
			for(String s : permute(arr, sum - i)) {
				result.add(i + s);
			}
		}
		
		return result;
	}

- timpham2003 April 28, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

How about this:

private static HashSet<String> result = new HashSet<String>();
	private static int [] inputArray = { 2, 3, 5};
	private static int target = 10;
	
	public static void main(String[] args) {
		System.out.println("InputArray = " + Arrays.toString(inputArray));
		System.out.println("Target = " + target);
		for(int i=0; i<inputArray.length; i++) {
			checkSum("",i,0);
		}
		for(String res : result) {
			System.out.println(res);
		}
	}

	private static void checkSum(String sofar, int next, int sum) {
		if (next >= inputArray.length) return;
		if (sum==target) {
			char [] arr = sofar.toCharArray();
			Arrays.sort(arr);
			result.add(String.valueOf(arr));
			return;
		}
		
		if (sum > target) {
			return;
		}
		checkSum(sofar+Integer.toString(inputArray[next]), next, sum+inputArray[next]);
		checkSum(sofar+Integer.toString(inputArray[next]), next+1, sum+inputArray[next]);
	}

- psisanon April 29, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

getSum(int *arr, int NUM, int *numlist)
{
	int temp=NUM;
	for (int i=0,i<sizeof(arr); i++)
	{
		temp=temp-arr[i];
		newlist=(int *) malloc ( sizeof(numlist)+sizeof(int));
		newlist[0]=arr[i];
		copy_arr(newlist,numlist);
		if (temp>0)
		{
			getSum(arr,temp,newlist);
		}
		else if (temp <0)
		{
			return NULL;
		}
		else
		{
			print_arr(newlist);
		}
		temp=NUM;
		free(newlist);
	}
}

- sanjay.2812 May 03, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

public void test(List<Integer> list, int sum, List<Integer> result) {
		for (int i = 0; i < list.size(); i++) {
		    if (sum == 0) {
		    	System.out.println(result);
		    	return;
		    }
		    if (sum < list.get(i))
		    	return;
		    result.add(list.get(i));
			test(list, sum - list.get(i), result);	
			result.remove(result.size()-1);
		}
	}

- sapal.jazz May 06, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

static void Find(List<int> array, int sum, string result, List<string> results)
        {
            if (sum == 0)
            {
                results.Add(result);
                return;
            }
            if (sum < 0)
            {
                return;
            }
            foreach (var i in array)
            {
                Find(array, sum - i, result + i, results);
            }
        }

- Roman A May 07, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

int *A, n, t;

void print(const vector<int> &a)
{
	for (int i = 0; i < a.size(); ++i) cout << a[i] << " "; cout << endl;
}

void dfs(int i, int sum, vector<int> &a)
{
	if (sum == t)
	{
		do
		{
			print(a);
		}
		while (next_permutation(a.begin(), a.end()));

		return;
	}

	a.push_back(0);

	for (int j = i; j < n && sum + A[j] <= t; ++j)
	{
		a.back() = A[j]; dfs(j, sum + A[j], a);
	}

	a.pop_back();
}

void printPermutationsEqualtoSum(int A[], int n, int target)
{
	::A = A; ::n = n; t = target;

	sort(A, A + n);

	vector<int> a;

	dfs(0, 0, a);
}

- malinbupt May 12, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

JavaScript:

function solve(array, target) {
    var result = [];

    function recursolve(equation, sum) {
        if (sum == target) {
            result.push(equation.join(""));
        } else if (sum < target) {
            for (var i = 0; i < array.length; i++) {
                recursolve(equation.concat([array[i]]), sum + array[i]);
            }
        }
    }
    recursolve([], 0);
    return result;
}

- Jack Le Hamster May 13, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

Seems like something that dynamic programming could help. I did not remove duplicates making the assumption that numbers are unique.

I was going to convert into a bottom up algorithm adding till is more than sum that you are looking for but decided to keep it like these as I can think this way best to understand, at least for me it is.

public static IEnumerable<IEnumerable<int>> GetPermutations(int[] A, int[] S)
{
	List<List<int>> result = new List<List<int>>();

	var memo = new Dictionary<int, List<List<int>>>();

	foreach(int sum in S)
	{
		result.AddRange(GetPermutationsCore(A, new List<int>(), sum, memo));
	}

	return result;
}

private static List<List<int>> GetPermutationsCore(
						int[] A, 
						List<int> current, 
						int sum, 
						Dictionary<int, List<List<int>>> memo)
	{

	if(sum == 0)
	{
		return new List<List<int>>() { new List<int>(current) };
	}
	else if(sum < 0)
	{
		return new List<List<int>>();
	}

	if(memo.ContainsKey(sum))
	{
		return memo[sum];
	}

	var result = new List<List<int>>();

	foreach(int a in A)
	{
		current.Add(a);
		result.AddRange(GetPermutationsCore(A, current, sum - a, memo));
		current.RemoveAt(current.Count - 1);
	}

	memo.Add(sum, result);
	return result;
}

- Nelson Perez May 15, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

graph traversal algorithm using node weighted graph? node weights are numbers in arrays

- catchclrs June 05, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

cassic dynamic programing problem. If I am not wrong, this is also np-hard? or even np-complete?

- charu June 12, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

private static Stack<Integer> stack = new Stack<Integer>();
	private static int sumInStack = 0;

	private static void populateSubset(int[] data, int fromIndex, int endIndex) {

		if (sumInStack == TARGET_SUM) {
			print(stack);
		}
		else if (sumInStack > TARGET_SUM) {
			return;
		}
		for (int currentIndex = fromIndex; currentIndex < endIndex; currentIndex++) {

			stack.push(data[currentIndex]);
			sumInStack += data[currentIndex];

			populateSubset(data, currentIndex , endIndex);
			sumInStack = sumInStack - (Integer) stack.pop();
		}
	}

	private static void print(Stack<Integer> stack) {
		StringBuilder sb = new StringBuilder();
		for (Integer i : stack) {
			sb.append(i).append(" + ");
		}
		String str = sb.toString();

		System.out.println("combination is : " + str.substring(0, str.length() - 3));
	}

- er.vishalmehta83 February 03, 2016 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

Use Trie data structure. Build the tries till the sum became = to the given one.
Take all the tries whose sum_node becomes 10.

- Pranay Deshpande February 11, 2016 | Flag Reply
Comment hidden because of low score. Click to expand.
-1
of 1 vote

You can do DFS on the array of elements.

- cnu1438 April 27, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
-1
of 1 vote

Should 0 be include in the question? what about 910, 9100, 91000.... it will have infinity permutation result.

- LiLLI April 27, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

There is no zero(0). just 1 - 9.

I put it as 0-9 by mistype. But actually it is from 1-9.

- panchadi520 April 28, 2015 | Flag
Comment hidden because of low score. Click to expand.
-1
of 1 vote

ииии

- иии April 29, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
-1
of 1 vote

START_DEVICE



3

device = eeprom



4

devNo = 0



5

devBase = (0x80000000 + (0x0074 << 1))



6

dataBusWidth = BITS_TEJ_I2C



7

eepromType = SERIAL_EEPROM



8

regWidth = BITS_8



9

portSize = BITS_16



10

privateData = 0xa0



11

intrLine = NONE



12

baseIsAbs = 0



13

END_DEVICE



14



15

START_DEVICE



16

device = lm81



17

devNo = 0



18

devBase = (0x80000000 + (0x0074 << 1))



19

dataBusWidth = BITS_TEJ_I2C



20

regWidth = BITS_8



21

portSize = BITS_16



22

privateData = 0x58



23

intrLine = NONE



24

baseIsAbs = 0



25

END_DEVICE

- vvnv April 29, 2015 | 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