Interview Question

Country: United States

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

1)start left most
2) keep three variables: max= current highest bar, total and current which hold the final total and current temporary units
3) for each bar, adding to the current, until reaching a bar >= max, then add current to total, and reinitialize current
4)Do this until reaching the end of the graph

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

test

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

I think the intuition is that you know that 2 peaks will either be the same, the first one will be bigger than the other or the second will be bigger than the first. Keep one variable for peak1, one variable for highestPeakSoFar (hpsf)

We will iterate through the bar graph, starting with peak1 = element 0. If we encounter a peak p that ends up being greater than or equal to peak1, we will calculate the amount of water sumOfWater += (Min(peak1, p) - element). Then, we set p as peak1 and repeat the process from there. If we don't encounter a higher peak, we simply set hpsf as the highest peak we've encountered so far that is smaller than peak1. This is because this smaller peak wouldn't affect the water unless it is the final peak.

Finally, if we can't find anymore high peaks, we do the calculation with hpsf,

sumOfWater += (Min(peak1, hpsf) - element)

We are guaranteed To be done with this in 2n operations, which runs in O(n)

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

How would this work with
{5, 1, 4, 1, 3}

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

Good point.

Then basically, I'd arrange it in this way instead.
We are looking for local maxima in the array and then compare the distance between them.

``````for (int i = 0; i <bargraph.length; i++) {

if (bargraph[i-1] < bargraph[i] && bargraph[i] > bargraph[i+1]) {

//check this local max with the previous local max and find the water between them and add
}
}``````

I think this modification should work

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

{5,1,4,1,5}

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

I think the algorithm needs to be:

1: Find the first local maxima, call it "left"
2. Scan the rest of the array for either a maxima >= the left, or the highest in the array. Call it "right". If none, stop.
3. Compute water between left and right.
4. Assign right to left.
5. Goto 2

Unfortunately, this is not O(n) though! it is O(n^2). think about
{5,1,4,1,3,1,2}

This question is a pain!

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

Also, the maxima detection has to be more sophisticated than in your example. for cases like
{..., 3, 4, 4, 3, ...} and {..., 3, 4, 4, 5, ...}

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

Yeah this is the algorithm I'm thinking. but it would be O(n) because you check left and right at most twice.

So it would still be O(2n) -> O(n)

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

Like the example I gave, you might check them at most n/2 times, in the case where every other element is a descending maxima.

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

Find the bar with max heights and second max heights
Calculate water in between the two as sum of second max minus every bar heights

These two bar divided bars on three parts. Recursively, solve for bars in the left part and in the right, inclusively with dividers.
Note that after 2nd recursion and on, highest will always be on the border, so will have 2 parts, not three, without loss of generality of the recursive step.

Time complexity O(n). Even though search max will go each bar on every recursion, we only do it on just a portion of bars for which water is not counted, which reduces exponentially. Same reasoning as quickselect is O(n)

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

This is a good answer, though it can be done without recursion in O(n) as well.

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

Could you step through this with {5, 4, 1, 3, 1, 2}?

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

@Javeed agree this same logic can be well done without recursion. After first recursion, on the left it is always water on the right and step-in to the left and on the right it is always water on the left and step in to the right. So, after initial divide you can just iterate down on the left side and iterate up on the right.

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

@tjcbs2

max 5, second max 4

left:5. middle 5,4 right 4,1,3,1,2

left and middle 0 water, done.

at 4,1,3,1,2

max 4, second max 3

left:4. middle 4,1,3 right 3,1,2

left is 0 water. both middle and right have two maxes on the side so they themselves have only middle parts. first contains 2, second one, total 3

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

I think the worst case of your algorithm is when the array is sorted. It's similar to worst case of quick sort.

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

Am I the only who didn't understand this task? Are those bar vertically or horizontally aligned on the graph? What does "maximum amount of storage" mean?

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

this can be imagined as if the graph is a cross-section of some hills/mountains with rain falling on it. Where would the water collect vs where would it drain off and flow away? You want to calculate how much water is stored. Draw out a graph on paper and you can get a general idea.

a simple example:
[5,1,1,5]

this would look something like (sorry it's time for ascii art):

x x
x x
x x
x x
x x x x

water would collect in this one, you would have 8 units collected after it is done

Assume 1 unit of water is one unit of height per bar on the table (i.e. the x's in the example)

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

oops my art got butchered.

``````x       x
x       x
x       x
x       x
x x x x``````

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

and again that got messed up a bit. oh well you get the idea.

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

Got it, thanks!

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

``````public static int storedVolumeOfBarChart(int[] in) {
return calculateVolumeBetweenAnyTwoPoints(in, 0, in.length - 1);
}

private static int calculateVolumeBetweenAnyTwoPoints(int[] in, int leftPos, int rightPos) {
// "Trim" the slopes on either side
int leftCrestPos = leftPos, rightCrestPos = rightPos;
while (leftCrestPos < rightCrestPos - 1 && in[leftCrestPos + 1] > in[leftCrestPos])
leftCrestPos++;
while (leftCrestPos < rightCrestPos - 1 && in[rightCrestPos - 1] > in[rightCrestPos])
rightCrestPos--;

if (rightCrestPos - leftCrestPos > 1)
return calculateVolumeBetweenCrests(in, leftCrestPos, rightCrestPos);
else
return 0;
}

private static int calculateVolumeBetweenCrests(int[] in, int leftPos, int rightPos) {
int totalStorage = 0;

if (in[leftPos] < in[rightPos]) {
int currentPos = leftPos + 1;
int waterLevel = in[leftPos];
while (currentPos < rightPos) {
if (in[currentPos] <= waterLevel) {
totalStorage += waterLevel - in[currentPos];
currentPos++;
} else {
totalStorage += calculateVolumeBetweenAnyTwoPoints(in, currentPos, rightPos);
break;
}
}
} else {
int currentPos = rightPos - 1;
int waterLevel = in[rightPos];
while (currentPos > leftPos) {
if (in[currentPos] <= waterLevel) {
totalStorage += waterLevel - in[currentPos];
currentPos--;
} else {
totalStorage += calculateVolumeBetweenAnyTwoPoints(in, leftPos, currentPos);
break;
}
}
}

}``````

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

``````public static int storedVolumeOfBarChart(int[] in) {
return calculateVolumeBetweenAnyTwoPoints(in, 0, in.length - 1);
}

private static int calculateVolumeBetweenAnyTwoPoints(int[] in, int leftPos, int rightPos) {
// "Trim" the slopes on either side
int leftCrestPos = leftPos, rightCrestPos = rightPos;
while (leftCrestPos < rightCrestPos - 1 && in[leftCrestPos + 1] > in[leftCrestPos])
leftCrestPos++;
while (leftCrestPos < rightCrestPos - 1 && in[rightCrestPos - 1] > in[rightCrestPos])
rightCrestPos--;

if (rightCrestPos - leftCrestPos > 1)
return calculateVolumeBetweenCrests(in, leftCrestPos, rightCrestPos);
else
return 0;
}

private static int calculateVolumeBetweenCrests(int[] in, int leftPos, int rightPos) {
int totalStorage = 0;

if (in[leftPos] < in[rightPos]) {
int currentPos = leftPos + 1;
int waterLevel = in[leftPos];
while (currentPos < rightPos) {
if (in[currentPos] <= waterLevel) {
totalStorage += waterLevel - in[currentPos];
currentPos++;
} else {
totalStorage += calculateVolumeBetweenAnyTwoPoints(in, currentPos, rightPos);
break;
}
}
} else {
int currentPos = rightPos - 1;
int waterLevel = in[rightPos];
while (currentPos > leftPos) {
if (in[currentPos] <= waterLevel) {
totalStorage += waterLevel - in[currentPos];
currentPos--;
} else {
totalStorage += calculateVolumeBetweenAnyTwoPoints(in, leftPos, currentPos);
break;
}
}
}

}``````

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.