Ebay Interview Question
Software Engineer / DevelopersCountry: United States
Interview Type: Phone Interview
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);
}
}
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";
?>
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.
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.
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);
}
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
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
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);
}
}
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);
}
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);
}
}
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;
}
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)
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.
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.
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.
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;
}
}
- Anonymous October 25, 2013