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 ith 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

Also tagged in: Synopsys






Comments and Discussions

Ad: Are you a blogger? Join our Blogging forum.





Languages: » C » C++ » C++ STL » Java » Data Structure » C#.Net » Android » Kotlin » SQL
Web Technologies: » PHP » Python » JavaScript » CSS » Ajax » Node.js » Web programming/HTML
Solved programs: » C » C++ » DS » Java » C#
Aptitude que. & ans.: » C » C++ » Java » DBMS
Interview que. & ans.: » C » Embedded C » Java » SEO » HR
CS Subjects: » CS Basics » O.S. » Networks » DBMS » Embedded Systems » Cloud Computing
» Machine learning » CS Organizations » Linux » DOS
More: » Articles » Puzzles » News/Updates


© https://www.includehelp.com some rights reserved.