## Adobe Interview Question for Software Engineer / Developers

• 0

Country: India

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

I think this is simple Change problem, which can be solved by DP or recursion.
pseudo code for this will be....

``````Change(array, size, target)
best_change[0] = 0
for c in target
best_change[c] = infinite
for i in size
if c > array[i]
best_change[c-array[i]] + 1 < best_change[c]
best_change[c] = best_change[c- array[i]] + 1

return best_change[target]``````

and array need not to be sorted....

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

We can use the greedy approach as well but that doesn't always lead to the right solution.

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

recursive version

``````// Returns the min count of coins required to make a given change = amount
int coin_change(int change_amount, int val[], int n)
{
assert(change_amount>=0 && n>=0);

if(change_amount==0) return 0; // No coins required.

if(n==0) return INT_MAX;

if(val[n-1] > change_amount) return coin_change(change_amount, val, n-1);

// assuming infinite coins of each denominations (notice the first call with n again)
return min( coin_change(change_amount-val[n-1], val, n),
coin_change(change_amount, val, n-1) );
}``````

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

Another approach based on DP[Modification of cutting of rod].
This method doesn't require the coin[]={1,3,10} to be sorted.
Say, we know the number of coins required for n-1, we can extend it for n also.
1. Take a minCount array. If minCount[i]==j, then minimum of j number of coins are required for i.

``````void countCoins(int* coin,int size,int tofind)
{
int minCount[tofind+1],i,j,mintillnow;

for(i=0;i<tofind+1;++i)
minCount[i]=0;

for(i=0;i<size;i++)
if(coin[i]<=tofind)
minCount[coin[i]]=1;
for(i=1;i<=tofind;i++)
{
if(!minCount[i])
{
mintillnow=INT_MAX;
for(j=1;j<i;++j)
{
if(minCount[j]+minCount[i-j]<mintillnow)
mintillnow=minCount[j]+minCount[i-j];
}
minCount[i]=mintillnow;
}
}
printf("Minimum number of coins needed is: %d",minCount[tofind]);
}``````

The only disadvantage of this method is that it may require large amount of space.
e.g. we may need change of Rs 1 lakh[space required is 1lakh bytes]. However, it can be reduced if we go for bit-vector.

Complete code here: ideone.com/pKEwC

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

This blog has the solution n1b-algo.blogspot.com/2009/01/optimal-coin-change-problem

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

n1b-algo.blogspot.com/2009/01/optimal-coin-change-problem.html

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

It is the simple one.
Assuming that the coin array is sorted in ascending order[1,3,10].

Time complexity: O(N)
Space complexity: O(1)

Here is the code
// to find the change of k.

``````int countCoins(int* coin,int size,int value)
{
int i,count,total=0;
for(i=size-1;i>=0;i--)
{
count=value/coin[i];
if(count)
{
value-=count*coin[i];
total+=count;
printf("%d number of Rs %d coins\n",count,coin[i]);
}
}
}

int main()
{
int coin[]={1,3,10},size,k;

size=sizeof(coin)/sizeof(coin[0]);
scanf("%d",&k);

printf("Minimum pickings: %d",countCoins(coin,size,k));
return 0;
}``````

ideone.com/Tr69T

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

This code will not give minimum count.
Try {1,2,6,7,10} and k=13, this code will give answer 3 but it should be 2.

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

``````int getMinPicks(int []numbers, int target){
int minIndex = numbers.length -1;
int result = target/numbers[minIndex];
target = target%numbers[minIndex];

while(target!= 0){
if(minIndex  == 0)
return -1;
result+=(target/numbers[--minIndex]);
target = target%numbers[minIndex];
}
return result;
}``````

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

is the array is sorted or not?

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

The first answer by Mejbaol Sajib is wrong. Run it for the input {1, 2, 4, 5, 6} with the target of 15. The answer should be 3 (6 + 5 + 4). Your code returns 4.

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

This problem is NP complete. It is same as subset sum problem. en.wikipedia.org/wiki/Subset_sum_problem

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

I've compiled and tested this C++ code. The input array doesn't need to be sorted. Also prints the elements that add up to the target sum.

``````#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

int main ( ) {
int val, target;
int index = 0; /* Current array index */
int minpick = 10000; /* Initialize to a high value */

vector<int> arr; /* The vector holding the elements */

/* Temporary vector and the vector holding the minimum set */
vector<int> temp, min;

cout << endl << "Enter the array elements. End with EOF (ctrl + D)" << endl;

while (cin >> val)
arr.push_back(val);

/* Clear the cin buffer */
cin.clear();

cout << endl << "Enter the target sum: ";
cin >> target;

/* Sort the array */
sort(arr.begin(), arr.end());

/* Assumption made that the target itself
* doesn't exist in the array. Would be better
* if that edge-case is added too. */
while (index < arr.size() && arr[index] < target) {
int sum = arr[index];	/* Sum of array elements */
int i = index + 1;
int count = 1;	/* Count of elements that add up to target */
temp.push_back(arr[index]);

while (i < arr.size() && sum < target) {
sum = sum + arr[i];
temp.push_back(arr[i]);
count++;

if (sum >= target) {
if (sum == target) {
if (count < minpick) {
/* Least number of elements maintained
* in minpick variable */
minpick = count;

/* Copy the elements adding up to target
* from temp to the min vector */
min.assign (temp.begin(), temp.end());
}

}

/* Pop the last two elements from the temp
* vector and take them off from sum. This
* is needed to move on and try out other
* possible combinations. */
sum = sum - temp.back(); temp.pop_back();
sum = sum - temp.back(); temp.pop_back();
count = count - 2;

if (sum == 0) break;
}
else {
i++;
}
}
temp.clear();
index++;
}

if (minpick == 10000) {
cout << endl << "No combination exists." << endl << endl;
return 0;
}

cout << endl;

for (vector<int>::iterator it = min.begin(); it != min.end(); it++) {
cout << *it << "  ";
}

cout << endl << "Minimum picks = " << minpick << endl << endl;
return 0;
}``````

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

With some assumption the code can be done.
1. We will pick the coin only once - ie. no duplicates
2. The array is ordered - or sorting is needed

``````#include<stdio.h>

void main()
{
int test1[] = {1,2,3,4,5,6};
int test2[] = {1,3,10};
//assuming the sorted array is given
//otherwise it has to ordered.
printf("%d \n", minimum_pick(test1, 6, 15)); //printed 3
printf("%d \n", minimum_pick(test2, 3, 11)); //printed 2
}

int minimum_pick(int *numbers, int size, int sum)
{
int tot = 0, count = 0;
if (sum == 0)
{
return 0;
}
else
{
//loop until you attain the max sum
while(size > -1)
{
if (tot + numbers[size-1] < sum)
{
count++;
tot += numbers[size-1];
}
else if (tot + numbers[size-1] == sum)
{
count++;
break;
}
size--;
}
}
return count;
}``````

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

ethioer : Your code is just checking whether how many numbers were fit together. You does not actually checking whether the particular sum is present or not!

please check with the input 4, 6, 8, 9 and the sum required is 11. Your code is giving 2 as answer.

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

Ethioer ....dnt paste any code next tym here ..watsed my time :/

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

@Mahendra: What's with your English dude?

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

The first has a flaw. it can be done with O(n^2) as follows with some test case
it is done in c

``````#include<stdio.h>
void main()
{
int test1[] = {1,2,3,4,5,6};
int test2[] = {1,3,10};
int test3[] = {1,3,4,5,6};
//assuming the sorted array is given
//otherwise it has to ordered.
printf("%d shall print 3\n", minimum_pick(test1, 6, 15));
printf("%d shall print 2\n", minimum_pick(test2, 3, 11));
printf("%d shall print 1\n", minimum_pick(test3, 5, 4));
printf("%d shall print 2\n", minimum_pick(test3, 5, 7));
printf("%d shall print 3\n", minimum_pick(test3, 5, 14));
}

int minimum_pick(int *numbers, int length, int sum)
{
int tot = 0, count = 0, min = 1000;;
if (sum == 0)
{
return 0;
}
else
{
int index = length - 1;
//loop until you attain the max sum
while(index >= 0)
{
tot = numbers[index], count=1;
if (tot == sum)
{
return count; //one is the minimum
}
else if (numbers[index]>sum)
{
index--;
continue;
}

int inner_index = index - 1, found=0;
while(inner_index >= 0)
{
if (tot + numbers[inner_index] < sum)
{
count++;
tot += numbers[inner_index];
}
else if (tot + numbers[inner_index] == sum)
{
count++;
found=1;
break;
}
inner_index--;
}
if (found && count < min)
{
min = count;
}
index--;
}
}
return min;
}``````

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

``````int main()
{
int numOfDenominations = 0;
cout << "Please put in the number of denominations available " << endl;
cin >> numOfDenominations;
int * denominations = new int[numOfDenominations];
memset(denominations , 0 , sizeof(int) * numOfDenominations);

int sumNeeded = 0;
cout << "Please enter the sum for which the change is needed " << endl;
cin >> sumNeeded;
int * optimumDenominationCount = new int[sumNeeded+1];
int * optimumDenomination = new int [sumNeeded+1];

for (int i =0 ; i < sumNeeded+1 ; i ++)
{
optimumDenominationCount[i] = 10000;
optimumDenomination[i] = 10000;
}

cout << "Please put in the denominations " << endl;

for (int i = 0 ; i < numOfDenominations ; i++)
{
cin >> denominations[i];
if(denominations[i] <= sumNeeded )
{
optimumDenomination[(denominations[i])] = (denominations[i]);
optimumDenominationCount[(denominations[i])] = 1;
}
}

for (int i = 1 ; i <= sumNeeded ; i++)
{
for (int j = 0 ; j < numOfDenominations ; j ++)
{
if(i-denominations[j] > 0)
{
if(optimumDenominationCount[i] > optimumDenominationCount[i-denominations[j]] + 1)
{
optimumDenominationCount[i] = optimumDenominationCount[i-denominations[j]] + 1;
optimumDenomination[i] = denominations[j];
}
}
}
}
if(optimumDenominationCount[sumNeeded] == 10000)
{
cout << "Change cannot be provided " << endl;
}
else
{
cout << " The count is = " << optimumDenominationCount[sumNeeded] << endl;
cout << "The coins needed are " << endl;
int temp = sumNeeded;
while(temp > 0)
{
cout << optimumDenomination[temp] << endl;
temp = temp - optimumDenomination[temp];
}
}
}``````

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

/* Sort the Input Array using any Sorting Algorithm and pass it as an I/P arg to FindSum() */

int FindSum (int *p_array, int req_sum, int num_elements)
{
int index = INVALID_VAL;
int num_picks = 0;
char flag = NOT_SET;

/* Find the Maximum Array Element which is <= req_sum */
for (index = num_elements-1; index < num_elements && p_array[index]>=req_sum; index--)
{
if (p_array[index] == req_sum)
{
flag = SET;
break;
}
}
if (index>=0 && index<MAX_SIZE)
{
num_picks++;
}

/* Now, p_array[index] = maximum array value < req_sum */
if (!flag)
{
num_picks = num_picks + FindSum(p_array, req_sum-p_array[index], num_elements);
}

return num_picks;
}

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

good solution, but can't we do it for unsorted array.

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

int main()
{
int numbers[]={1,2,4,5,6};
int target = 9, len = 5;
int final_result = 999, temp_result = 0;
while(len > 0)
{
temp_result = 0;
temp_result = findsum(numbers,target,len,temp_result);
if( final_result > temp_result)
{
final_result = temp_result;
}
len--;
}

printf("\nFinal result is %d", final_result);
}

int findsum(int numbers[], int target, int len, int temp_result)
{
if(target == 0)
return temp_result;
if(len>=0)
{
if((target - numbers[len-1]) >= 0)
{
temp_result++;
return findsum(numbers,target-(numbers[len-1]), len-1, temp_result);
}
else
return findsum(numbers,target, len-1, temp_result);
}
}

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

``````int MAX_NO_PICKS = Integer.MAX_VALUE;
//Pass any unsorted array, sum to check,no of picks pass 0, baseIndex pass 0
int getNumberOfPicks(int[] coinArr, int sum, int noOfPicks, int baseIndex){
if(noOfPicks+1 >= MAX_NO_PICKS && sum !=0){
return -1;
}else if(sum == 0){
MAX_NO_PICKS = noOfPicks;
return noOfPicks;
}
if(sum < 0) return -1;
if(baseIndex >= coinArr.length) return -1;
int tempSum = sum - coinArr[baseIndex];
int choosenPick = getNumberOfPicks(coinArr, tempSum, noOfPicks+1,baseIndex+1);
int notChoosenPick = getNumberOfPicks(coinArr, sum, noOfPicks,baseIndex+1);
//System.out.println(choosenPick +" "+notChoosenPick);
if(choosenPick == -1 && notChoosenPick == -1){
return -1;
}else if(choosenPick == -1){
return notChoosenPick;
}else if(notChoosenPick == -1){
return choosenPick;
}else{
if(choosenPick < notChoosenPick){
return choosenPick;
}else{
return notChoosenPick;
}
}

}``````

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

thnx ;) it was very helpful..

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

Array should be sorted

``````{

#include <iostream>
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
void PrintArray(int* A, int* B, int arr_size)
{
printf("\n Picking Coins \n");
for(int i = 0; i <arr_size; i++)
{
printf("\n A[i] %d ::  B[i] %d \n", A[i], B[i]);
}
return;
}
int SolveEquation(int* A, int* B, int total, int size, int arr_size, int coins )
{
static int min_coins = total;
if(size == 0)
{
if(total % A[size] == 0)
{
B[size] = total/A[size];
total = total - A[size]*B[size];
if(coins +B[size] < min_coins)
{
printf("\n current min coins %d min_coins %d \n", coins, min_coins);
min_coins = coins;
PrintArray(A, B, arr_size);
}
}
return min_coins;
}
int max = total/A[size];
for(int j = max; j >= 0; j--)
{
if(coins+j > min_coins)
break;
B[size] = j;
SolveEquation(A, B, total - A[size]*j , size-1, arr_size, coins+j);
}
return min_coins;
}``````

}

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

I think we can simply use the Knapsack solution. Please correct me if I am wrong.

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

+1 For a cleanly asked question with proper English and a sensible description. :)

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

this works!

``````int minimum_pick(int *numbers, int size, int sum)
{
int tot = 0, count = 0,s=size;
if (sum == 0)
{
return 0;
}
else
{
//loop until you attain the max sum
while(size > 0)
{
if (tot + numbers[size-1] < sum)
{
count++;
tot += numbers[size-1];
}
else if (tot + numbers[size-1] == sum)
{
count++;
break;
}
else if(size<=1)
{
size=s--;
count=0;
tot=0;
}
size--;
}
}
return count;
}

int main()
{
int test1[] = {1,2,3,4,5,6};
int test2[] = {5,6,9};
//assuming the sorted array is given
//otherwise it has to ordered.
printf("%d \n", minimum_pick(test1, 6, 15)); //printed 3
printf("%d \n", minimum_pick(test2, 3, 11)); //printed 2

return 0;
}``````

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

``````#include<stdio.h>

int count(int *coin , int len , int sum)
{
int tot , min = 10000;
int i ;
for( i = len - 1 ; i >= 0 ; i--)
{
tot = 0 ;
int sum1 = sum;
int j ;
int val;
for( j = i ; j >= 0 ; j--)
{
val = sum1/coin[j] ;
tot += val;
int sum2 = coin[j] * val;
if(sum1 == sum2)
{
break;
}
sum1 -= val*coin[j] ;
}
if( tot < min)
min = tot;
}
return min;
}

int main()
{
int coin[] = {1,3,10};
int size,sum;
scanf("%d",&sum);
size=sizeof(coin)/sizeof(coin[0]);
printf("Min No. of coins =  %d",count(coin,size,sum));
return 0;
}``````

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

//Given coin array and a sum K, find min. number of required coin to make sum K.
#include<stdio.h>
#include<conio.h>
main()
{
int a[20],n,i,k,j,b=0,max,sum=0;
printf("enter no of coin\n");
scanf("%d",&n);//no of coin
printf("\n enter coin\n");
for(i=0;i<n;i++)
scanf("%d",&a[i]);//enter arrat
printf("enter sum of money");
scanf("%d",&k);//enter money
for(i=0;i<n;i++)
sum=sum+a[i];
if(sum<k)//if sum of money is grester then the sum of array
printf("not possible");
else
{
while(k>0)
{max=0;
for(i=0;i<n;i++)
{
if(max<a[i]&&k>=a[i])
{
max=a[i];
j=i;
}}
k=k-max;
printf("%d ",a[j]);
a[j]=0;
b++;
}
printf("\n no of coin==%d\n",b);
}
getch();
}

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

((( #include<stdio.h>

int reqd(int *a, int siz, int sum)
{
int i;

if(a[siz - 1] > sum && siz > 0)
{
//printf("A%d ", a[siz - 1]);
return reqd(a, siz-1, sum);
}
else if(a[siz - 1] == sum && siz > 0)
{
printf("B%d ", a[siz - 1]);
return (1);
}
else if(a[siz - 1] < sum && siz > 0)
{
printf("C%d ", a[siz - 1]);
i = reqd(a, siz, sum - a[siz - 1]);
if(i <0 )
return reqd(a, siz-1, sum);
else return (1 + i);

}
else
printf("failed ");
return -1;
}
main()
{
int ar[] = {3,5,7,11}; // sorted array
int siz = 4; //size of above array
int sum=0,j=0;

scanf("%d", &sum);

j = reqd(ar, siz, sum);
printf("\n%d", j);
}
)))

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

``````#include<stdio.h>

int reqd(int *a, int siz, int sum)
{
int i;

if(a[siz - 1] > sum && siz > 0)
{
//printf("A%d ", a[siz - 1]);
return reqd(a, siz-1, sum);
}
else if(a[siz - 1] == sum && siz > 0)
{
printf("B%d ", a[siz - 1]);
return (1);
}
else if(a[siz - 1] < sum && siz > 0)
{
printf("C%d ", a[siz - 1]);
i = reqd(a, siz, sum - a[siz - 1]);
if(i <0 )
return reqd(a, siz-1, sum);
else return (1 + i);

}
else
printf("failed ");
return -1;
}

main()
{
int ar[] = {3,5,7,11};   // sorted array
int siz = 4;            //size of above array
int sum=0,j=0;

scanf("%d", &sum);

j = reqd(ar, siz, sum);
printf("\n%d", j);
}``````

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

The below code does it recursively. It shows failure message if the sum is not possible to obtain from the given denominations.

``````#include<stdio.h>

int reqd(int *a, int siz, int sum)
{
int i;

if(a[siz - 1] > sum && siz > 0)
{
//printf("A%d ", a[siz - 1]);
return reqd(a, siz-1, sum);
}
else if(a[siz - 1] == sum && siz > 0)
{
printf("B%d ", a[siz - 1]);
return (1);
}
else if(a[siz - 1] < sum && siz > 0)
{
printf("C%d ", a[siz - 1]);
i = reqd(a, siz, sum - a[siz - 1]);
if(i <0 )
return reqd(a, siz-1, sum);
else return (1 + i);

}
else
printf("failed ");
return -1;
}

main()
{
int ar[] = {3,5,7,11};   // sorted array
int siz = 4;            //size of above array
int sum=0,j=0;

scanf("%d", &sum);

j = reqd(ar, siz, sum);
printf("\n%d", j);
}``````

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

``````#include <iostream>
#include <string.h>
#include<limits.h>
using namespace std;

int change(int *coin, int size, int num){
int total[num + 1];
total[0] = 0;
for (int i = 1; i <= num; i++){
total[i] = INT_MAX;
for (int j = 0; coin[j] <= i && j < size; j++){
if (total[i - coin[j]] + 1 < total[i] )
total[i] = total[i - coin[j]]+ 1;
}

}
}

int main() {
int coin[3] = {1, 3, 5};
int k =11;
int size = sizeof(coin)/sizeof(coin[0]);
cout<<change(coin, size, k);
return 0;
}``````

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

an o(n) solution: the question is same as:

geeksforgeeks.org/archives/19267

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

This is not the same problem.

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

ohhh..i get that..sorry, i guess it is the following problem. we can modify to get the shortest sub-set

geeksforgeeks.org/archives/14469

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.