Interview Cake Problem #8

I signed up for Interview Cake and got my first problem as promised.

I first tried to solve it using some function chaining with lodash‘s sort, filter, and reduce methods to toss out and sum up values. I wrote numerous tests against my max_duffel_bag_value() function with Mocha and used the command

mocha --watch cake-thief.js`

so I could watch my tests pass or fail on every save. I thought I had solved the problem, so I decided to look at the solution.

The sample input values in the solution failed when I added them to my mocha tests. The example solution was not what I expected, but was satisfying to follow and implement.

I used node.js as my programming environment instead of Python. Translating the solution provided by the site from Python to JS was not hard. Things worth noting:

• JS does not have tuples. I used a nested array like [[7, 160], [3, 90], [2, 15]]; instead. I also could have used object literals like [{weight:1, value:20}, {weight:5, value:200}]
• JS has an Infinity value which replaces Python’s sys.maxint value
• JS arrays aren’t fixed length, so that some_array = [0] * a_number + 1 line which creates an array with a_number + 1 elements isn’t needed.
• Python’s xrange lazily makes a list of numbers. JS does not have a built-in equivalent

I look forward to problem #2!