101–110 of 134 posts
Random question but why is it called memoization instead of just caching? Isn't it the same thing? For some reason I never ran across the word memoization when I was doing CS a number of years ago.
The term is over 50 years old: https://en.m.wikipedia.org/wiki/Memoization#Etymology Probably been used in CS longer than “caching”.
Earlier quoted context omitted.
This isn't a brain teaser, they actually correlate with on-the-job performance. When I worked at Google I looked up their internal reports on the subject and they showed that the score people got on these algorithm interviews correlated pretty well with their performance ratings after they got hired. In other words the group of people who got hired even though they had low scores performed significantly worse than th…
Maybe for Google-type/scale problems, but I'd say that the engineers I've worked with and hired for "normal" software jobs (e.g. here's a boring business domain, make it CRUD, make an API, make a UI for it) - there is almost an inverse correlation between being a CS/algorithm genius and being happy/successful at these everyday roles. From observation, many super sharp CS people very frequently want to write systems f…
There is an argument to be made here about career and skill growth. I left my previous job which was basically business-logic-to-CRUD-in-a-complex-domain simply because I stopped growing there. The moment you stop growing in software industry is the moment your career dies, at least that's my perception at this time given my personal experiences.
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 autho…
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.
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.
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 autho…
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.
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.
Earlier quoted context omitted.
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.
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…
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.
Earlier quoted context omitted.
> and if it takes 5 minutes to discuss with a non-chess-playing candidate how a knight moves If it takes 5 minutes to explain how a knight moves I think that person might not be Google material...
We've already established that there are at least four different people in this thread alone who cannot clearly explain how a knight moves.
For anybody wondering, this is a disguised 'count number of walks of length k on a graph' problem. On a more general note, anytime a problem admits a dynamic programming solution, there almost always is a graph based approach.
Whoa, this is something new for me. For e.g. how would you transform calculating nth fibonacci number into a graph problem?
This problem was used at my work years ago. We now have a hiring guild dedicated to making a better interview process. Multiple people said they were originally in the guild to prevent this problem from being used haha.
Earlier quoted context omitted.
The junior and the senior aren't competing for the same job though, this just checks that you still remember the theory you learned in college. And no, just because you are senior doesn't mean that you get a free pass forgetting everything you learned in college. I haven't practiced problems like this in over 5 years and I still ace them.
> this just checks that you still remember the theory you learned in college. Sure, but not everyone went to college or studied computer science / math. This seems like one of those problems that's really just testing a very specific type of preexisting knowledge.