4 ms·

subset-sum is a computer science undergraduate homework problem -- if you have learned dynamic programming, and paid attention to the frequent reminders that so

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.

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.