back
13 comments
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.

For example, the code given appears to make

    skyline [(1, 2, 3), (2, 1, 4)]
evaluate to

    [(1,2),(3,0),(4,0)]
when if I’ve understood correctly it should be

    [(1,2),(3,1),(4,0)]
You are right. Thank you. Going to correct this.
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.
I too got this problem, though not at google. White-boarded it and came up with the n^2 solution.
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.
Here's a more or less faithful translation of the first solution to JavaScript:

https://jsfiddle.net/zhrpm8su/2/

"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
mean:

  first_half = first_n_elements(bs, length(bs) / 2)
  second_half = remove_first_n_elements(bs, length(bs) / 2)
  result = merge ((skyline(first_half), 0), (skyline(second_half), 0))
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.

Then, in merge function:

  merge ([], _) (ys, _) = ys
  merge (xs, _) ([], _) = xs
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!
Thank you! That was exactly what I was looking for, I think I can follow from here.
I wrote a really nice merge function (in Haskell) when I helped a friend prepare for an interview. Perhaps I should send it to the author.
I believe integer sorting doesn't have a lower bound of O(n log n), because you can do more with them than just comparing.
Of course. But nowadays, space complexity is more and more important, which makes every sorting algorithm that is > O(n) not sufficiently efficient.
Just to make sure, are you referring to bucket sort and similar algorithms or something else?