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

Feature #11: Generate Movie Viewing Orders

Explore how to apply backtracking in Kotlin to generate all permutations of movie viewing orders for streaming marathons. This lesson helps you understand how to implement efficient algorithms to experiment with different user experiences and improve streaming satisfaction through permutation generation.

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 add the moveList to the output

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

  • We will place the ith movie first in the permutation, using function Collections.swap(moviesList, first, i).

  • We will proceed to create all the permutations that start from the ith movie: backTrack(first + 1, size, moviesList, output).

  • Now we will swap again, that is, Collections.swap(moviesList, first, i) 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:

Kotlin 1.5
internal object Solution {
    fun backTrack(
        first: Int,
        size: Int,
        moviesList: List<String>,
        output: MutableList<List<String>>
    ) {
        // If all strings of given array `moviesList` are used and 
        // and Backtracking is performed add the permutations to output array.
        if (first == size) {
            val temp: List<String> = ArrayList(moviesList)
            output.add(temp)
        }
        // Perform Backtracking for the size of a given array.
        for (i in first until size) {
            // Swap: In the current permutation place i-th integer first.
            Collections.swap(moviesList, first, i)
            // Complete permutations using the next integers.
            Solution.backTrack(first + 1, size, moviesList, output)
            // Swap 
            Collections.swap(moviesList, first, i)
        }
    }
    fun generatePermutations(movies: Array<String>): List<List<String>> {
        val output: MutableList<List<String>> = LinkedList()
        val size = movies.size
        // convert movies into list since the output is a list of lists
        val moviesList = ArrayList<String>()
        for (movie in movies) moviesList.add(movie)
        Solution.backTrack(0, size, moviesList, output)
        return output
    }
}
fun main() {
    // Example #1
    val input = arrayOf("Frozen", "Dune", "Coco")
    var output: List<List<String?>?> = Solution.generatePermutations(input)
    println("Output 1: $output")
    // Example #2
    val input2 = arrayOf("Frozen", "Dune", "Coco", "Melificient")
    output = Solution.generatePermutations(input2)
    println("Output 2: $output")
    // Example #3
    val input3 = arrayOf("Dune", "Coco")
    output = Solution.generatePermutations(input3)
    println("Output 3: $output")
}
Generate movie viewing orders

Complexity measures

...