The Skyline algorithm for packing 2D rectangles

Great writeup. Sucks when this gets asked in a coding interview to be solved in 15min :)

To be fair, in an interview context they’re probably looking for what you would implement in the mvp just to avoid getting blocked, and a brief acknowledgement that it’s an academic problem and once you have data to understand it better you’ll select and implement an appropriate algorithm after design review with colleagues.

In theory, yes, but in practice...

I’ve interviewed with several companies that asked me this specific question [1], including Facebook, ByteDance, LinkedIn, and a particular team at Apple (not my current team). The interviewers, perhaps somewhat optimistically [2], expected a fully working solution. They gave me about 40 minutes—more than the 15 minutes mentioned in the original comment—but I definitely needed the first 10-15 minutes just to get a brute-force solution running. The rest of the time was spent refining the approach and addressing 1-2 additional requirements to pass a set of visible tests.

It was challenging, but not in a traditional engineering sense. It felt more like an ACM competition [3].

Fortunately, programming skills aren’t the only thing companies assess these days. With over a decade of work experience, behavioral (experience-based) interviews now play a larger role in the final hiring decision. That said, depending on who conducts the technical portion of the interview, you could still be rejected if your code doesn’t work.

[1] https://leetcode.com/problems/the-skyline-problem/descriptio...

[2] Them, being so young (<10 YoE), consider LeetCode a panacea

[3] https://en.wikipedia.org/wiki/Competitive_programming

Blah, that sucks. I happily did a take home assignment recently for an interview and enjoyed digging into it, but if asked to solve such a generic brain teaser under a time constraints I’d probably just walk out— at 38 I’m too old to be playing those games.

thanks for linking that leetcode link; the entire time i've been reading about it i thought it was a separate programming language used for these "challenges" at workplaces. I'm not a programmer by trade so i was surprised to see python is usable, too.

Sorry for asking you (i'm not, just shouting into the ethernet) - when people say they take a few months off to "grind leetcode" do they just go through the problems on that site? When an employer issues a challenge it's going to be exactly worded as when you practiced? like, the potential employer in your experience gave you that URL and said "go"?

Not OP but yeah, they mean to work your way through the problems there and yes most "normal" languages are fine, python, js, C, java, etc.

In my experience they won't just give you an URL, it'll just be a problem in the style of the ones there. Thing is, once you've done a few of them you'll see that there's only a set of algorithms that usually apply. The setting and input will vary but in the end you can reduce it to a known algorithm or technic so it's more about finding which one fits and can solve the problem

“This exact problem” isn’t the packing problem discussed in the OP, right? It’s a different problem about taking the union of overlapping rectangles with their bottom edges at the same vertical position.

Reading just the headline, I thought that's what this post was referring to. I used to give the Skyline overlapping rectangle problem at Google for several years, until it got banned. I'd say that with appropriate nudges, most candidates were able to get through it in an hour. I don't know how things have changed since 2015, but this was all on a whiteboard, so at least there wasn't time wasted fighting a compiler.

Then again, my lifetime stats on interviewing at Google, measured by interview scores vs eventual offers extended was somewhere between noise and a slightly negative correlation, so I never did figure out why they let me interview at all! (I think I'm too nice in interviews, because I want everyone to succeed, and asking myself "if this person were on my team, would I be as happy to collaborate with them as I would be with Nick? Really?" only goes so far in counteracting that.)