3 ms·

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 algorith

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

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?

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