The skyline problem
briangordon.github.io
briangordon.github.io
This problem is also known as "skyline queries"!
According to [2], author's bound O(n log(n)) is the best bound for d=2.
[1] http://en.wikipedia.org/wiki/Pareto_efficiency [2] http://pdf.aminer.org/000/211/201/on_the_computational_compl...
Of course, this being HN, there are already several comments stating how the optimal solution is obvious.
For example, a programmer decently knowledgeable in JS will probably start with the "pre-data-structure-change" solution presented in the article, because if you're pretty good with JS then you know how events work and you probably start with, "okay, I'm going to scan left to right and emit an event on each new edge; that will look like this."
var events = [];
buildings.forEach(function (x) {
events.push([x.l, 'add', x.h]);
events.push([x.r, 'rem', x.h]);
});
events.sort(function (x, y) {
return x[0] - y[0];
});
function max(arr){
return Math.max.apply(null, arr);
}
var height_stack = [], out;
out = events.map(function (e) {
var x = e[0], y = e[2], cmd = e[1];
switch (cmd) {
case "add":
height_stack.push(y);
return [x, max(height_stack);
case "rem":
height_stack.splice(height_stack.indexOf(y), 1);
return [x, max(height_stack)];
default:
throw new TypeError("No such command: " + cmd);
}
});
But I wouldn't expect them to come up with binary heaps a la http://eloquentjavascript.net/1st_edition/appendix2.html . I guess the best you could expect the candidate to do is to say, "then I Google someone who has done public-domain binary heaps and steal their code."
1. Take all the start x-coordinates of a buildings (=start events).
2. Take all the end x-coodinates of the buildings (=end events).
3. Sort all the events the by the value of the coordinate.
4. Now walk over all the events and keep count of how many there currently are (or in this case: how high the building is) by adding one for a start event and substracting one for a end event.
Personally I find that a simpler problem to visualize, however it deals with almost the same information. Rather than what height to draw, you're keeping a count of how many events are underneath. You increment at each leading "critical point" and decrement at each ending one.
The problem presented here is nice because it requires thought on both the algorithm as well as the data structure. Very nice article.
merging skylines together gets us more bang-for-the-buck. and is trivially done with scanning them from left->right, match x-coordinates, adjust heights...
all of this is just divide-and-conquer, and usual recurrence rules apply i.e. T(n) = 2T(n/2)+O(n), which means T(n) = O(n lg n)
Havent checked for correctness, but my off the cuff attempt would be to sort the left and right edges, then use a variable for the height and a stack. Proceed left to right. If I encounter a left edge and current height is lower than stack, push height on stack and update current height. If left edge lower than current, just push its value on the stack. If I encounter a right edge that matches current height pop height from stack in to current height. If right edge lower than current height, just pop the stack. The awkward case is when the left and right edges coincide.
I enjoyed the article and then came back to read the comments and found this sort of insulting.
Just because something is detailed doesn't mean that it's hand-holding. It's interesting to see how other people think.
Yup, another great interview question for your repertoire to weed people out and talk about the kinds of things that come up in the day to day of being a modern software engineer.
Or, in your mind, is the solution to every problem that a modern software engineer might encounter already found in some stackoverflow post?
On the job? Sure they do. In an interview room? That's not an adequate replication of the job environment. I am not asked to design an algorithm for a problem introduced to me 17 seconds ago and have 5 minutes to do it.
Plus, you're committing the #1 sin of interviews; that many of the people that can answer the question in an interview setting have encountered the problem before, and that's why they can answer it.
Most people with the title "software engineer" are day in, day out, faced with random debugging, tinkering with code and keeping the code-base organized as they go. Clever algorithms are not needed. Solid development skills are. Furthermore when you do run into occasional algorithm problems, it is enough for there to be people in your environment that you can turn to for that.
This is an accurate description of most of the productive colleagues that I've known over the years. I've known a lot of people who do not do well on algorithm challenges, but who I'd like to work with again because I know that they can consistently pull their weight.
But doesn't someone need to know algorithms? Well, yes. I certainly do. But it doesn't need to be everyone. In a good team, people naturally turn to the most appropriate teammate for help when they need it. So they might turn to me for algorithm questions, someone else for weird git problems, and yet another person for networking expertise. Algorithms are just one component.
But, I can see you say, all else being equal, wouldn't you prefer someone who knows algorithms? Obviously so. But algorithms are only one component of what we do. And is not always strongly correlated with everything else that we need to know, such as unit testing and writing modular code.
And here we get to the real problem. When our interview tests test something different than what we actually need, then we don't know whether we're getting the skills we need. Furthermore when that different thing is something that every other organization is also testing for (like algorithms), then we wind up both not being interested in people who have the skills we need, but we wind up in direct competition with everyone and his dog.
Therefore interviews should try to test the skills that we actually need people to use day to day. If your job does not require people to regularly write clever data structures, don't test for that. If your job requires people to lay out and modify class hierarchies for new business requirements, test for that instead.
Another unrelated problem is there is a legit observation that the most interesting jobs involve very interesting business logic and/or unusual situations. I'd much rather be programming a bubble sort on a mars rover at NASA than writing (from scratch of course?) quicksort at a corporate crud app house, despite in theory the crud app being more "elite" of an algo.
You'd be surprised how much embedded / life critical stuff is brutally brute force, and is also pretty fascinating work. Implementing a beautiful recursive algo for robot arm movement is cool, until a stack overflow kills an employee. Then its not so cool compared to brute forcing it where the employee would have lived. I heard about that one although I wasn't involved directly. (and this is bordering on hearsay so I have nothing further to say wrt that specific death)
It is a widely known "good interview question" which means it is a bad interview question.
This even makes it easy to parallize it because you can use the quick sort algorithm to split the rectangles in two non-overlapping sets and once your two cores have made the two parts of the skyline you only need to update the line between them.
Also, you end up as N^2 degenerate case if the buildings form a pyramid.
The problem becomes much more interesting when you consider optimal parallel performance. The best span you can do is log^2 n. I believe the problem can be reduced to sorting, though it is not required to explicitly sort the sequence of buildings in order to achieve the desired asymptotic performance.
Speaking of which: Given values 0 < a_i < A for some A, apply the skyline algorithm to the rectangles a_i < x < A, 0 < y < a_i. The resulting sequence of heights gives you the values a_i sorted in increasing order; thus the skyline problem cannot be solved in less than O(n log n) time.
Also, something interesting to note that I was thinking about yesterday is that you don't actually need to use an interval tree for this. You can use a range tree instead, which is simpler (to my mind). You only need an interval tree to do a certain kind of query which we never need to do:
https://briangordon.github.io/images/worstcase.svg
> n queries taking log(n) + n time each is O(n log n)
No, it's O(n^2).
But then again. If I read well, he wants to 1st sort the points, 2 iterate over them and using the heap. So we have n log n for the sort and n * n log n for the heap use.. Basically (1+n) n log n (or i'm still tired ? :-))
1. Peek the root of the heap to find the tallest rectangle in the active set. This is a constant time operation.
2. Add a new rectangle to the active set. This is a O(log(n)) operation.
3. Remove a rectangle from the active set. This is a O(log(n)) operation if you use something like a hash table to locate the element in the heap.
Each rectangle is added once (at its left edge) and removed once (at its right edge). The root of the heap is peeked on every critical point. All together, that makes the algorithm O(n log n).
Or am I missing something?
https://creative.adobe.com/products/animate
It's a really interesting tool. Here are the animation source files if you want to play around with them: