-
-
Save theWhiteFox/a783f28980babdecae04a0fd01f1066c to your computer and use it in GitHub Desktop.
kd
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
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) => { | |
let maxVal = -Infinity; | |
let max = null; | |
// recursively find all combinations of activities | |
// if the total XP of any combination is greater than max, store in closure | |
const findCombos = (items, prefix=[]) => { | |
for (let i = 0; i < items.length; i++) { | |
const combo = [ | |
...prefix, | |
items[i] | |
]; | |
const xp = totalXp(combo); | |
if (xp > maxVal && totalTime(combo) <= time) { | |
maxVal = xp; | |
max = combo; | |
} | |
findCombos(items.slice(i + 1), combo); | |
} | |
}; | |
const totalXp = acts => acts.reduce((total, act) => total + act.xp, 0); | |
const totalTime = acts => acts.reduce((total, act) => total + act.time, 0); | |
findCombos(activities); | |
return max.map(act => act.name); | |
}; | |
// The time complexity of this solution is O(n! * n) | |
// The space complexity is O(n! * n) | |
console.log(findJob(10, ACTIVITIES)); | |
//=> [ 'algorithms', 'systems design', 'making CSS codepens' ] |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment