Perhaps I’ve misunderstood the problem, but the second solution shown here doesn’t seem to be correct: it always adds a trailing 0-height entry to the skyline, yet there could be an existing building touching or overlapping the newly added building, whose height is then lost.
I was given this exact problem at a Google interview. In fact it was virtually the only high level, real code programming exercise I was asked to do in many hours of interviews.
For those of us not particularly skilled at Haskell, could you add some comments on the actual code, or at least explain some of the lines? I get the English part of the algorithm, but I don't think I'm up to speed on some of the syntax being used in your solutions.
"foldl" works like aggregation in databases. When you say "fold func init values", the result is calculated as:
result = init
for value in values:
result = func(result, value)
return result
So, "foldl add_endpoints [] bs" will translate to:
result = []
for (x1, h, x2) in bs:
result = add_endpoints(result, (x1, h, x2))
return result
If you expand the 3rd line, you get:
result = []
for (x1, h, x2) in bs:
result = result ++ [(x1, height x1), (x2, height x2)]
return result
where "++" is the list concatenation, and "height x" is a function which finds the skyline height by finding the tallest building with "x1 <= x && x < x2".
I think the 2nd solution should be easy to understand if you understand the 1st solution. Probably the only new thing is that I've sorted the buildings by height before passing them to "foldl".
In the 3rd solution, the following lines:
skyline bs = (skyline (take n bs), 0) `merge` (skyline (drop n bs), 0)
where n = (length bs) `div` 2
You may wonder what are those 0s? In the merge function I need to keep track of current height of each half, and the initial height of left and right skylines are 0.
means return the other list if any of the lists become empty. The underscores mean a variable whose value is not important for us. We don't care about the current height values here, so I've put _'s instead of real names.
Then the other cases:
merge ((x, xh):xs, xh_p) ((y, yh):ys, yh_p)
| x > y = merge ((y, yh):ys, yh_p) ((x, xh):xs, xh_p)
| x == y = (x, max xh yh) : merge (xs, xh) (ys, yh)
| max xh_p yh_p /= max xh yh_p = (x, max xh yh_p) : merge (xs, xh) ((y, yh):ys, yh_p)
| otherwise = merge (xs, xh) ((y, yh):ys, yh_p)
First case, "x > y" simply swaps the two args. This ensures that in the following cases we have x <= y.
Second case is probably easy to understand.
In third case, we know that x < y. Just before reaching x, skyline has height "max xh_p yh_p". When we reach x, height of skyline changes to "max xh yh_p". If these values are not equal, we have a height change. So we a construct a new list with head "(x, new height)" and the result of merging the rest of skylines.
If the height doesn't change, we just ignore the change at x and continue with the rest of skylines.
Upvote for a really accessible explanation. I wish I had posts like these to read when I was learning Haskell half a decade ago. You've got a knack for conveying concepts! Write some texts or at least a blog!
For example, the code given appears to make
evaluate to when if I’ve understood correctly it should be