Amazon Interview Question Senior Software Development Engineers
Country: India
Interview Type: In-Person
Memoization is probably helpful here since subproblems overlap.
Ex. Map from int to all the permutations of strings making up that int.
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;
}
}
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;
}
}
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;
}
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]);
}
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);
}
}
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);
}
}
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);
}
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;
}
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;
}
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));
}
Should 0 be include in the question? what about 910, 9100, 91000.... it will have infinity permutation result.
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
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