## 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) 		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).

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.

Comment hidden because of low score. Click to expand.
0

out needs to passed to second sumsTo function

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){
} if(targetSum > 0){
for (int num : array) {
Set<String> stringSubSet = findCombinations(pre+String.valueOf(num), array, targetSum-num);
}
}
return stringSet;
}
}

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){
} if(targetSum > 0){
for (int num : array) {
Set<String> stringSubSet = findCombinations(pre+String.valueOf(num), array, targetSum-num);
}
}
return stringSet;
}
}

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) {
return result;
}
}

for(int i : arr) {
for(String s : permute(arr, sum - i)) {
}
}

return result;
}``````

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

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

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

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;
test(list, sum - list.get(i), result);
result.remove(result.size()-1);
}
}``````

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)
{
return;
}
if (sum < 0)
{
return;
}
foreach (var i in array)
{
Find(array, sum - i, result + i, results);
}
}``````

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

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

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

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)
{
result.AddRange(GetPermutationsCore(A, current, sum - a, memo));
current.RemoveAt(current.Count - 1);
}

return result;
}``````

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

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?

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

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.

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

You can do DFS on the array of elements.

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.

Comment hidden because of low score. Click to expand.
0

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

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

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

ииии

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

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.

### 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.