Home » Interview coding problems/challenges

Suggesting movie randomly from a list C++ program

In this article, we are going to see how to implement an application where we will be able to recommend movies randomly out of a movie list? This question has been asked in Synopsys interview round.
Submitted by Radib Kar, on July 14, 2020

Problem statement:

Write an application code that will suggest movies from a list randomly and there won't be any repeat while suggesting the movies. That means the same movie won't be suggested twice though it will be done randomly. Input will be a movie list.

Prerequisite: Shuffling a given array in O(n) time using Fisher-Yates algorithm

Example:

Input:
["D-DAY", "RAINCOAT", "OCTOBER","LUNCHBOX", "BARFI", "RAAZI","PIKU"]

Movie suggestion list can be
"BARFI"
"PIKU"
"RAAZI"
"OCTOBER"
"D_DAY"
"LUNCHBOX"
"RAINCOAT"

Solution

We can use Fisher-Yates random shuffling algorithm to solve this problem. Firstly, we need to create a map to store indexes of the movies as we will shuffle based on their indexes.

So the map will be:

KEY	VALUE
1	"D-DAY"
2	"RAINCOAT"
3	"OCTOBER"
4	"LUNCHBOX"
5	"BARFI"
6	"RAAZI"
7	"PIKU"

So our movie list will be converted as: [1,2,3,4,5,6,7]

Then we will shuffle using the Fisher-Yates algorithm

At each step iteration, we will suggest movie[i]. Below is the detailed algorithm for suggesting movie randomly

The detailed algorithm will be,

For i=n-1 to 1
    Pick and element in the range [0,i-1] randomly
    Swap the randomly picked element with a[i]
    // since it's not going to be reshuffled again 
    // as we are decrementing i , 
    // thus it's guaranteed that it won't be suggested twice 
    Recommend movie[a[i]]
Decrement i
End for loop

So, how this guarantees unique suggestion each time?

Because, we are fixing the i^th element after the swap and decrementing i, so that the movie that got suggested never takes part again in swaps.

C++ Implementation:

#include <bits/stdc++.h>
using namespace std;

void recommend_movie_randomly(vector<string> movies)
{
    srand(time(0));

    map<int, string> mymap;
    int n = movies.size();

    for (int i = 0; i < n; i++) {
        mymap[i] = movies[i];
    }

    vector<int> arr(n); //stores the indexes
    for (int i = 0; i < n; i++)
        arr[i] = i;

    //shiffling randomly and suggesting movie 
    //at each iteartion
    for (int i = n - 1; i >= 1; i--) {
        //j will be a random no with in range 0 to i-1
        int j = rand() % i;
        //swap ith index with jth
        int temp = arr[i];
        arr[i] = arr[j];
        arr[j] = temp;

        //suggest the ith movie now
        cout << "Suggesting next movie...\n";
        cout << mymap[arr[i]] << endl;
    }
}

int main()
{
    //input list
    vector<string> movie_list{ "D-DAY", "RAINCOAT", "OCTOBER", "LUNCHBOX", "BARFI", "RAAZI", "PIKU" };

    cout << "Recommending movies randomly from the list\n";

    recommend_movie_randomly(movie_list);

    return 0;
}

Output:

Recommending movies randomly from the list
Suggesting next movie...
RAAZI
Suggesting next movie...
OCTOBER
Suggesting next movie...
PIKU
Suggesting next movie...
D-DAY
Suggesting next movie...
RAINCOAT
Suggesting next movie...
LUNCHBOX