Adobe Interview Question
SDE1sCountry: India
The Java solution below will ensure that all the volumes for all the songs will be different. It is still O(2^n) though, so I would not be shocked if there was a much more optimized solution than this. The run-time of it is normally smaller than O(2^n) thanks to it not running further calculations for a path once it has any volume less than the mix, more than the max, or hits the same volume twice.
It also assumes from the problem statement that volumes can be the maximum value or the minimum value, so it uses the >= and <= operators.
int findMaxVolume(int index, int currentVolume, int[] deltaArray, int max, Set<Integer> marked){
if(index == deltaArray.length){
return currentVolume;
}
int down = currentVolume - deltaArray[index];
int up = currentVolume + deltaArray[index];
int downRecursiveResult = -1;
int upRecursiveResult = -1;
if(down >= 0 && down <= max && !marked.contains(down)){
marked.add(down);
downRecursiveResult = findMaxVolume(index+1, down, deltaArray, max, marked);
marked.remove(down);
}
if(up >= 0 && up <= max && !marked.contains(up)){
marked.add(up);
upRecursiveResult = findMaxVolume(index+1, up, deltaArray, max, marked);
marked.remove(up);
}
return Math.max(downRecursiveResult, upRecursiveResult);
}
In order to call this recursive function, do the following:
findMaxVolume(0, initialVolume, volumeChangesArray, maximum, new HashSet<Integer>()))
The Java solution below will ensure that all the volumes for all the songs will be different. It is still O(2^n) though, so I would not be shocked if there was a much more optimized solution than this. The run-time of it is normally smaller than O(2^n) thanks to it not running further calculations for a path once it has any volume less than the mix, more than the max, or hits the same volume twice.
It also assumes from the problem statement that volumes can be the maximum value or the minimum value, so it uses the >= and <= operators.
int findMaxVolume(int index, int currentVolume, int[] deltaArray, int max, Set<Integer> marked){
if(index == deltaArray.length){
return currentVolume;
}
int down = currentVolume - deltaArray[index];
int up = currentVolume + deltaArray[index];
int downRecursiveResult = -1;
int upRecursiveResult = -1;
if(down >= 0 && down <= max && !marked.contains(down)){
marked.add(down);
downRecursiveResult = findMaxVolume(index+1, down, deltaArray, max, marked);
marked.remove(down);
}
if(up >= 0 && up <= max && !marked.contains(up)){
marked.add(up);
upRecursiveResult = findMaxVolume(index+1, up, deltaArray, max, marked);
marked.remove(up);
}
return Math.max(downRecursiveResult, upRecursiveResult);
}
In order to call this recursive function, do the following:
findMaxVolume(0, initialVolume, volumeChangesArray, maximum, new HashSet<Integer>()))
this can be done with dp in o(n*max)
n-array size
max-maximum acceptable volume
explanation- my dp table will have (0 to max) rows and (0 to n-1) columns (initialise with -1)
fill first column by using initial volume(I) ie. update only dp[i-arr[0]][0] and dp[i+arr[0]] (dont forget to maintain the value within 0-max, otherwise -1) by using only positive values(say v) of first column update second column for v+arr[1] and v-arr[1] and so on till (n-1)th column
Ans will be the largest value from (n-1)th column
static int maxvalue=-1;
public static void count(int a[],int low,int high,int index,int curr)
{
if(index==0)
{
if(curr+a[index]>high || curr+a[index]<low)
return;
}
if(curr>high || curr<low)
return;
maxvalue=Math.max(maxvalue, curr);
if(index==a.length)
return;
count(a, low, high, index+1, curr+a[index]);
count(a, low, high, index+1, curr-a[index]);
}
Hi I have a code for this, but the problem is that its terribly slow. The max volume is decided recurently by observing the fact that at each song you have only two choices, increase the volume by current difference, or decrease. So the recurent function makes a binary tree with cutoffs, where the current volume is out of bounds the code stop reccur deeper.
At worst case there are 2^n possible volumes for last song. And the number of additions or subtractions that the code perform will be the same as number of edges in the tree. So i guess if you define n as volume levels in array the complexity would be 2^n+1?
the code below
- bogdan.zima October 12, 2016