[Solution]Problem 55:Playlist with Buffer[Apple]

Dynamic Programmming, Logic, Combinatorics

To learn more about the newsletter, check our detailed About Page + FAQs

To help me understand you better, please fill out this anonymous, 2-min survey. If you liked this post, make sure you hit the heart icon in this email.

Recommend this publication to Substack over here

---

Are you ready for this,

Let’s jump right into it.

Problem

You are going on a road trip, and would like to create a suitable music playlist. The trip will require N songs, though you only have M songs downloaded, where M < N. A valid playlist should select each song at least once, and guarantee a buffer of B songs between repeats.

Given N, M, and B, determine the number of valid playlists.

Step 1: Understanding the Mechanics

As I’ve gone over many times, a good first step is to simply read the problem. Read the problem well, annotate important points, and you will automatically notice a lot of interesting details. So what stands out about this problem?

Notice the wording-

Given N, M, and B, determine the number of valid playlists.

This is a classic combinatorial problem. Since we have been given a choice that can be varied (the song you play at any given moment) and we have to generate a total number of combinations- dynamic programming seems like a likely feature of our solution. At this point, the specifics are not important. What matters is that we have a rough idea of the viable next steps, that we can build upon. Remember, take it slow. One step at a time.

So how can we proceed? Anyone that has solved tricky combinatorial problems knows something important- to solve hard combinatorics problems, you have to solve easier ones first. In our case, the big constraint is the buffer. Let’s relax it and then try to work out our simpler solution. Since our simpler problem will have a lot of similarities to our original, we will be able to gain a lot of insights onto the bigger problem.

Step 2: Solving the Simple Problem

Clearly, to solve this problem we need a function ways(i,j) that give us the number of ways of making a playlist of length i with j unique songs. Next, let’s proceed to building out some simple base cases, and working our way up from there. Remember, in your interviews, always take the low-hanging fruit. It’s much better than sitting there awkwardly in silence, hoping the interviewer notices your pretty eyes.

A simple base case is when i and j are both zero. This gives us one value- a playlist with no songs.

Otherwise, we apply one of our favorite techniques - the case by case analysis- to split out the remaining coding problem into two cases-

1. The last song is new- If the last song is new, we have used j-1 songs till this point. Thus our current song is one of the m-(j-1) unused songs. Each of these songs can be combined with any of the playlists with one fewer song and one fewer unique song, or ways(i-1,j-1). So ways(i,j)= ways(i-1,j-1)* m-(j-1)

2. The last song is a repeat- We now have to use one of the j songs already used. Each of these songs can be combined with any of the options that would be generated by creating playlists of length i-1 and j unique songs or ways(i - 1,j). So ways(i,j)= ways(i - 1,j)* j

If you’re confused by multiplication, look into studying some basic permutations and combinations. We have a very diverse level of Math knowledge b/w the subs (most of my subs come from either Machine Learning or Computer Science, but I do have a good number of Bootcamp grads and web/mobile devs amongst you), so I’m not sure if you need a full deep-dive here. If you need help understanding it, reach out to me.

According to the Multiplication Principle, if one event can occur in m ways and a second event can occur in n ways after the first event has occurred, then the two events can occur in m×n m × n ways.

-The basic reason we multiply. Source

Our analysis should make one thing very obvious. Our solution has a recursive substructure. Here is a neat lil trick to help you with DP. If you notice a recursive substructure and you have combinatorics/generation, you’re probably looking at Dynamic Programming. After all, DP exists to help you avoid repeated computations. Which will happen a lot with recursive generation functions.

Reminder, we covered Recursive problem solving (and much more). Go through the Archives.

So now let’s combine all the insights we’ve gained so far with the understanding that DP will help us to create the algorithm for the buffer. After that, I’m going to go eat some Falafels and gyro. I’ll be doing my first Judo class in a couple of months too, so I’m pretty psyched for the evening. How do y’all normally spend your Thursdays?

Step 3: Introducing the Buffer

So how does the buffer change things up?

Good thing we have things split up by cases. This will make the analysis so much easier.

Clearly, our base case wouldn’t be affected by a buffer. What about the other two?

In case 1, we have a new song. By definition, we haven’t repeated anything.

In case 2, what changes? Simply put, we will not be able to use the last B songs in our playlist. Instead of having access to j unique songs, we’re now left with j-B songs. If the buffer is bigger than the number of distinct songs played so far, no repeat songs are possible, so our computation should return 0. Thus we can rework our math to account for this- ways(i,j)= ways(i - 1,j) * max(j - b, 0)

And that, we’re good to go. Let’s start coding things up.

Step 4: Coding things up

Using all our insights, we can generate the code for our solution. I went with a bottom-up DP approach here, because that is generally considered ‘better’ than top-down. This is because memoization is a pretty expensive process. Bottom-up avoids that. They have the same time complexity though, so don’t sweat it too much if you really have to use memoization in the interview.

def valid_playlists(n, m, b):
    ways = [[0 for _ in range(m + 1)] for _ in range(n + 1)]
    ways[0][0] = 1 #base-case

    for i in range(1, n + 1):
        for j in range(1, m + 1):
            ways[i][j] = ways[i - 1][j - 1] * (m - (j - 1)) + ways[i - 1][j] * max(j - b, 0)

    return ways[n][m]

Time Complexity- O(N*M). We go through the nested loop

Space Complexity- O(N*M).

Loved the solution? Hate it? Want to talk to me about your crypto portfolio? Get my predictions on the UCL or MMA PPVs? Want an in-depth analysis of the best chocolate milk brands? Reach out to me by replying to this email, in the comments, or using the links below.

Stay Woke. I’ll see you living the dream.

Go kill all,

Devansh <3

Reach out to me on:

Instagram: https://www.instagram.com/iseethings404/

Message me on Twitter: https://twitter.com/Machine01776819

My LinkedIn: https://www.linkedin.com/in/devansh-devansh-516004168/

My content:

Read my articles: https://rb.gy/zn1aiu

My YouTube: https://rb.gy/88iwdd

Get a free stock on Robinhood. No risk to you, so not using the link is losing free money: https://join.robinhood.com/fnud75