I was on the panel for interviewing software engineer candidates at a large software company where I worked earlier. I asked one junior candidate (having a few years of experience) to tell me how she would solve the set cover problem [1].
I illustrated the problem with a concrete example: a project needing to fill roles with different tech skills; there is a pool of candidates, each of whom had one or more of those skills; and the goal is to find the minimum set (i.e. number) of candidates, the union of whose skills matches the total set of skills needed for the project. (Contrived problem, of course, since just having multiple skills might not mean a candidate would have the bandwidth to use all of them in the project.)
She started out by making up an example set of skills, an example pool of candidate names and their skills, thought for a bit, and then started describing how she would solve the problem.
I asked her to stop, and then, using an OOP analogy, said something like: You are giving a solution for an instance of the problem. Can you give me a solution for the class of the problem? :) That is, give a solution in generic terms, without using a specific input data set. Don't remember whether she could do that or not. But she was quite good at all the other areas tested on, and got the job.
I didn't know the following about it before (from the Wikipedia page):
[ The set cover problem is a classical question in combinatorics, computer science and complexity theory. It is one of Karp's 21 NP-complete problems shown to be NP-complete in 1972.
It is a problem "whose study has led to the development of fundamental techniques for the entire field" of approximation algorithms.[1] ]
I was on the panel for interviewing software engineer candidates at a large software company where I worked earlier. I asked one junior candidate (having a few years of experience) to tell me how she would solve the set cover problem [1].
I illustrated the problem with a concrete example: a project needing to fill roles with different tech skills; there is a pool of candidates, each of whom had one or more of those skills; and the goal is to find the minimum set (i.e. number) of candidates, the union of whose skills matches the total set of skills needed for the project. (Contrived problem, of course, since just having multiple skills might not mean a candidate would have the bandwidth to use all of them in the project.)
She started out by making up an example set of skills, an example pool of candidate names and their skills, thought for a bit, and then started describing how she would solve the problem.
I asked her to stop, and then, using an OOP analogy, said something like: You are giving a solution for an instance of the problem. Can you give me a solution for the class of the problem? :) That is, give a solution in generic terms, without using a specific input data set. Don't remember whether she could do that or not. But she was quite good at all the other areas tested on, and got the job.