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

Feature #11: Generate Movie Viewing Orders

Explore how to generate all possible viewing orders of movies in a marathon using backtracking in C++. This lesson helps you understand permutation generation, apply it to enhance user experience through A/B testing, and analyze the algorithm's time and space complexities for efficient coding interview solutions.

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 an argument backtrack(first).

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

  • We will iterate over the marathon from index first to index n - 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 some illustrations to better understand this:

Note: We are using numbers to represent movies in the following illustration.

Let’s look at the code for this solution:

C++ 17
void backTrack(int first, int size, std::vector<std::string>& moviesList, std::vector<std::vector<std::string>>& output) {
    // If all strings of given array `moviesList` are used and 
    // and Backtracking is performed push_back the permutations to output array.
    if (first == size) {
      std::vector<std::string> temp(moviesList.begin(), moviesList.end());
      output.push_back(temp);
    }
    // Perform Backtracking for the size of a given array.
    for (int i = first; i < size; i++) {
        // Swap: In the current permutation place i-th integer first.
        auto temp = moviesList[first];
        moviesList[first] = moviesList[i];
        moviesList[i] = temp;
        
        // Complete permutations using the next integers.
        backTrack(first + 1, size, moviesList, output);
        
        // Swap and Backtrack
        temp = moviesList[first];
        moviesList[first] = moviesList[i];
        moviesList[i] = temp;
    }
}
std::vector<std::vector<std::string>> generatePermutations(std::vector<std::string>& movies) {
    std::vector<std::vector<std::string>> output;
    int size = movies.size();
    // convert movies into list since the output is a list of lists
    std::vector<std::string> moviesList;
    for (auto movie : movies)
      moviesList.push_back(movie);
    backTrack(0, size, moviesList, output);
    return output;
}
int main() {
    // Driver code
    // Example #1
    std::vector<std::string> input = {"Frozen","Dune","Coco"};
    auto output = generatePermutations(input);
    std::cout << "Output 1: " << toString(output) << std::endl;
    // Example #2
    std::vector<std::string> input2 = {"Frozen","Dune","Coco","Melificient"};
    output = generatePermutations(input2);
    std::cout << "Output 2: " << toString(output) << std::endl;
    // Example #3
    std::vector<std::string> input3 = {"Dune","Coco"};
    output = generatePermutations(input3);
    std::cout << "Output 3: " << toString(output) << std::endl;
    return 0;
}
Generate movie viewing orders

Complexity measures

...