Intergalactic Avenger, a Google engineer, interviewed Stealthy Werewolf in JavaScript

Summary

Problem type

Meeting hour optimization

Question(s) asked

1) Given a list of meeting objects (e.g. {name: 'MeetingName', hours: numHours}) and an integer haveHours denoting how many hours of one's schedule alloted to meetings, write a function that optimizes the total number of meetings in one's day
2) Using the same input, write a function that optimizes the total number of hours one spends in meetings

Feedback

Feedback about Stealthy Werewolf (the interviewee)

Advance this person to the next round?

No

How were their technical skills?

2/4

How was their problem solving ability?

N/A

What about their communication ability?

2/4

I could see that you were struggling with this problem a bit. You solved the first version really well, including a good analysis of runtime, etc, but the second version with a different optimization strategy was tough. I could tell that you grasped the challenge of the problem and the general style of solution, but in practice I would have liked to see the solution come faster and with less guidance. I would suggest brushing up on combinatorics and dynamic programming, as they come up a lot in algorithmic-style questions.

Feedback about Intergalactic Avenger (the interviewer)

Would you want to work with this person?

Yes

How excited would you be to work with them?

N/A

How good were the questions?

4/4

How helpful was your interviewer in guiding you to the solution(s)?

4/4

You gave lots of good hints and guidance. You didn't give up on me; I really appreciate that. I now realize that I need a lot more practice in combinatorics and dynamic programming.

Transcript

Stealthy Werewolf: Hello?
Intergalactic Avenger: Hello! Hi there how are you doing?
Stealthy Werewolf: Good good, how are you?
Intergalactic Avenger: Going well, going well. Alright are you ready for a question?
Stealthy Werewolf: Sure yeah.
Intergalactic Avenger: Alright so this is going to be sort of an algorithmic question and there will be some coding so if you want to pick a language that you are comfortable with so for algorithmic type problems. I don't know if you've used the platform before but you can pick from a number of different languages. Yeah JavaScript will be just fine. So the idea here is we're going to implement something of a scheduler, something that will help you schedule meetings in your day sort of optimize your meeting plans for a day. So let's just say that you'll receive a list of

`meetings`

objects and you will return the meetings you should attend for that day. So let's just say you have more meetings than you could ever attend and you need to optimize that in some way shape or form and I'll give you the different ways that we want to optimize it.
Stealthy Werewolf: Okay.
Intergalactic Avenger: So let's start by saying you're going to write a function that is going to take in a list of these meeting objects and a number which is the number of hours in the day that you want to have meetings, and you'll just return a subset of `meetings`

that maximizes the total number of them. So let's just say from my first pass I just want to attend as many meetings as possible for that given day. And for each of these meeting objects, all of these objects will have a name and a number of hours they take.
Stealthy Werewolf: So a `meeting`

object would be something like: `{name: 'Meeting1', hours: 2}`

?
Intergalactic Avenger: Yeah.
Stealthy Werewolf: And this is the function signature here is that correct?
Intergalactic Avenger: Yep that looks correct.
Stealthy Werewolf: And I'm suppose to return the specific `meetings`

that you can attend.
Intergalactic Avenger: Yep as a list or something like that.
Stealthy Werewolf: Okay, return….So um this sort of makes sense. For each meeting though we only have how long it lasts, there's no mention of when it starts or when it ends.
Intergalactic Avenger: Right so let's say that all of these, it's sort of a contrived example but let's just say you know you want to meet with so many people during that day and you don't know exactly when they can meet you but maybe you're really important so you can tell them to start and stop the meetings whenever you want. So what you're trying to do now is you're just trying to figure out how many you can get in and which ones you can get in and don't worry for now about the start and stop time. So we'll just assume that if you're given a set of a `meetings`

with their durations you can figure out a way to start and stop them. That's not so interesting from this perspective.
Stealthy Werewolf: Gotcha. And the order that the `meetings`

are passed in, is there anything special about that?
Intergalactic Avenger: No they're in random order. You can't make any assumptions about the order that they're sent to you.
Stealthy Werewolf: Okay so if I'm returning a list of meeting objects it doesn't matter what order I turn them in either. So what it sounds like is we want to have as many `meetings`

as possible for a given number of hours, so the approach I would take is: sort the `meetings`

by the number of hours they would take and then pick the first `haveHours`

number of `meetings`

.
Intergalactic Avenger: Yeah, sounds good. That sounds like a perfectly good way of going this, let's code it up and see what happens.
Stealthy Werewolf: Sure. Okay so I'm going to sort this and I believe `sort()`

can take a comparative function is it okay if I look that up?
Intergalactic Avenger: Yeah that's totally fine.
Stealthy Werewolf: Okay so takes a comparative function which returns `-1`

or `+1`

that's fine so `meetings.sort()`

and we will return `1`

or `-1`

and you want to return `0`

if they're equal. So `if(m1.hours === m2.hours)`

return `0`

otherwise greater return `1`

or return `-1`

and that should give you sorted `meetings`

objects. And then now we go through the list….and `totalHours`

will track how many hours we have met with people for. So here's my question what would happen if...so let's say you have 8 hours rights, and you have 3 `meetings`

of 3 hours then a 4 hour meeting so would you prefer to return 7 I guess?
Intergalactic Avenger: I mean all we're doing is we're optimizing based on the total number of `meetings`

. In that case you can only fit in two `meetings`

: that's the max. And there's no other criteria, so as long as it returns 2 `meetings`

in that case then that's correct.
Stealthy Werewolf: Yeah but I can see an edge case where my method wouldn't exactly work but we'll go through that later that's fine.
Intergalactic Avenger: Okay.
Stealthy Werewolf: So I start from `0`

then I return `i`

. So by the time I get to..So stepping into the logic: we have a sorted list of `meetings`

and a a set number of hours. We start up by finding how many hours those `meetings`

add up to, which is `0`

. Then at every step through the for loop we check if adding the next meeting's hours would take us over the limit. Would then you break immediately otherwise you add it onto `totalHours`

and of course I advance this by `1`

and when you're done the point at which you finish is the number of `meetings`

you could have, which is `i`

.
Intergalactic Avenger: But actually, could you return the actual `meetings`

objects?
Stealthy Werewolf: Yeah.
Intergalactic Avenger: You want to maximize `i`

, but you want to return the meeting objects.
Stealthy Werewolf: Right right sorry, forgot about that. Let's call that `meetingsCanBeMade[]`

. And you return that. Okay so I think it now returns the list of objects.
Intergalactic Avenger: Okay now let's write a little test harness for this and let's create 3 `meetings`

, lengths of 2, 3, and 5 hours. Run it through this and see what we get back. Actually just for fun, let's try putting that in reverse order. So here it says `2, 3, 5`

. Just make it `5, 3, 2`

.
Stealthy Werewolf: Okay and how many hours do we have?
Intergalactic Avenger: 8
Stealthy Werewolf: Right so it's going to fail for this, because you're going to sort in ascending order, and...well actually you'd still only be able to make two `meetings`

.
Intergalactic Avenger: Yep, I think this is going to work. Let's fire it up, let's see what happens.
Stealthy Werewolf: Okay yeah it will return.
Intergalactic Avenger: Could you also add a log at the end with the original `meetings`

object? Just afterwards just so we can see what happens if…
Stealthy Werewolf: Like here?
Intergalactic Avenger: Yeah.
Stealthy Werewolf: Well it will have modified the initial `meetings`

object on `sort()`

.
Intergalactic Avenger: Yeah so is that really a good idea? Might that confuse some people if they pass in some `meetings`

and the original object they passed in was modified?
Stealthy Werewolf: Yeah, if that's undesirable behavior one thing we can do is copy out the pass in list of `meetings`

to another list inside the function that is one option. And of course that means we would be using extra space, I don't know if that's acceptable. The other way would be: you go through the list of `meetings`

, find the meeting with the smallest number of hours, add that on. Go through the list again, find the one with the second least numbers, add that on…
Intergalactic Avenger: Okay yeah.
Stealthy Werewolf: That would increase the time complexity.
Intergalactic Avenger: Okay and that was the next question I was going to ask. So you have the two options there: one would be to create a copy and sort the copy like you did here. The second is to go through and pick out the other: the 2nd smallest etc. What are the time complexities of those two approaches?
Stealthy Werewolf: So the first one the time complexity is `O(nlogn)`

because the sort is `O(nlogn)`

. And the search is just linear. For the second one it would be `O(n^2)`

because you have the for loop outside and inside you're doing a search for the smallest and second smallest.
Intergalactic Avenger: Okay now that's perfect! Nice little warm up problem you did great. Now we're going to throw a little wrinkle in it. The first time we optimized for just the total number of `meetings`

and you're right that if we want to optimize only for the total number of `meetings`

by length and then just pass them in a greedy fashion. Now let's say I wanted to maximize the total number of hours I was in meetings. So it doesn't actually matter how many meetings I attend, what only matters is that I'm in meetings for as long as possible during my day. So if I have an 8 hour day, and I can be in meetings for 8 hours, that's optimal.
Stealthy Werewolf: So you want to have the sum of `meetings`

be as close to `haveHours`

as possible.
Intergalactic Avenger: Exactly.
Stealthy Werewolf: Okay yeah that is slightly more difficult. So one approach might be: you start from the other end and you take the biggest and you add that on. Does that change anything though? So let's say you have 8 hours and instead of 5, 3, and 2 you have 2, 3, 4, and 5. And now you start from the end....Oh okay I think I sort of have it. So I think the approach here might be that you maybe use...you still sort the array and then you start from the end of the array and you look at the meeting that runs the longest and you add that to your list of `meetings`

that can be made and then you go to the other end of the array, the start of the array. And you look for another meeting that...and you calculate how many hours you have left. You have 5 hours right, and now you have 3 hours left and you go back to the start of the array where you find a 3 and you find the number that's closest to 3 without going over 3.
Intergalactic Avenger: So what if, in this case, you start off and there's 8 hours in a day, but your `meetings`

are 4, 4, and 5?
Stealthy Werewolf: Gotcha yeah. That's a good point. What if you started at the other end then? What if you started at the first meeting and you see how many hours you have left then you search from the end of the array, basically going backwards.
Intergalactic Avenger: Sort of like you did in the original one? Where you sorted then went up?
Stealthy Werewolf: Sort of. So what I'm saying is you start with the first meeting 4, and now you have only 4 hours left so you scan from the beginning of the array for another meeting that has 4 or fewer hours. Do you see what I'm saying.
Intergalactic Avenger: And you've sorted it first.
Stealthy Werewolf: Yes.
Intergalactic Avenger: Wait but it wouldn't work for the first example. Let's say you have...you need 6 and 5 is less than 6. That's not the ideal solution. The ideal solution is 3 and 5.Yeah, just starting at 1 end is not quite going to get you there. It's close but there certainly are some other cases that aren't going to work in a greedy fashion like this.
Stealthy Werewolf: Gotcha. So the naive way to do this is generate every single possible combination and see which ones add up to 8 and that would be the naive way to do this.
Intergalactic Avenger: Or do they, they don't necessarily always have to add up to 8.
Stealthy Werewolf: As close to 8 as possible. You generate all the combinations, you find the sums and then you pick the one that's closest to 8 without going over it.
Intergalactic Avenger: Yeah that would certainly work, and let's try coding that up, let's see what that looks like.
Stealthy Werewolf: Sure, write that out. Okay. So first we want combinations of 1 element and then combinations of 2 elements then 3 elements all the way up to meetings.length elements. So now to get combinations of 1 element we would do. Totally blanking here.
Intergalactic Avenger: That's fine. So think of it…You sort of had a good intuition at the beginning where you were talking about all different combination you can sort of think of it as `meeting1`

, 2, 3, 4. One of the combinations either has the first one or it doesn't, it either has the second one or it doesn't, and it either has the third one or it doesn't and if you add up all of those, you have the complete set of all possible meeting arrangement.
Stealthy Werewolf: Yeah okay sort of. I mean I've done this sort of combination thing before and I'm just blanking. So I'm going to generate all the ones of length 2 and hopefully that gets me somewhere. Okay so this gets you all the combinations of `meetings`

with length 2.
Intergalactic Avenger: This is only going to return 2 right?
Stealthy Werewolf: Yeah all the `meetings`

with length 2.
Intergalactic Avenger: But there's 4 combinations of length two? Well it's either…well I guess it depends on what you mean by length two. So this is going to return…
Stealthy Werewolf: So you'd get 2,3 3,4. This not anything close to the actual solution.
Intergalactic Avenger: No I understand.
Stealthy Werewolf: That's what this would return.
Intergalactic Avenger: I see, I see. Okay it does do that. So that's basically saying all the possible combinations of two `meetings`

. But let's see if I can give you a hint here about how it might work. If you think of breaking this down into subproblems you could think that given a hundred `meetings`

, and you want to enumerate all of them you could break it down to say well I'm going to enumerate every way I can permeate the first meeting and append that to the list of what the maximum or what all the permutations of the next 99 are. Does that give you an idea of how you might do this next permutation?
Stealthy Werewolf: Yeah. Sorry is a permutation order dependent or not order dependent?
Intergalactic Avenger: It's order independent, so it doesn't matter the order.
Stealthy Werewolf: Okay so these are permutations not combinations. So I understand what you're saying so its going to be something like: for…So this will get everything from `0`

to `i`

and then you add that to…add `i`

to the end, no you want to skip `i`

itself so `i+1`

. So this is basically just saying: you want to get permutations of every element except the element at `i`

, so basically the singular case. Okay so what this is going to do is return all the permutations of the `meetings`

without the meeting at I and once you have those, you add on the meeting at `i`

to those permutations then you return the whole thing. Whereas if the length is 1 then you return just that meeting object itself.
Intergalactic Avenger: Well here's a sample input to think about. So you say when the meeting length is `1`

you just return that. Well let's say that in the input set I only have 1 meeting for that day but that it's greater than the numbers I have. So let's say there's only 1 meeting for that day, but it's 5 hours long and I decided I'm only taking a half day so I only give it a total meeting hours `haveHours`

of 4 so what's the correct answer in that case?
Stealthy Werewolf: Just an empty array.
Intergalactic Avenger: Right so in this implementation do you ever return an empty array?
Stealthy Werewolf: Well I'm not finished yet though. I'm still working out what I'm what `getPermutations`

will return.
Intergalactic Avenger: Or I guess from that perspective: if you `getPermutations`

on that `meetings`

array, does that ever return that empty set, that empty array.
Stealthy Werewolf: Well I haven't returned anything. I have a preliminarily calling all the sort `meetings`

and remove all the `meetings`

that exceed your `haveHours`

.
Intergalactic Avenger: You could, but I think that's making it a bit harder on yourself. The logic should be able to work without that.
Stealthy Werewolf: Okay.
Intergalactic Avenger: I guess what I'm saying is: if you look at these permutations for any meeting that is always going to return this meeting 0 whereas the permutations of all of these will always include or not include some `meetings`

so you're always returning this meeting and when looking at the permutations you want to not include some `meetings`

.
Stealthy Werewolf: Okay in that case `getPermutations`

would need to have some knowledge of how else….
Intergalactic Avenger: Well I mean getting the permutations I like the way you structured this: basically get me all the permutations of `meetings`

and at that point you don't know what the `haveHours`

is and that's totally fine. But I'm wondering if that's actually returning all the permutations that you want to be looking at. So like if you think of: if you're just given as the input meeting set meetingA, what are you planning to get back. So meeting is an array of length 1 and just has the hours 5.
Stealthy Werewolf: Yes. So here's how I see it. If you have a set of `meetings`

that exceeds the number of hours in your day, you go filter it out before you even get to permutations so you have fewer permutations to get through.
Intergalactic Avenger: But, or even. You can think of it another way: you can say okay if my two `meetings`

are 4 and 5 hours and I have total of 8 hours in the day and the 5 hour meeting is not going to be able to fit. So somewhere in this permutation you have to say the 5 hour meeting is not going to fit and it's not going to be in the set that I'm returning. And I guess what I'm saying is that the logic I see here is always returning all of the `meetings`

.
Stealthy Werewolf: Okay, so you're saying that `getPermutations`

we check what we're going to return, let's say at `i`

. And we check the sum of each of those permutations and if any of them exceed `haveHours`

then we maybe return those permutations from this list?
Intergalactic Avenger: Not exactly. How about we try this: how about I write so I'm going to put `meetings2`

and it's going to have hours of 5 and `console.log(getPermutations(meetings2)`

. So what do you think to see come out of this?
Stealthy Werewolf: I expect to see what you just passed in.
Intergalactic Avenger: But that's not all the permutations right? So the expected result should be all permutations of 1 thing, so we want the empty set and we want the. So there's two permutations: there's it has the meeting and it doesn't have the meeting.
Stealthy Werewolf: Okay I didn't consider the empty set as one permutation but I suppose that's true. I'm sorry I don't understand the point you're trying to make here.
Intergalactic Avenger: I guess I'm saying we can try running this function and see if we get the result you think we're going to get. So you try running it and let's see what happens: if it actually returns what we think it will return.
Stealthy Werewolf: So it just returns `hours: 5`

, not in a list so….it returned an empty set.
Intergalactic Avenger: So let's just start with that, let's just start with the base case let's just make sure…with a lot of these recursive algorithms you're just dealing with a base case and some recursive case. So let's just get the base case down and then we can work on getting the other cases down.
Stealthy Werewolf: If you can consider the empty set to also be a part of the permutations then you can append the empty set to…
Intergalactic Avenger: Okay, now we're cooking with gas, that's exactly what we want to see. Now if I add another one, with hours of 4. So now our expected value is going to be `{hours: 4}`

and then `{hours: 5}`

and `{hours: 4}`

, `{hours: 5}`

. So there's 4 combinations of `meetings`

: just the 5 hour meeting, just the 4 hour meeting, and both the 5 hour meeting and the 4 hour meeting.
Stealthy Werewolf: Yes, okay.
Intergalactic Avenger: So we know that your base case is working up here, now can you think of a way to fill out your get permutation such that it calls `getPermutations`

on the next thing and still produces what we expect.
Stealthy Werewolf: Okay so you're saying not this.
Intergalactic Avenger: Yeah I think it's a bit more complicated than you need and I think the slice from `0`

to `i`

. I think you're iterating through the number of `meetings`

and then calling `getPermutations`

on all of those `meetings`

is causing a bit of a problem there. I think you're recursively calling it too many times.
Stealthy Werewolf: Let me walk through this logic and think about it. So in the example that you gave so if `i = 0`

then you're calling `getPermutations`

on `slice()`

and then you go in and `getPermutations`

on this slice then you get it on this slice. You come back up the stack, `permutationsWithoutI`

…
Intergalactic Avenger: So is that the right place? So you said that given this length of 4 meeting, at that level do you really want to be calling the permutations function for each successive length or do you want to let the recursive call take care of shorter and shorter things for you. Because another way you can think of it is breaking down the problem into smaller units is I can say: I have my first meeting and all the rest of my `meetings`

, so I can say: I want to concatenate all the permutations from my first meeting from all of the permutations of all of the rest of the `meetings`

. That second part is completely handled by the recursive call.
Stealthy Werewolf: Okay, something more like. I mean in that case the recursive function would get the index of the element that is not being considered so everything except `i`

.
Intergalactic Avenger: And then you can just pass in…think about how you can get `getPermutations`

to work correctly the first time. It just: given a bunch of `meetings`

, return a set of all the permutations of that set of `meetings`

and it work, you didn't need and `i`

you didn't need anything. So this base case totally worked. If you think about the length greater than 1 then just think of it as solving the problem from the first one and recursively asking the same function again to solve a little bit smaller function.
Stealthy Werewolf: Right I understand what you're saying I'm just not sure whether that would work. Okay fine I guess that would work. So you just take the first, fine. Okay so this will get you all the permutations except for the first one and then in this case at the second to last level `permutationsWithoutI`

would contain that. To the next level what you'd want to return is….
Intergalactic Avenger: So you're really close. The first meeting is correct, the `permutationsWithoutI`

is correct it's just this last piece. Just a hint: you don't need to go through that but at this point you.
Stealthy Werewolf: I don't need to go through the list per se, what I need to do is join the first meeting to every other element in `permutationsWithoutI`

so…So onto this so for the first element we join the first meeting then push it to `permutationsWithoutI`

and for the second one we do the same thing and that would probably work.
Intergalactic Avenger: Alright, let's hit go see if that works.
Stealthy Werewolf: So `permutationsWithoutI.push()`

…. Okay so there was something that was undefined. Okay so that's exactly what we expected.
Intergalactic Avenger: Yeah and you have the right idea that for each one of those, we want to push on hours `5`

. So I think maybe the problem, I'm not that familiar with JavaScript, would be that there's some weird recursive thing going on with this `permutationsWithoutI`

pushing onto itself which is pushing onto itself. I'm wondering if there's something weird there and if there's another way of doing that.
Stealthy Werewolf: Huh it's logging a 2 somewhere which is not quite what we wanted huh. Clearly pushed a 2 somewhere.
Intergalactic Avenger: So it's obviously the length right? But I'm wondering if I is actually getting the length out of it which is strange. Because `permutationsWithoutI.length`

is 2 right?
Stealthy Werewolf: Yeah, storing the length somewhere?
Intergalactic Avenger: So is there a way to copy the entire….You copy the entire list that you got back and in front of each one of those add the first meeting kind of like you're doing and concatenate all of that together. Is there a way to do that? I don't know. Because you have the logic basically right here but there's something weird with the code.
Stealthy Werewolf: I'm just going to try rewriting it. So that's exactly what we expect for a string and that's also what we expected. And I think you said that copying might be a problem let's just make….
Intergalactic Avenger: I mean eventually, if you're returning all of them, then a certain amount of copying is going to be necessary.
Stealthy Werewolf: Pretty much. That's going to necessitate a loop inside the…So I think what you were saying earlier is happening because this is like an array of arrays if you try and push something onto an array inside an array and push that back on the array it's going to cause…
Intergalactic Avenger: It's getting confused a little bit yeah.
Stealthy Werewolf: Let's just copy it out.
Intergalactic Avenger: So there's no array copy in JavaScript?
Stealthy Werewolf: JS 6 might have it, I don't know the library function offhand.
Intergalactic Avenger: I think you can just say `slice()`

with no operator, that makes a copy. So `slice()`

with no arguments, that makes a copy. Yeah.
Stealthy Werewolf: Not quite what we wanted though is it.
Intergalactic Avenger: Not quite. But it's getting close. If you think about it, it's going to create a variable that is going to contain all the permutations so you can just create a new one at the beginning. The sub-permutations…right yeah there you go.
Stealthy Werewolf: So are you sure that calling `slice()`

without….
Intergalactic Avenger: I could be wrong but seems like…stack overflow says it does.
Stealthy Werewolf: I wonder if a shallow copy means….Since we have an array of objects its not going to work.
Intergalactic Avenger: I see. Oh I know what's happening, it's because you're increasing the length of `permutations`

so when you say `permutations.push(copied)`

you're increasing the length of it so `i`

is just going to get bigger and bigger and bigger. I think you need another array that's called something like `allPermutations`

and you should push all of those.
Stealthy Werewolf: Okay alright fine.
Intergalactic Avenger: Or you could check the `permutations.length`

earlier, actually that might be simpler. Check the total `permutations.length`

and make sure that `i`

is, yeah. You actually have to set `len`

.
Stealthy Werewolf: Looking at the documentation so the…Do we have to return all the different permutations of `meetings`

that `haveHours`

?
Intergalactic Avenger: No just the one best permutation. It's the optimal one which might not be `haveHours`

, it's the maximum number that's less than `haveHours`

.
Stealthy Werewolf: Gotcha, that's true. So if `sum <= haveHours`

and we want to check if whether sum is closer to `haveHours`

than `closestSum`

is….
Intergalactic Avenger: Alright so yeah. Let's call optimize meeting with our `meetings2`

, or actually it was `meetings`

and with 8. See what happens.
Stealthy Werewolf: Sorry which ones?
Intergalactic Avenger: Just give it this `meetings`

as input.
Stealthy Werewolf: Oh that okay
Intergalactic Avenger: And `haveHours`

of 8. See how that does.
Stealthy Werewolf: Empty array 8, that's not what we wanted. Not yet. Let's look at this again. We have `getPermutations`

, let's check if we actually caught the right permutations. Okay so the permutations were correct.
Intergalactic Avenger: Yep the permutations were good. I wonder if the sum is....can you log the sum?
Stealthy Werewolf: Sure, I was checking for the correctness of my `reduce()`

function. There is something wrong with my reduce function. Okay wondering….Oh I called it backwards.
Intergalactic Avenger: Looks like you need 4 values?
Stealthy Werewolf: You don't have to take all of them if you don't need them.
Intergalactic Avenger: Okay yeah, previous value and current value should be enough.
Stealthy Werewolf: Okay so now it's definitely logging the sum so there's probably something wrong with my if.
Intergalactic Avenger: Can you log the permutations of sum I think that should….okay so that looks okay so we're getting really close.
Stealthy Werewolf: Yeah. I'm going to take out this console.log. And now….why is it logging 8 though. That's strange. There's no reason for it to log 8.
Intergalactic Avenger: At each iteration can you console.log optimal`meetings`

to see what's happening there? Does it ever go into that if statement?
Stealthy Werewolf: Doesn't look like it. Yeah, it doesn't look like it ever goes into here. So there's something wrong with the if.
Intergalactic Avenger: `haveHours`

if undefined….oh but that's where from you call it.
Stealthy Werewolf: And that's why it was actually logging 8.
Intergalactic Avenger: There you go. Alright so it took a little while but you made it through and now you have the optimal solution here.
Stealthy Werewolf: I imagine there's dynamic programming solution for this also?
Intergalactic Avenger: Yeah so how it works is you don't use a recursive solution you just set up a table where you look back as the optimal solutions. So it again builds on the idea of starting with a base case and building out from that base case. So say I have 0 hours in my day and a whole set of `meetings`

and in that case that is the base case where you say well my optimal solution is just an empty set because I have 0 hours. Then for the hour number 1 you say: well what if I have 1 hour in my day then what you do is you say for each one of these `meetings`

I have, I look back that many hours and say well what's the best way I can fit in 1 hour given all of them. So some of the `meetings`

may be too long and they're not even looked at. But if you have some 1 hour `meetings`

then they look back and say well I just need to add that 1 hour meeting to whatever it was 1 back and so the whole time you're building up this array you have an optimal solution up to that many hours. So you'll have an optimal solution for 0 hours and 1 hour and 2 hours and 3 hours and you say okay I'm at hour 16 and I'm looking for how can I best add on `meetings`

of length 4 and 2 then you basically just look back 4 and 2 hours from 16 in your array to say which one of those gives me the biggest sum.
Stealthy Werewolf: Interesting.
Intergalactic Avenger: Yeah it's a little bit intricate but it's kind of a neat sort of trick. Well done, you stuck with it I liked the tenacity and in the end we got a real working program. Do you have any other questions?
Stealthy Werewolf: No and thanks for walking me through it. I appreciate it.
Intergalactic Avenger: No problem, take care.
Stealthy Werewolf: Bye.
Intergalactic Avenger: Okay, bye.