3 ms·

To interviewers who have given this problem: how do candidates typically perform? I would expect a lot of people to come up with some variant of an O(n^2) solu

To interviewers who have given this problem: how do candidates typically perform? I would expect a lot of people to come up with some variant of an O(n^2) solution on the spot, but probably not get much further without some help, in an interview where you realistically have ~30 min to solve a problem. Of course, this being HN, there are already several comments stating how the optimal solution is obvious.

drostie 12y ago
I'm also interested in how this varies by different languages. 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]; }); If you're lucky, they'll then say, "okay, I now need a height-stack where I can query the largest height, so..." 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); } }); (There are a couple of other ways to implement max() above, depending on style; you could use .reduce(max_fn) for example, where max_fn is Math.max truncated to exactly two arguments.) But I wouldn't expect them to come up with binary heaps a la http://eloquentjavascript.net/1st_edition/appendix2.html 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."
deleted 12y ago
[deleted]

drostie 12y ago

I'm also interested in how this varies by different languages. 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]; }); If you're lucky, they'll then say, "okay, I now need a height-stack where I can query the largest height, so..." 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); } }); (There are a couple of other ways to implement max() above, depending on style; you could use .reduce(max_fn) for example, where max_fn is Math.max truncated to exactly two arguments.) But I wouldn't expect them to come up with binary heaps a la http://eloquentjavascript.net/1st_edition/appendix2.html 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."

deleted 12y ago

[deleted]