Andrew here. Connor, thanks for releasing this on the orange site.
This story is also more fun from my position. I've been applying to internships and interviewing every week. They're mostly rejections. They're the same questions over and over with minor variation (sorry to top comment for "impersonating" your comment style). My days are deteriorating from a colorful sphere down to two points. In fact, down to two pointers, left and right, iterating over a list of heights to find how much rain water it can trap.
I'm about to repeat the experience for the 10th time and I'm 100% on autopilot. But suddenly, a man reaches out to me on email and offers me up to $80/hr to be his senior engineer. This feels sketchy, my girlfriend tells me, "you're good but let's be honest here...". Anyways, I proceed, it might just be the start of a beautiful thing. I'm asked to interview as one of our developers because English is not their best language. I'm a little bothered, but I was fine with it. But then I see the developer name: Connor Tumbleson. My laughter bursts and so does my suspicion: With a name like that, no way the guy doesn't speak good English. I look up Connor Tumbleson on linkedin, and my suspicions were proved correct. I detail everything to Connor, and now this is on the top of HN. I lost a opprotunity but gained a story of the lifetime.
> In fact, down to two pointers, left and right, iterating over a list of heights to find how much rain water it can trap.
Ah haha I hate that question
It should be banned everywhere, oh well.
I once saw a physicist (not even a coder) give a really cool answer to it though, I wish I could remember it.
I remember being asked this during my interview at Google. It was the first time I heard it and I gave an answer that iterated over the list twice. The interviewer said that it wasn't good enough and I am only allowed to iterate over it once. He didn't let me write my O(2n) solution down so he returned a strong no as feedback.
This type of interviewing style is bullshit. It means the interviewer knows a better solution that is "clever" and expects you to either have the same cleverness epiphany on the spot or to have studied this question. Neither is actually very useful as a hiring criterion.
Guy Steele gave an incredibly interesting guest talk[1] at google about four different ways to solve this exact problem, and the fact that it's an interesting enough topic for an hour long google talk should probably be a clue that you shouldn't be expected to invent the best solution on the whiteboard in 40 minutes.
Thanks for the link, that made for entertaining watching!
Curious that he gave that talk about parallelism in the end of 2015, and talked about how we'll engineer more systems to enable parallelism.
First question at the end was actually whether we can get this into existing languages because new languages are "notoriously hard to get accepted."
I'm currently learning Rust and now I'm wondering how the iterator map() and other "accumulation style" functions are implemented and whether there's a way to make these parallel, since the map() call treats things independently and a sum() could be done in the proposed tree style way.
Guess I have a piece of code to look up in the standard library :)