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

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

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 ;)

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

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

Too many for loops buddy.

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";

?>``````

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

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.

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

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.

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

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

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

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

Good solution man
Thanks

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

Good solution
Thanx

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);

}

}``````

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

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

}

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

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)

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

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.

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

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.

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

I agree with jvermette. 20 is the correct answer.

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

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.

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

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

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;

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

}
}``````

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

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 }

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.