It's hard for me to believe that Tom hasn't ever come across the knapsack problem and a discussion of space and time complexity before, but it's clear to me that he will be productive for a bunch of things immediately, and he probably learns fast.
And Harry is undoubtedly a resource of incredible value on things that the grocery startup hasn't even considered yet; exactly the sort of senior person they're going to need.
Hiring both of them is the right thing.
I'm not sure how Dick got past the phone interview, though.
Its amazing to see people actually taking the time to read ginormous walls of text and giving feedback, so thank you!
afaik Knapsack as originally stated is integer programming ie. it operates over discrete n, and NP-hard, so for large n the compute times are prohibitive. Simplex algorithms operate over continuous n[1], so you have amortized poly or worst-case exponential big O.
In other words, if you were in a fruit market with 1000 different kinds of fruit & you were not allowed to chop a fruit ( generally the case, you can't walk into Safeway, chop up an apple & walk out with one-eighth of an apple or half a grape or quarter blackberry ), then you'd have Knapsack, & there'd be no easy way to solve it for n=1000. But here you can buy 0.47 pounds of ham & 0.26 pounds of cheese & so forth ie. anything above 0.25 pounds is fair game, so the problem lends itself to a solution in reasonable time even for very large n.
There is a variant of Knapsack called Continuous Knapsack[2], which is solvable in polynomial time, in-fact O(n) if you reformulate a bit. But that isn't the simplex algorithm either.
I guess what I'm saying is - knowing Knapsack & dynamic programming won't help you in this case. I actually solved a very similar problem for BofA a few years ago. We used the commercial version of CPLEX to optimally allocate a couple hundred million dollars to a few million home loan portfolios across the US.
I was actually hoping someone would post a solution using criss-cross[3].
And Harry is undoubtedly a resource of incredible value on things that the grocery startup hasn't even considered yet; exactly the sort of senior person they're going to need.
Hiring both of them is the right thing.
I'm not sure how Dick got past the phone interview, though.