James Michael Hare

...hare-brained ideas from the realm of software development...
posts - 166 , comments - 1431 , trackbacks - 0

My Links

News

Welcome to my blog! I'm a Sr. Software Development Engineer in the Seattle area, who has been performing C++/C#/Java development for over 20 years, but have definitely learned that there is always more to learn!

All thoughts and opinions expressed in my blog and my comments are my own and do not represent the thoughts of my employer.

Blogs I Read

Follow BlkRabbitCoder on Twitter

Tag Cloud

Article Categories

Archives

Image Galleries

.NET

CSharp

Little Wonders

Little Wonders

vNext

Little Puzzlers–Largest Puddle on a Bar Chart

I like to keep my brain sharp by working on programming puzzlers. On off weeks I'm going to start posting programming puzzlers I've collected over the years. Hopefully you'll find them as entertaining as I do.

This is perhaps one of the more fun problems I’ve had to solve in an evaluation situation before.  I’m not claiming I have the optimal answer, so I’ll be curious to see what you all come up with as well!

The Problem:

Given an array of int that represents the height of bars in a bar chart, calculate the size of the largest puddle that would form if water were poured over the top of the graph. 

You may assume the following:

  • All bars have a width of 1
  • There is no extra space between adjacent bars.
  • There are no negative bars
  • The edges of the bar chart are an implicit “zero” height.

Example:

Assume you had the following array:

var bars = new [] { 10, 20, 80, 70, 60, 90, 40, 30, 40, 70 };

We would have the following bar chart with the indicated puddles forming on top:

GraphPool

Note that no water pools on the left side because there isn’t a left “wall” to hold it in.

So in this example, two pools would form: one from the 80-90 bars that hold 30 units of water, and one from the 90 bar to the 70 bar that holds 100 units of water.  Thus the largest pool size would have an area of 100.

Spoiler Alert!

Fair Warning: there may be discussion of the problem and potential solutions posted in the comments below.

Print | posted on Tuesday, April 7, 2015 1:28 PM | Filed Under [ My Blog C# Software .NET Little Puzzlers ]

Powered by: