Ebay Interview Question for Software Engineer / Developers


Country: United States
Interview Type: Phone Interview




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

void FindMaxWaterReservoir(int *a)
{
        if(a==NULL) 
            return;
	int n=SIZE(a);	
	int diff=INT_MAX;
	int maxleft=INT_MIN;
	int I,J,i;

	int *max=new int[n];
	memset(max,0,sizeof(int)*n);
	max[n-1]=a[n-1];

	for(i=n-2;i>=0;i--)
		max[i]=maxval(max[i+1],a[i]);	

	for(i=0;i<n;i++)
	{
		if(a[i]>maxleft)
			maxleft=a[i];
		if(max[i]-maxleft<diff && max[i]-maxleft>0)
		{
			diff=max[i]-maxleft;
			I=max[i];
			J=maxleft;
		}
	}

	printf("\nFirst: %d\tSecond: %d\t Difference: %d\tAmount Saved: %d\n",I,J,diff,(I<=J?I:J));
	delete [] max;
}

- Anonymous October 25, 2013 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

Above looks familiar. You posted code almost identical to this in another thread after I solved the this same question in there.

Cool. Anonymous isn't really anonymous ;)

- S O U N D W A V E October 26, 2013 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

Here is a simple Java code to solve this puzzle. I've tried it with different inputs, which are commented in the source code.

/**
 * 	An array of integer represents a bar graph, where index of array is X axis (width = 1) and Y axis represents height of the bar graph at X, find out how much water will retain if it rains infinite on the structure. Only portion of graph that retains water is enclosed area due to height difference of bar graph. You need to assume that each bar itself doesn't store any water. 

	e.g. {1,2,3} then no water is stored 
	{6,4,1} then no water is stored 
	{3,2,1, 5} then 3 unit water is stored between 3 & 5 (1 unit on 2 and 2 unit on 1)
 * 	@author ruharish
 *
 */
public class CollectedWaterOnBarGraph {
	public static void main(String[] args)
	{
		/*
		 * This program follows a simple algo -
		 * 1. Iterate over each of the element, treating current element value as curValue.
		 * 2. Keep comparing with the elements on the left, till we reach beginning of the array or boundary of previous collection enclosure.
		 * 3. If any element is more than curValue, make it as the curMaxValue and continue searching.
		 * 4. If any element is equal to the curValue, make sure that there is at least one element in between, so that water can get collected there and continue searching for bigger numbers.
		 * 5. Keep comparing with the elements on the rgith, till we reach end of the array.
		 * 6. If any element is more than curValue, make it as the curMaxValue and continue searching.
		 * 7. If we have a non-zero lIndex & rIndex (found a enclosure where water can get collected), iterate over each of the element in between and measure the water collected. 
		 */
		
		//int[] input = {1, 2, 3, 5};
		//int[] input = {3, 2, 1 ,5};
		int[] input = {4, 1, 6, 4, 1, 6, 3, 1, 4, 6};
		//int[] input = {9, 4, 1, 6, 4, 1, 6, 3, 1, 4, 6};
		//int[] input = {9, 4, 1, 6, 4, 1, 6, 3, 1, 4, 6, 8};
		
		int totalQuantity = 0; //Total # of units of water collected
		int prevRIndex = 0; //Used as the delimiter while searching to the left of the current index; right boundary of previous collection enclosure 
		
		//Iterate over each element of the input
		for(int i=0, len=input.length; i<len; i++)
		{
			int lIndex = -1, rIndex = -1, curValue = input[i], curMaxValue = -1;
			
			//Initialize the current max value to the value of current element
			curMaxValue = input[i];
			
			//Iterate to the left of current index i
			for(int j=i-1; j>=prevRIndex; j--)
			{
				if(curMaxValue > input[j])
					continue;
				
				if(curMaxValue == input[j] && i-j > 1 && lIndex == -1)
					lIndex = j;
				
				if(curMaxValue < input[j])
				{
					lIndex = j;
					curMaxValue = input[j];
				}
			}
			
			//Initialize the current max value to the value of current element
			curMaxValue = input[i];
			
			//Iterate to the right of current index i
			for(int k=i+1; lIndex > -1 && k<len; k++)
			{
				if(curMaxValue > input[k])
					continue;
				
				if(curMaxValue == input[k] && k-lIndex > 1 && rIndex == -1)
					rIndex = k;
				
				if(curMaxValue < input[k])
				{
					rIndex = k;
					curMaxValue = input[k];
				}
					
			}
			
			//Measure the water collected, if we find a enclosure enclosed
			if(lIndex > -1 && rIndex > -1)
			{
				//Identify the smaller of #s at beginning or ending of the collection enclosure
				int minValue = input[lIndex] < input[rIndex] ? input[lIndex]:input[rIndex];
				
				System.out.print("Water gets stored between index " + lIndex + " and " + rIndex + ", at ");
				
				for(int start = lIndex + 1; start < rIndex; start++)
				{
					if(start > lIndex + 1)
						System.out.print(", ");
					
					System.out.print("index " + start + " - " + (minValue - input[start]));
					totalQuantity += minValue - input[start];
				}
				
				//Continue searching from the end of the current enclosure
				i = rIndex - 1;
				
				//Set the end of this enclosure as the boundary for next enclosure's start
				prevRIndex = rIndex;
				
				System.out.println();
			}
		}
		
		System.out.println();
		System.out.println("Total quantity stored - " + totalQuantity);
	}
}

- ruharish October 25, 2013 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

Too many for loops buddy.

- Stupid Developer October 25, 2013 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

Seems as simple as traversing left to right and recording a "potential store" based on when the bars start decreasing. When you next get to a bar the same height or higher than the previous highest, save the store as fact and start with that next height. Repeat. If you end without recording a potential store as fact, discard it because that would be a hill running off to the end.

Working code, O(n):

<?php ;

$bars = array(4, 1, 6, 4, 1, 6, 3, 1, 4, 6);

$lastMax = 0;
$potentialStore = 0;
$finalStore = 0;
foreach ($bars as $height) {
  //End of trough?                                                                                                                                                                                      
  if ($height >= $lastMax) {
    $finalStore += $potentialStore;
    $potentialStore = 0;
    $lastMax = $height;
  }

  //Not the end.  Do we have a last max or are we in initial runoff?                                                                                                                                    
  if (!	$lastMax) continue;

  //We're in a trough.  Add the diff                                                                                                                                                                    
  $potentialStore += $lastMax -	$height;

}

echo "\n\n", $finalStore, "\n\n";

?>

- jvermette October 25, 2013 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

Hey I just tooked your code and tried to test it with this input {9, 4, 1, 6, 4, 1, 6, 3, 1, 4, 6, 8}. However it was not giving the correct value. Since am not a PHP developer I might have done some mistake in copying pasting or might be some syntax misunderstanding. Can you just run your code against these values and let me know the result.

Thanks.

- Stupid Developer October 25, 2013 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

Ah you're right. It breaks when there's a max which never gets caught by an equal or greater max on the right but which has mini-troughs in it. I don't think I have time to adjust, but I'm sure it could be fixed in the same time bound by using a stack for $lastMax instead of a simple value. The concept remains the same.

- jvermette October 26, 2013 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

private void CalculateStorage(int[] bars)
        {
            int waterStored = 0;
            int maxValue = bars[0];

            int possibleWaterCanBeStored = 0;
            int lastSuccessfullWaterStoredAt = 1;

            bool equalOrGreaterBarEncountered = false;
            int lastBarValue = 0;
            for (int i = 1; i < bars.Length; i++)
            {
                if (maxValue > bars[i])
                {
                    possibleWaterCanBeStored += (maxValue - bars[i]);
                }
                else
                {
                    maxValue = bars[i];
                    waterStored += possibleWaterCanBeStored;
                    possibleWaterCanBeStored = 0;
                    equalOrGreaterBarEncountered = true;
                    lastSuccessfullWaterStoredAt = i;
                }
                lastBarValue = bars[i];
            }

            if (!equalOrGreaterBarEncountered)
            {
                possibleWaterCanBeStored = 0;
                for (int i = lastSuccessfullWaterStoredAt; i < bars.Length; i++)
                {
                    if((lastBarValue - bars[i] ) > 0)
                    possibleWaterCanBeStored += lastBarValue - bars[i];
                }

                waterStored += possibleWaterCanBeStored;
            }

            Console.WriteLine("Water that can be stored is " + waterStored);
        }

- Stupid Developer October 25, 2013 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

Two auxiliary cumulative arrays, say cumArrLeft[] & cumArrRight[] can be used to store the *indices* of maxHeight seen so far from the left and from the right respectively

Supposing we have the routine: computeWaterQuantity(startPos, endPos)

0. Start from the middle(say, mid) of the array.
1. leftMax = cumArrLeft[fmid]
2. rightMax = cumArrRight[mid + 1]
3.totalWaterQty = computeWaterQuantity(leftMax, rightMax)
4. if leftMax == 0 go to Step 8
5. newLeftMax = cumArrLeft[leftMax -1]
6. totalWaterQty += computeWaterQuantity(newLeftMax, leftMax); leftMax = newLeftMax;
7. goto step 4
8 if righttMax == (size_of_the_array - 1) go to Step 12
9. newRightMax = cumArrRight[rightMax +1]
10. totalWaterQty += computeWaterQuantity(rightMax, newRightMax); rightMax = newRightMax;
11. goto step 8
12 Stop

- Murali Mohan October 29, 2013 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

Here's my version of the answer. It uses two arrays, storing, for each x-coordinate, the max left and max right. For each x-coordinate, it compares the left and right max, whichever is smaller must be the shorter side of the current container, it then adjusts the sum accordingly.

public static int water_logger(int[] graph){
		int[] rmax = new int[graph.length];
		int[] lmax = new int[graph.length];
		rmax[graph.length - 1] = graph[graph.length - 1];
		lmax[0] = graph[0];
		
		int sum = 0;
		
		for(int i = graph.length - 2; i >= 0; i--){
			rmax[i] = Math.max(rmax[i+1], graph[i]);
		}
		for(int i = 1; i < graph.length; i++){
			lmax[i] = Math.max(lmax[i-1], graph[i]);
		}

		for(int i = 0; i < graph.length; i++){
			sum += (lmax[i] <= rmax[i])? lmax[i] - graph[i] : rmax[i] - graph[i];
			
		}
		return sum;
	}

It should run in O(n) (three for-loops going O(n) each, but no nested loops, no complex operations, etc)

It is able to detect multiple "bucket" regions, i.e.
{0 1 2 1 0 1 5 3 2 3 5 3 1 3 0}
sum for each is, in array form
{0 0 0 1 2 1 0 2 3 2 0 0 2 0 0}
totaled:
13

- Javeed November 03, 2013 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

Good solution man
Thanks

- ZB April 04, 2015 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

Good solution
Thanx

- ZB April 04, 2015 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

public class WaterStore {
	public static void main(String[] args){
		int[]arr = {8 , 7 , 6 , 5, 1, 1, 2};
		int water = 0;
		
		int i = 0;
		while(i<arr.length-1){
			int k=i+1;
			if(arr[i]> arr[k] && k < arr.length-1 ){
				while( !(arr[i]<=arr[k]) && k < arr.length-1 ){
				   k++;
				};
				if( arr[i]<=arr[k]){
	//				System.out.println(" k "+ k + " i " + i);
					int j = i;
					while(j<k-1){
	//					System.out.println(" arr[j] "+ arr[j] + " arr[j+1] " + arr[j+1]);
						
						water = water + (((arr[i]-arr[j+1]) >=0 ? (arr[i]-arr[j+1]) :0 ));
	//					System.out.println(" water " +  water);
						
						j++;
					}
			     }
			}
			i=k;
			
		}
		System.out.println( water);
		
		
	}

}

- shatarupa.majumdar January 21, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

public void water(){
		int[] ar = {4, 1, 6, 4, 1, 6, 3, 1, 4, 6};
		int i=0 ;
		
		int res = 0, max =0, last = Integer.MIN_VALUE;
		Stack<Integer> st = new Stack<Integer>();
		max = ar[0];
		st.push(max);
		
		while(i<= ar.length-1){
			if(max >= ar[i]){
				st.push(ar[i]);
				i++;
			}else{
				while(!st.isEmpty()){
					res = res+max-st.pop();
				}
				max = ar[i];
				st.push(ar[i]);
				i++;
			}
		}
		
		while(!st.isEmpty()){
			int temp = st.pop();
			if(temp >= last)
				last = temp;
			else{
				res = res+last-temp;
			}
		}
		
		System.out.println("Water stores is "+res);
	}

- Delta February 07, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

package interv.eBay;

public class WaterStoredCalculator {

public static void main(String[] args) {
// TODO Auto-generated method stub
int[] input = { 4, 1, 6, 4, 1, 6, 3, 1, 4, 6 };
WaterStoredCalculator wSC = new WaterStoredCalculator();
wSC.findStoredWaterQuantity(input);
}

private void findStoredWaterQuantity(int[] input) {
// TODO Auto-generated method stub
int[] lArray = new int[input.length];
int[] rArray = new int[input.length];
int currentMax;
int totalWaterStored = 0;
currentMax = input[0];
int i;
for (i = 0; i < rArray.length; i++) {
lArray[i] = currentMax - input[i];
if (input[i] > currentMax)
currentMax = input[i];
}
i--;
currentMax = input[i];
for (; i >= 0; i--) {
rArray[i] = currentMax - input[i];
if (input[i] > currentMax)
currentMax = input[i];
}
for (int j = 0; j < rArray.length; j++) {
totalWaterStored += Math.max(0, Math.min(rArray[j], lArray[j]));
}
System.out.println("Total water stored " + totalWaterStored);
}

}

- sLion August 17, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

static int min_val(int a, int b)
{
    if(a<=b) 
        return a;
    else
        return b;
}

int how_many_units( int arr[], int size )
{
    int *left_array;
    int *right_array;
    left_array = (int *)malloc(sizeof(int)*size);
    right_array = (int *)malloc(sizeof(int)*size);
    assert(left_array);
    assert(right_array);
    int i;
    
    left_array[0] = -1;
    for(i=1; i<size; i++)
    {
        if(arr[i] >= left_array[i-1])
            left_array[i] = arr[i-1];
        else
            left_array[i] = left_array[i-1];
    }

    right_array[size-1] = -1;
    for(i=size-2; i>=0; i--)
    {
        if(arr[i] >= right_array[i+1])
            right_array[i] = arr[i+1];
        else
            right_array[i] = right_array[i+1];
    }

    int sum=0;
    for(i=1; i<size-1; i++)
    {
        sum += min_val(left_array[i], right_array[i]) - arr[i];
    }
    
    return sum;
}

- P.B.SureshBabu February 13, 2018 | Flag Reply
Comment hidden because of low score. Click to expand.
-1
of 5 vote

Water is stored at a point if there are buildings at both sides of it.

If for some X, we know the max. height of the building to the left and the right and the height of the building there, we can calculate the height of water at X.

Let us take the case height = {3, 2, 1, 5}. Let's make two arrays Lmax and Rmax, which store the max. height of the building to the left and to the right. We can do this in O(n):

Lmax = {0, 3, 3, 3}
Rmax = {5, 5, 5, 0}

Now water_height[i] = max(0, min(Lmax[i], Rmax[i])-height[i])

So water_height = {0, 1, 2, 0} and thus total water height = 3

Total time complexity = O(n)
Total space complexity = O(n)

- anotherguy October 25, 2013 | Flag Reply
Comment hidden because of low score. Click to expand.
-1
of 3 votes

How it will work for more complex example? Let's say {4, 1, 6, 4, 1, 6, 3, 1, 4, 6}, the result should be 14.

- anonymous October 25, 2013 | Flag
Comment hidden because of low score. Click to expand.
Comment hidden because of low score. Click to expand.
0
of 2 votes

The way I read {4, 1, 6, 4, 1, 6, 3, 1, 4, 6}, total water stored is 20. (zero indexed) spot 1 stores 3, spot 3 stores 2, spot 4 stores 5, spot 6 stores 3, spot 7 stores 5, spot 8 stores 2. 3+2+5+3+5+2=20. I think this solution doesn't account for multiple troughs.

Assuming I understand the problem correctly -- I just submitted a very small O(n) solution that handles that.

- jvermette October 25, 2013 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

I agree with jvermette. 20 is the correct answer.

- Stupid Developer October 25, 2013 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

Above one liner looks familiar :) This question was asked a few weeks ago.
Except LMax need not be an array (you can update it on the fly).

All you really need is ~1n storage and ~2n passes.

- S O U N D W A V E October 26, 2013 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

My algorithm is correct.

@Nitin R. Gupta: the sum of{0,3,0,2,5,0,3,5,2,0} is 3+2+5+3+5+2 = 20, not 15.

@jvermette: it handles multiple troughs as well

- anotherguy October 26, 2013 | Flag
Comment hidden because of low score. Click to expand.
-1
of 1 vote

Here's my Java solution. It iterates over the array and keeps a running maximum of the total water collected. It divides everything into smaller buckets which can contain water. As soon a bucket was found the water is accumulated. There a few test cases I`ve run and they worked as expected.

public class Buckets {

        public static void main(String[] args) {

                int[] graph = {5,4,3,2,1};
                int[] graph1 = {1,2,3,5};
                int[] graph2 = {2,1,2,1,2,1,2,0,2,3,4,5};
                int[] graph3 = {4,1,6,4,1,6,3,1,4,6};

                Buckets buckets = new Buckets();

                printResult(graph, buckets.getTotalWater(graph));
                printResult(graph1, buckets.getTotalWater(graph1));
                printResult(graph2, buckets.getTotalWater(graph2));
                printResult(graph3, buckets.getTotalWater(graph3));
        }

        static void printResult(int[] graph, int total) {

                for(int index = 0; index < graph.length-1; index ++) {
                        System.out.print(graph[index]);
                        System.out.print(", ");
                }
                System.out.println(graph[graph.length-1]+";\nTotal water contained is: " + total);
        }

        public int getTotalWater(int[] array) {
                int totalWater = 0;
                if(array != null) {
                        int currentMaxHeight = array[0];
                        int currentBucketWater = 0;
                        int head = 0;

                        for(int index = 1; index <array.length; index++) {
                                if(array[index] >= currentMaxHeight) {
                                        currentMaxHeight = array[index];
                                        totalWater += currentBucketWater;
                                        currentBucketWater = 0;
                                } else {
                                        currentBucketWater += (currentMaxHeight - array[index]);
                                }
                        }
                }

                return totalWater;
        }
}

- pittbull October 26, 2013 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

It will fail for the cases (9, 4, 1, 6, 4, 1, 6, 3, 1, 4, 6, 8) & { 8 , 7 , 6 , 5, 1, 1, 2 }

- Stupid Developer October 26, 2013 | Flag


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