Histogram based water volume calculation Algorithm
Here is the problem I was given to solve in an interview long time ago. During the interview – I had taken a hasty approach to solving the problem and used brute force.
However, later on I gave another good thought to the problem and found an elegant the solution using Recursive Divide and Conquer approach.
Assume you have a 3 dimensional histogram where the width of each bar is 1 unit and the depth is 1 unit too. However what varies is the height of each successive bar – depending on the data content.
If we pour some liquid into the structure what will be the volume of that liquid that can accumulate in this structure.
Here is my approach to solving this
So the input data set is a series of +ve numbers which represent the height of each bar. This is any random finite stream of +ve numbers – each of which represents the height of the bar.
Take this set of numbers and find the first 2 largest numbers.
These 2 numbers and the indexes at which they are located in the dataset represent the boundaries of 1 segment.
These 2 ends have now segmented the whole data set into 3 regions –
Example – if the index of these 2 largest elements in the whole entire data set is 12 and 20 then we divide the whole data set into 3 regions now (assuming the data set has 25 numbers)
Region 1 – (0 to 12) – inclusive
Region 2 – (12 to 20) – inclusive
Region 3 – (20 to 25) – inclusive
* Interesting thing to observe is that Region1 and Region3 include the 2 endpoints of the middle region.
Now in Region 2 – which we found just now, we apply the following steps
Here in this Region we have the 2 end points being the 1st and 2nd largest numbers in the data set.
Find the minimum of the 2 end points and the volume of this region is
Volume of Region 2 = min (numbers at the 2 endpoints)*(abs(index of endpoint 2 – index of endpoint 1)+1) –
sum( all of the bars between the 2 endpoints )
Now apply the same steps to Region1 and Region 3: So we have divided the original data set into basically 3 regions and apply the algorithm to each region recursively
Region1 now becomes the data set, similarly Region 3 now becomes the data set.
The runtime of the algorithm is log(n) base 3
= ln(n)/ln(3) ( base e )
* Attached is the python based recursive program – which computes the volume of liquid in this structure.
Here is the Python code for the above recursive algorithm
( this is not exhaustively tested program – however, I wanted to make sure my algorithm is correct on most use cases ).
This is an interesting problem where the program can be tested with a lot of very unique edge cases
python HistogramWaterContent.py 5 1 2 1 8
python HistogramWaterContent.py 6 1 8 1 2 1 5
and so on – where the numbers represent the heights of the bars