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 permutations of movies in a marathon using backtracking. Understand the approach and its time and space complexity, improving your problem-solving skills and preparing for coding interviews focused on generating permutations.

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, Movies[First], Movies[i] = Movies[i], Movies[First].

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

  • Now we will backtrack, that is, Movies[First], Movies[i] = Movies[i], Movies[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#
using System.Collections.Generic;
class Solution {
  public static void Backtrack(int n, List<string> nums, List<List<string>> output, int first) {
    
    // If all integers of given array `Movies` are used and 
    // and Backtracking is performed add the permutations to Output array.
    if (first == n)
      output.Add(new List<string>(nums));
    
    // Perform Backtracking for the Size of a given array.
    for (int i = first; i < n; i++) {
      
      // Swap: In the current permutaion place i-th integer first.
      var temp = nums[first];
      nums[first] = nums[i];
      nums[i] = temp;
      
      // Complete permuations using the next integers.
      Backtrack(n, nums, output, first + 1);
      
      // Swap and Backtrack
      var temp2 = nums[first];
      nums[first] = nums[i];
      nums[i] = temp2;
    }
  }
  public static List<List<string>> GeneratePermutations(string[] nums) {
    // init output list
    List<List<string>> output = new List<List<string>>();
    // convert nums into list since the output is a list of lists
    List<string> nums_lst = new List<string>();
    foreach(string num in nums)
      nums_lst.Add(num);
    int n = nums.Length;
    Backtrack(n, nums_lst, output, 0);
    return output;
  }
  static void Main(){
    // Example #1
    string[] Input = new string[3]{"Frozen","Dune","Coco"};
    var Output = GeneratePermutations(Input);
    System.Console.Write("Output 1: [");
    for(int i = 0; i<Output.Count; i++){
      System.Console.Write("[");
      System.Console.Write(string.Join(", ",Output[i]));
      System.Console.Write("]");
    }
    System.Console.WriteLine("]");
    // Example #2
    Input = new string[4]{"Frozen","Dune","Coco","Melificient"};
    Output = GeneratePermutations(Input);
    System.Console.Write($"Output 2: [");
    for(int i = 0; i<Output.Count; i++){
      System.Console.Write("[");
      System.Console.Write(string.Join(", ",Output[i]));
      System.Console.Write("]");
    }
    System.Console.WriteLine("]");
    // Example #3
    Input = new string[2]{"Dune","Coco"};
    Output = GeneratePermutations(Input);
    System.Console.Write($"Output 3: [");
    for(int i = 0; i<Output.Count; i++){
      System.Console.Write("[");
      System.Console.Write(string.Join(", ",Output[i]));
      System.Console.Write("]");
    }
    System.Console.WriteLine("]");
  }
}
Generate Movie Viewing Orders

Complexity measures

Time complexity
...