One of my favorite anecdotes, that I read on hn and unfortunately didn't save, is that a constant space algorithm for loop checking in a linked list was an open question for a long time. The rabbit and hare algorithm was novel enough that it was first published by Knuth in 1969.
So if you're asked that question in an interview, it's only checking if you've heard the answer. Because you almost certainly aren't going to come up with it on the spot.
That said, if you want to work at goog/fb/amazon/et al, you have to study, and that's a common dp problem. Put in your 100 hours of studying and you'll do fine. And before you grump at me, that's not an endorsement of this (I think it's quite silly), but we all know the deal. So stop whining and study before your interview, or don't bother interviewing with the well known list of companies that love algorithm bingo.
Knuth's paper gave incorrect credit to an earlier paper that did not mention the algorithm.
The tortoise and hare algorithm is so simple that it was never published as a novel result, it was never an "open question". It was just something people figured out when it came up.
If you're not interested in the algorithm bingo as /u/x0x0 put it (great description, by the way), then I would highly suggest focusing more on working at smaller companies that need intelligent people with experience. They don't care about people who can sort things in polynomial time or whatever; they need people who can hit the ground running and really help them out. And I'm not necessarily talking about the 3-person mom and pop shop down the street. Even companies with hundreds of people are often starving for good employees.
FB doesn't "need" people who can actually solve problems like these with a clock ticking (because basically no one can) -- or even people capable of regurgitating the answers. They're just mindlessly following the fad like everyone else -- only they seem to think they're being clever and taking it "up to the next level" by having people live-code NP-complete problems in front of a recruiter.
Yeah, these kinds of interviews are epically stupid. What's worse is that practices like this and similar ones from places like Google, etc. give credibility to dumb things that make for a terribly inefficient (at best) or outright toxic (at worst) job marketplace.
Other places follow the same practice because they hold these market leading companies up on a pedestal, which is tantamount to argument by appeal to authority.
But, but, but all the top companies do this and they're successful!!! Yeah, well they're successful despite stupid practices like this, not because of them. Their business models are so resilient that they can tolerate a whole shitload of failures in other aspects or dimensions and still come out on top.
Do you think that the people who invented PageRank and planet scale social graphs and virtualized server hardware and advertising auctions and personalizatio models were not capable of solving computer science homework problems?
1. I'm nearly 100% certain they're not hiring for the position of "Co-founder".
2. I'm nearly 100% certain they couldn't derive, in real-time and in-scope of the interview, the solution to a PhD thesis problem they had never heard of before, nor previously been given the answer to simply to recall it later.
3. I'm nearly 100% sure that if they can do #2, then they should be interviewing for #1 someplace else, not trying to become employee # X-thousandth-and-one in a mature enterprise, or that they'd never be asked these questions to begin with because they'd be interviewing for a job that was directly related to and based on their own pre-existing published academic works.
I'll start to believe that these companies are pioneering best-practices around hiring when their frontline recruiters are psychiatrists and psychologists who specialize in proficiency assessment and personality profiling.
When you've got 1000s of decent people applying you can't have enough half-decent sieves. You don't care about the false negatives, you only want to avoid false positives.
The people that are hurting themselves are companies applying these methods to small applicant pools.
You don't care about the false negatives, you only want to avoid false positives.
You might want to re-examine this assumption more critically. With a high enough false negative rate, you end up burning out your candidate pool (and severely deterring those who "failed" from every applying again).
Google themselves discovered this a few years ago when they did a fundamental re-evaluation of their hiring process -- having come to the conclusion that their previous filtering methods were woefully ineffective at predicting actual on-job performance. And specifically went back to their databases to try to re-recruit many of the people who had been "flushed" by the earlier incarnations of their filtering process.
The problem was to write a solution to solve the subset sum problem in polynomial time. The instructions specifically did not want the exponential time algorithm. After playing with the problem for a few minutes, I realized that the necessary solution involved dynamic programming.
Do FB engineering types really think that anyone -- save for mutants like von Neumann and Ramanujan -- is genuinely able to solve problems like these from scratch, having never seen them before, in such ridiculously short time frames? Being as typically they were kicking around as open problems (either in the literature or folklore) for years and years before the optimal solutions were found?
Or that such "tests" are a measure for anything besides rote memorization skills -- and the willingness to suck it up, and cram it out, week after week, specifically for otherwise pointless regurgitation sessions like these?
They filter for having randomly encountered this exact problem before. Now, the complexity of the randomness goes way down if the candidate encountered an educational program in which this problem is known to have been exposed.
So it's more like a "clubhouse handshake" than anything else, IMO.
subset-sum is a computer science undergraduate homework problem -- if you have learned dynamic programming, and paid attention to the frequent reminders that software companies like to ask about dynamic programming in interviews, it is a straightforward problem to solve in 30minutes.
You may argue that undergraduate computer science is not relevant to a software engineering job, and you might be right, but it's a relatively level playing field. What would you recommend instead? Ask a candidate something more job-specific, to build something you are currently working on, that tests for familiarity with the specific domain and toolset you happen to be using?
I'm a hacker. Never did comp sci. I hate questions like this, but my employer asks a lot like them. I've seen qualified applicants rejected because they couldn't do this. AFAICT, these questions are appropriate if you're hiring people who write algorithm-heavy code a lot. It doesn't tell you much at all for hackers who churn out lots of systems code, or frontend code.
It selects for people who learned how to do dynamic programming. Great technique, but I'd say that the vast majority of programming at Facebook, Google, or Microsoft doesn't involve writing dynamic programming algorithms (or really any algorithms) from scratch.
What I want to see in a candidate is their ability to reason in areas that it's reasonable to expect them to be able to extrapolate. If somebody doesn't know dynamic programming, they can still be a great programmer, but they're going to flop this problem. Dynamic programming is nonobvious.
That said, anybody applying for these kinds of jobs should research the kinds of questions asked and I think DP is so commonly asked about that knowing when to apply it is a practical way to be prepared.
If I wanted to give applicants a hard time, I'd give them a few hints about genetic recombination and then expect them to derive the Holliday Junction. After all, every undergrad biologist learns about it and it's "obvious" if you know how DNA base pairing works, but I guarantee that almost nobody who didn't study biology would infer its existence as a solution to the recombination problem.
What does this even prove an employee is able to do? Read other people's work?
I'm 100% sure that the people who came up with these solutions in the first place didn't take only 20 minutes.
It's also stupid that you can't look up the answer. In the real world I'd rather have an employee who can use google then one that takes 30 hours to find a solution to something complicated.
If that's what it takes to play with the "big boys" as you say then count me out.
I'm not interested in showing solutions for other people problems, I'm interested in finding solutions to problems I need to solve. Problems that might have never been solved before.
I want to think outside of the box and work on providing real world solutions, writing as clean code as I can, and being able to work with others through many revisions of our projects.
I don't want to work some place where I am meant to parrot back information I found from somewhere else.
I wouldn't call this bizarre; I'd call it sadly typical. "Write down things that were publication-worthy 40 years ago in a nearly impossible amount of time " is a very common interview technique these days. Even companies that know better do it. And, nobody interviews in a manner other than "write code, under pressure, with someone looking over your shoulder," even if they're not using absurdly hard DP problems.
The programming problem was a red herring. The interviewer and the screenshare was testing to see if he was clever enough to use his phone to cheat, to see if he had the mobile-first mentality needed in the modern industry.
Well, my feeling is that no programmer worth their salt has only one computer. I have 4 within easy reach at almost any time. :) I guess if you can't "cheat" on this test you don't deserve to get the job.
I had an interview once where the hiring manager asked me to estimate how many gas stations were in the US. I'm certain this was inspired by similar tech firm interviews but I just remember thinking afterwards how hilarious that was as a filtering criteria. Incidentally I didn't pursue the job because my would be manager kept using the word 'retarded' to describe things and I think people with any common sense should know better than that...
They're essentially essay questions- come up with reasonable-enoguh assumptions and get on with business.
We don't do a -ton- of stuff like that, but I've found that if you can't estimate with any rationale, you're probably just not very good at whatever domain you're asked to deal with.
For example, 'what sort of architecture are we going to use to make this system', 'how many simultaneous users are we expecting', 'how many requests per second can we handle given this hardware', 'how much memory do we really need- if we quadrupled it, what would that get us', etc.
Also- if a person locks up when they're thrown "How would you move mt fuji", there are going to be a lot questions that I'd be concerned about getting answers out of you for...
For a Sr or higher person, I'd hope to get some reasonable answers.
You don't feel that it's appropriate to ask a "Sr or higher" candidate questions such as:
"'how many requests per second can we handle given this hardware', 'how much memory do we really need- if we quadrupled it, what would that get us', etc," ?
In addition- do you feel it's reasonable for a "Sr or higher" candidate to lock up (ie- stammer, not be able to come to any sensible conclusion)if one was to be asked a question where they have to use the same tools to answer those questions above when asked a question not in their domain- for example, 'how many pianos tuners are likely to be in this area'?
I'm not arguing in favor of non-domain experience questions like mt fuji or piano tuners- but I can't see hiring a Sr who can't tell give me some Fermi question approximations about how many servers we need.
Maybe I don't know what a Sr is supposed to be capable of doing?
It's quite common at the major companies to ask a question where the true solution is NP-whatever, but for which a "trick approximation" can get you nlogn solution. If you know the trick, it's easy. If you don't know the trick and figure it out in 30 minutes, you're a genius. If you don't know the trick and don't figure it out in 30 minutes, the interviewer knows nothing at all abiout your ability to contribute to the company.
I recently did a remote interview via webex (not with FB, but with a big-ish tech company) so they could see my screen. It was for a full-stack-ish type job, although they asked me to do some questions in javascript. They said to "do what you normally do."
So I switched screens and googled it. Same for the docs for a few libraries that made things work (like the python csv module).
I not only got an offer, but I was told right up front "your google fu is strong."
I'd almost want to be looking for someone who does research on these problems. Reinventing the wheel is the classic engineering mistake.
I created some real world interview coding questions based on the work we were doing at a former job. My questions were rejected because the other engineers couldn't answer them because they were too "front-end" in that it required asynchronous programming. But they still got to ask their obscure CS college homework questions despite we never needed those skills.
It confirmed my suspicions of ego is why these questions are asked so often.
35 comments
[ 4.2 ms ] story [ 68.0 ms ] threadSo if you're asked that question in an interview, it's only checking if you've heard the answer. Because you almost certainly aren't going to come up with it on the spot.
That said, if you want to work at goog/fb/amazon/et al, you have to study, and that's a common dp problem. Put in your 100 hours of studying and you'll do fine. And before you grump at me, that's not an endorsement of this (I think it's quite silly), but we all know the deal. So stop whining and study before your interview, or don't bother interviewing with the well known list of companies that love algorithm bingo.
Facebook is looking for (Devs Who Can Implement CS Algorithms) ∩ (Devs who can game the system)
The second criteria is arguably more important when working for FB, than the first.
The tortoise and hare algorithm is so simple that it was never published as a novel result, it was never an "open question". It was just something people figured out when it came up.
https://en.wikipedia.org/wiki/Cycle_detection#Tortoise_and_h...
Other places follow the same practice because they hold these market leading companies up on a pedestal, which is tantamount to argument by appeal to authority.
But, but, but all the top companies do this and they're successful!!! Yeah, well they're successful despite stupid practices like this, not because of them. Their business models are so resilient that they can tolerate a whole shitload of failures in other aspects or dimensions and still come out on top.
2. I'm nearly 100% certain they couldn't derive, in real-time and in-scope of the interview, the solution to a PhD thesis problem they had never heard of before, nor previously been given the answer to simply to recall it later.
3. I'm nearly 100% sure that if they can do #2, then they should be interviewing for #1 someplace else, not trying to become employee # X-thousandth-and-one in a mature enterprise, or that they'd never be asked these questions to begin with because they'd be interviewing for a job that was directly related to and based on their own pre-existing published academic works.
I'll start to believe that these companies are pioneering best-practices around hiring when their frontline recruiters are psychiatrists and psychologists who specialize in proficiency assessment and personality profiling.
The people that are hurting themselves are companies applying these methods to small applicant pools.
You might want to re-examine this assumption more critically. With a high enough false negative rate, you end up burning out your candidate pool (and severely deterring those who "failed" from every applying again).
Google themselves discovered this a few years ago when they did a fundamental re-evaluation of their hiring process -- having come to the conclusion that their previous filtering methods were woefully ineffective at predicting actual on-job performance. And specifically went back to their databases to try to re-recruit many of the people who had been "flushed" by the earlier incarnations of their filtering process.
Do FB engineering types really think that anyone -- save for mutants like von Neumann and Ramanujan -- is genuinely able to solve problems like these from scratch, having never seen them before, in such ridiculously short time frames? Being as typically they were kicking around as open problems (either in the literature or folklore) for years and years before the optimal solutions were found?
Or that such "tests" are a measure for anything besides rote memorization skills -- and the willingness to suck it up, and cram it out, week after week, specifically for otherwise pointless regurgitation sessions like these?
Really now -- do they?
So it's more like a "clubhouse handshake" than anything else, IMO.
This being said, "use a table" seems a pretty obvious thing.
You may argue that undergraduate computer science is not relevant to a software engineering job, and you might be right, but it's a relatively level playing field. What would you recommend instead? Ask a candidate something more job-specific, to build something you are currently working on, that tests for familiarity with the specific domain and toolset you happen to be using?
It selects for people who learned how to do dynamic programming. Great technique, but I'd say that the vast majority of programming at Facebook, Google, or Microsoft doesn't involve writing dynamic programming algorithms (or really any algorithms) from scratch.
What I want to see in a candidate is their ability to reason in areas that it's reasonable to expect them to be able to extrapolate. If somebody doesn't know dynamic programming, they can still be a great programmer, but they're going to flop this problem. Dynamic programming is nonobvious.
That said, anybody applying for these kinds of jobs should research the kinds of questions asked and I think DP is so commonly asked about that knowing when to apply it is a practical way to be prepared.
If I wanted to give applicants a hard time, I'd give them a few hints about genetic recombination and then expect them to derive the Holliday Junction. After all, every undergrad biologist learns about it and it's "obvious" if you know how DNA base pairing works, but I guarantee that almost nobody who didn't study biology would infer its existence as a solution to the recombination problem.
I'm 100% sure that the people who came up with these solutions in the first place didn't take only 20 minutes.
It's also stupid that you can't look up the answer. In the real world I'd rather have an employee who can use google then one that takes 30 hours to find a solution to something complicated.
It would seem so. That, and a willingness to say and do whatever it takes to sit with the "big boys."
I'm not interested in showing solutions for other people problems, I'm interested in finding solutions to problems I need to solve. Problems that might have never been solved before.
I want to think outside of the box and work on providing real world solutions, writing as clean code as I can, and being able to work with others through many revisions of our projects.
I don't want to work some place where I am meant to parrot back information I found from somewhere else.
It's sick how broken tech interviewing is.
They're essentially essay questions- come up with reasonable-enoguh assumptions and get on with business.
We don't do a -ton- of stuff like that, but I've found that if you can't estimate with any rationale, you're probably just not very good at whatever domain you're asked to deal with.
For example, 'what sort of architecture are we going to use to make this system', 'how many simultaneous users are we expecting', 'how many requests per second can we handle given this hardware', 'how much memory do we really need- if we quadrupled it, what would that get us', etc.
Also- if a person locks up when they're thrown "How would you move mt fuji", there are going to be a lot questions that I'd be concerned about getting answers out of you for...
For a Sr or higher person, I'd hope to get some reasonable answers.
Am I off?
In addition- do you feel it's reasonable for a "Sr or higher" candidate to lock up (ie- stammer, not be able to come to any sensible conclusion)if one was to be asked a question where they have to use the same tools to answer those questions above when asked a question not in their domain- for example, 'how many pianos tuners are likely to be in this area'?
I'm not arguing in favor of non-domain experience questions like mt fuji or piano tuners- but I can't see hiring a Sr who can't tell give me some Fermi question approximations about how many servers we need.
Maybe I don't know what a Sr is supposed to be capable of doing?
That's what the page he linked says about this problem. Solution he linked doesn't cover case with negative numbers and is at best pseudo-polynomial.
Or is the whole post just satiric bit about the state of recruitment?
So I switched screens and googled it. Same for the docs for a few libraries that made things work (like the python csv module).
I not only got an offer, but I was told right up front "your google fu is strong."
I'd almost want to be looking for someone who does research on these problems. Reinventing the wheel is the classic engineering mistake.
It confirmed my suspicions of ego is why these questions are asked so often.