Skip to content

Instantly share code, notes, and snippets.

@dengjonathan
Created February 16, 2017 19:14
Show Gist options
  • Save dengjonathan/2b68ef6a7e5e2ba338323c4de2f65f40 to your computer and use it in GitHub Desktop.
Save dengjonathan/2b68ef6a7e5e2ba338323c4de2f65f40 to your computer and use it in GitHub Desktop.
job search DP
const ACTIVITIES = [
{name: 'side-project', time: 10, xp: 12},
{name: 'algorithms', time: 3, xp: 7},
{name: 'networking', time: 1, xp: 0.5},
{name: 'exercise', time: 2, xp: 1.5},
{name: 'systems design', time: 4, xp: 4},
{name: 'making CSS codepens', time: 3, xp: 4}
];
/**
* Returns array of type string with names of activites that maximize XP
* @param {number} time
*/
const findJob = (time, activities) => {
const optimalSolution = (items, n = items.length, timeLeft = time) => {
// if we have no time left or no items left to consider, return empty arr
if (n === 0 || timeLeft === 0) {
return [];
}
// if last item is too heavy (we sorted the array), don't consider it
if (items[n - 1].time > timeLeft) {
return optimalSolution(items, n - 1, timeLeft);
}
const lastItem = items[n - 1];
const withLastItem = [
lastItem,
...optimalSolution(items, n - 1, timeLeft - lastItem.time)
];
const withoutLastItem = optimalSolution(items, n - 1, timeLeft);
if (totalXp(withLastItem) > totalXp(withoutLastItem)) {
return withLastItem;
} else {
return withoutLastItem;
}
};
const totalXp = arr => arr.reduce((total, ea) => total + ea.xp, 0);
const sortedByTime = activities
.slice()
.sort((a, b) => a.time - b.time);
return optimalSolution(sortedByTime)
.map(act => act.name);
};
/*
The time complexity of this solution is O(n * nT) where n is number of items
and T is the total amount of time we have.
We have to recusively find the optimal solution for each time from 0 to the total
time we have, and for each recursive call we have to consider each item in the
list of items. And for each item we consider, we have to calculate the total
XP.
At the cost of being less clear, we could refactor the solution to not
calculate total XP every time. This would make our solution O(nT)
The space complexity is O(nT) because there are T function scopes created by
recursive calls and each scope stores an array with up to n items.
*/
console.log(findJob(10, ACTIVITIES));
//=> [ 'systems design', 'making CSS codepens', 'algorithms' ]
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment