11 ms·

The most bizarre technical interview I went on

38 points by lj3 10y ago

x0x0 10y ago
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.
- tarr11 10y ago
  I agree. This is a sort of meta-interview. 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.
- srtjstjsj 10y ago
  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. https://en.wikipedia.org/wiki/Cycle_detection#Tortoise_and_hare https://en.wikipedia.org/wiki/Cycle_detection#Tortoise_and_h...
- deleted 10y ago
  [deleted]
kafkaesq 10y ago
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? Really now -- do they?
- ArkyBeagle 10y ago
  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.
  - srtjstjsj 10y ago
    The "clubhouse" is "computer science undergraduate curriculum", which is available for free online.
    - ArkyBeagle 10y ago
      So any accredited BSCS program ia guaranteed to have this particular problem in it? This being said, "use a table" seems a pretty obvious thing.
- srtjstjsj 10y ago
  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?
shepardrtc 10y ago
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.
- kafkaesq 10y ago
  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.
  - im_down_w_otp 10y ago
    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.
    - srtjstjsj 10y ago
      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?
gravypod 10y ago
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.
- kafkaesq 10y ago
  What does this even prove an employee is able to do? Read other people's work? It would seem so. That, and a willingness to say and do whatever it takes to sit with the "big boys."
  - gravypod 10y ago
    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.
pmiller2 10y ago
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. It's sick how broken tech interviewing is.
srtjstjsj 10y ago
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.
- phonon 10y ago
  Well, Yahoo is looking for MAVENS.
- Corrado 10y ago
  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.
  - lj3 10y ago
    That actively selects for dishonest employees. Then again, it does seem to work for the financial sector.
nickpeterson 10y ago
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...
- dethswatch 10y ago
  God I love those questions. 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?
  - dekhn 10y ago
    You're off. You're confusing Fermi Problems https://en.wikipedia.org/wiki/Fermi_problem https://en.wikipedia.org/wiki/Fermi_problem with computer science algorithm approximation problems.
    - dethswatch 10y ago
      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?
cheez 10y ago
How do you solve the problem? I'm going to guess there is some ordering involved.
scotty79 10y ago
Maybe it was a trick question. Maybe he was just supposed to respond that polynomial solution doesn't exist because this problem is np-complete. 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?
- dekhn 10y ago
  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.
cbanek 10y ago
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.
bobbytherobot 10y ago
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.

38 points by lj3 10y ago

x0x0 10y ago

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.

tarr11 10y ago
I agree. This is a sort of meta-interview. 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.
srtjstjsj 10y ago
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. https://en.wikipedia.org/wiki/Cycle_detection#Tortoise_and_hare https://en.wikipedia.org/wiki/Cycle_detection#Tortoise_and_h...
deleted 10y ago
[deleted]

kafkaesq 10y ago

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? Really now -- do they?

ArkyBeagle 10y ago
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.
- srtjstjsj 10y ago
  The "clubhouse" is "computer science undergraduate curriculum", which is available for free online.
  - ArkyBeagle 10y ago
    So any accredited BSCS program ia guaranteed to have this particular problem in it? This being said, "use a table" seems a pretty obvious thing.
srtjstjsj 10y ago
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?

shepardrtc 10y ago

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.

kafkaesq 10y ago
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.
- im_down_w_otp 10y ago
  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.
  - srtjstjsj 10y ago
    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?

gravypod 10y ago

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.

kafkaesq 10y ago
What does this even prove an employee is able to do? Read other people's work? It would seem so. That, and a willingness to say and do whatever it takes to sit with the "big boys."
- gravypod 10y ago
  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.

pmiller2 10y ago

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. It's sick how broken tech interviewing is.

srtjstjsj 10y ago

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.

phonon 10y ago
Well, Yahoo is looking for MAVENS.
Corrado 10y ago
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.
- lj3 10y ago
  That actively selects for dishonest employees. Then again, it does seem to work for the financial sector.

nickpeterson 10y ago

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...

dethswatch 10y ago
God I love those questions. 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?
- dekhn 10y ago
  You're off. You're confusing Fermi Problems https://en.wikipedia.org/wiki/Fermi_problem https://en.wikipedia.org/wiki/Fermi_problem with computer science algorithm approximation problems.
  - dethswatch 10y ago
    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?

cheez 10y ago

How do you solve the problem? I'm going to guess there is some ordering involved.

scotty79 10y ago

Maybe it was a trick question. Maybe he was just supposed to respond that polynomial solution doesn't exist because this problem is np-complete. 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?

dekhn 10y ago
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.

cbanek 10y ago

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.

bobbytherobot 10y ago

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.