×

String Coding Problems

Arrays Coding Problems

Sorting Coding Problems

Searching Coding Problems

Coding Algorithms

Tree Coding Problems

Stack Coding Problems

Linked list Coding Problems

Graph Coding Problems

Greedy Algorithms Coding Problems

Dynamic Programming Coding Problems

Matrix Coding Problems

Recursion Coding Problems

Number Theory Coding Problems

Backtracking Coding Problems

Heap Coding Problems

Brute Force Coding Problems

Implementation Coding Problems

Google Contests

Competitive Programming Coding

Miscellaneous

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!

Load comments ↻





Copyright © 2024 www.includehelp.com. All rights reserved.