# 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.

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