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
     }

- bogdan.zima October 12, 2016 | Flag Reply
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)){
			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>()))

- mike.S October 17, 2016 | Flag Reply
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)){
			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>()))

- mike.S October 17, 2016 | Flag Reply
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

- learn October 21, 2016 | Flag Reply


Add a Comment
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.

Learn More

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.

Learn More

Resume Review

Most engineers make critical mistakes on their resumes -- we can fix your resume with our custom resume review service. And, we use fellow engineers as our resume reviewers, so you can be sure that we "get" what you're saying.

Learn More

Mock Interviews

Our Mock Interviews will be conducted "in character" just like a real interview, and can focus on whatever topics you want. All our interviewers have worked for Microsoft, Google or Amazon, you know you'll get a true-to-life experience.

Learn More