Search⌘ K
AI Features
Home
Courses
Decode the Coding Interview in Java: Real-World Examples

Feature #11: Generate Movie Viewing Orders

Explore how to generate all permutations of movies in a marathon using a backtracking algorithm. Understand how to apply this approach to experiment with different viewing orders, and learn the time and space complexity involved in solving this problem.

We'll cover the following...

Description

We want to offer marathons for our viewers. Each marathon will have a fixed set of movies catering to a specific taste. For a given marathon, different viewing orders of the movies will yield different user satisfaction results. We want to experiment (A/B testing) with different viewing orders of the same marathon.

Your task is to generate all the possible permutations of movies in a given marathon.

Let’s look at an example to better understand this:

Solution

To solve this problem, we will use the backtracking approach.

We will assume a backtrack function that takes the index of the first movie to consider as one of the arguments.

  • If the first movie to consider has index size, then that means that the current permutation is done.

  • We will iterate over the marathon from index first to index size - 1.

  • We will place the ith movie first in the permutation, that is, moviesList[first], moviesList[i] = moviesList[i], moviesList[first].

  • We will proceed to create all the permutations that start from the ith movie: backtrack(first + 1).

  • Now we will backtrack, that is, moviesList[first], moviesList[i] = moviesList[i], moviesList[first] back.

Let’s look at ...