Haskell Skyline

You are right. Thank you. Going to correct this.

I too got this problem, though not at google. White-boarded it and came up with the n^2 solution.

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.

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?