## Adobe Interview Question for SDE1s

Country: India

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

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

``````public static int maxVolume(int vol[], int init, int max)
{
return max(vol, init, max, 0);
}

private static int max(int vol[], int init, int max, int level)
{
if(init < 0 || init > max)return -1;
if(level == vol.length)return init;
int maximum = max(vol, init + vol[level], max, level + 1);
int maximum2 = max(vol, init - vol[level], max, level + 1);
return Math.max(maximum, maximum2);
}

public static void main(String []args){
System.out.println(maxVolume(new int[]{5,3,7}, 5, 10));//10
System.out.println(maxVolume(new int[]{1,1,1}, 0, 5));//3
System.out.println(maxVolume(new int[]{9,1,5,4}, 8, 15));//-1
System.out.println(maxVolume(new int[]{4,9,1,5,4}, 8, 15));//13
}``````

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

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)){
downRecursiveResult = findMaxVolume(index+1, down, deltaArray, max, marked);
marked.remove(down);
}
if(up >= 0 && up <= max && !marked.contains(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>()))``

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

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)){
downRecursiveResult = findMaxVolume(index+1, down, deltaArray, max, marked);
marked.remove(down);
}
if(up >= 0 && up <= max && !marked.contains(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>()))``

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

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

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

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

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.