5 ms·

So here's the thing. And I know I'll get knocked to r/iamverysmart for this. It timed myself. It took less than 10 minutes from reading the problem to coding up

So here's the thing. And I know I'll get knocked to r/iamverysmart for this. It timed myself. It took less than 10 minutes from reading the problem to coding up a working dynamic programming solution (no peaking at the rest of the article). A big chunk of that was (unsuccessfully) trying to come up with a closed-form solution. I didn't get the log(n) solution until I found it existed at the bottom, but once the author mentioned it's existence, that took less than 5 minutes to figure out. I didn't code that up, though. I'm probably an above-average programmer, but I'm not a 99.99% outlier. I interviewed early Google. The questions were tough for me (much more so than this one). Things which jumped out at me: "The better the candidate, the fewer hints I tend to have to give, but I have yet to see a candidate who required no input from me at all." I read this as "We're scraping the bottom of the barrel for candidates. Our candidates are nothing like those who applied to Google circa 2000" And: "I didn’t even know it existed until one of my colleagues came back to his desk with a shocked look on his face and announced he had just interviewed the best candidate he’d ever seen." I read this as: "Our employees are dumb. In using this interview question for years, none of us ever noticed the obvious." What's going on there? I mean I can see messing up an interview question like this under the stress of an interview (I literally confused linked lists and arrays in probably my worst interview ever). But no candidate? Ever? And no employee? Come on. There's something deeply wrong at Google. It's been deeply wrong for a few years. I hope someone fixes it.

chromatin 6y ago
Likewise I was surprised at how trivial this seemed? My first solution was matrix multiplication -- I remember distinctly in undergraduate discrete mathematics learning that matrix exponentiation solved the hops-on-graph problem. I did not think to convert to binary to make logarithmic time, however.
- murgindrag 6y ago
  The "convert to binary" is a standard algorithm for modular exponentiation. Anyone who has taken a cryptography course will know it. It's not the fastest algorithm (by big-O; probably is in practice), though. You can do a matrix decomposition, exponentiate the eigenvalues, and convert back. Speed will depend on how you do the exponentiation, and that's gets into a pile of optimized numerical methods.
username90 6y ago
Note that you need to pass at least 4 out of 5 interviews, each asking about 2 questions. But yeah, you don't have to be a genius to get into Google nowadays. What you need is the creativity to solve problems you haven't seen before (which is why Google bans questions once they get out), basic algorithms skills and the programming skills to implement it at a reasonable pace.
- murgindrag 6y ago
  Yeah. I'm aware of that. It's a bunch of straightforward questions, a pretty high bar for how many you need to answer, and so it's pretty random how many of them you mess up, so it's kind of like a die roll to get a job. I had a really bad interview at a peer company once, and I'm well aware how it goes. But I kind of miss the old Google where you DID need to be a genius. I interviewed with Google probably around the year 2000, and there was a genuinely hard ball packing problem. I'm kind of curious what happened. Anyone who could answer that question would find this one trivial -- and not just the dynamic programming solution, but the O(log n) one which apparently no one at Google (or even applying to Google) noticed. What I hate about Google is that everyone there still thinks they're a genius. In 2000, it felt okay, since for the most part, they actually were. Today, it's kind of obnoxious.
  - joshuamorton 6y ago
    > But I kind of miss the old Google where you DID need to be a genius. I interviewed with Google probably around the year 2000, and there was a genuinely hard ball packing problem. I'm kind of curious what happened. Anyone who could answer that question would find this one trivial -- and not just the dynamic programming solution, but the O(log n) one which apparently no one at Google (or even applying to Google) noticed. Fwiw this is very much untrue. While this person may not have known the optimal solution, it's well documented within google. > What I hate about Google is that everyone there still thinks they're a genius. In 2000, it felt okay, since for the most part, they actually were. Today, it's kind of obnoxious. News to me ;) There are certainly places where I think Google is a world-leader. But that doesn't require or imply that everyone be a super genius.

chromatin 6y ago

Likewise I was surprised at how trivial this seemed? My first solution was matrix multiplication -- I remember distinctly in undergraduate discrete mathematics learning that matrix exponentiation solved the hops-on-graph problem. I did not think to convert to binary to make logarithmic time, however.

murgindrag 6y ago
The "convert to binary" is a standard algorithm for modular exponentiation. Anyone who has taken a cryptography course will know it. It's not the fastest algorithm (by big-O; probably is in practice), though. You can do a matrix decomposition, exponentiate the eigenvalues, and convert back. Speed will depend on how you do the exponentiation, and that's gets into a pile of optimized numerical methods.

username90 6y ago

Note that you need to pass at least 4 out of 5 interviews, each asking about 2 questions. But yeah, you don't have to be a genius to get into Google nowadays. What you need is the creativity to solve problems you haven't seen before (which is why Google bans questions once they get out), basic algorithms skills and the programming skills to implement it at a reasonable pace.

murgindrag 6y ago
Yeah. I'm aware of that. It's a bunch of straightforward questions, a pretty high bar for how many you need to answer, and so it's pretty random how many of them you mess up, so it's kind of like a die roll to get a job. I had a really bad interview at a peer company once, and I'm well aware how it goes. But I kind of miss the old Google where you DID need to be a genius. I interviewed with Google probably around the year 2000, and there was a genuinely hard ball packing problem. I'm kind of curious what happened. Anyone who could answer that question would find this one trivial -- and not just the dynamic programming solution, but the O(log n) one which apparently no one at Google (or even applying to Google) noticed. What I hate about Google is that everyone there still thinks they're a genius. In 2000, it felt okay, since for the most part, they actually were. Today, it's kind of obnoxious.
- joshuamorton 6y ago
  > But I kind of miss the old Google where you DID need to be a genius. I interviewed with Google probably around the year 2000, and there was a genuinely hard ball packing problem. I'm kind of curious what happened. Anyone who could answer that question would find this one trivial -- and not just the dynamic programming solution, but the O(log n) one which apparently no one at Google (or even applying to Google) noticed. Fwiw this is very much untrue. While this person may not have known the optimal solution, it's well documented within google. > What I hate about Google is that everyone there still thinks they're a genius. In 2000, it felt okay, since for the most part, they actually were. Today, it's kind of obnoxious. News to me ;) There are certainly places where I think Google is a world-leader. But that doesn't require or imply that everyone be a super genius.