Akamai Interview Question
Software DevelopersCountry: United States
// ZoomBA
def ways_to_dist( target_value ){
count = 0
q = list() // create a queue
q.enqueue ( [0,0,list(0)] ) // add to it
// now the loop
while ( !empty(q) ){
#( prev_inc , cur_sum , path ) = q.dequeue()
continue ( cur_sum > target_value ) // obvious, nothing else can do
continue ( cur_sum == target_value ) {
println( path ) // for debug diagnostic
count +=1 // increment possible scenarios
}
for ( inc : [1,5,10,25 ] ){
if ( inc >= prev_inc ){ // ensure sorted path
q.enqueue( [ inc , cur_sum + inc , path + inc ] )
}
}
}
return count
}
println ( ways_to_dist( 42 ))
This is now a non recursive solution.
#include <iostream>
using namespace std;
int coin_chng(int*arr,int n,int sum,int dp[][100])
{
if(sum==0)
return 1;
if(n<0)
return 0;
if(dp[sum][n]!=-1)
return dp[sum][n];
if(arr[n]>sum)
return dp[sum][n]=coin_chng(arr,n-1,sum,dp);
return dp[sum][n]=coin_chng(arr,n,sum-arr[n],dp)+coin_chng(arr,n-1,sum,dp);
}
int main() {
// your code goes here
int arr[]={1,5,10,25};
int sum=5;
int n=sizeof(arr)/sizeof(arr[0]);
int dp[100][100];
for(int i=0;i<=sum;i++)
{
for(int j=0;j<n;j++)
dp[i][j]={-1};
}
int num=coin_chng(arr,n-1,sum,dp);
cout<<"Possible combinations are: "<<num;
return 0;
}
A D.P approach!(Top down approach)
Tiime complexity-O(n^2)
public class CoinDenomination {
public static void main(String[] args) {
double coins[] = {25.0,10.0,5.0,1.0};
double sum = 2342.5;
int count = 0;
for(int i=0;i<coins.length;i++){
count = (int) (sum/coins[i]);
sum = sum - count * coins[i];
System.out.println("Denomination for " + coins[i] + " is:" + count);
count = 0;
}
if(sum > 0){
System.out.println("The balance of " + sum + " have no coin denomination available");
}
}
}
We tried a bit sanity here. BUT, we are not sure, we are going to optimize it further.
- NoOne October 10, 2016