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

*, so that the movie that got suggested never takes part again in swaps.*

**i****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

TOP Interview Coding Problems/Challenges

- Run-length encoding (find/print frequency of letters in a string)
- Sort an array of 0's, 1's and 2's in linear time complexity
- Checking Anagrams (check whether two string is anagrams or not)
- Relative sorting algorithm
- Finding subarray with given sum
- Find the level in a binary tree with given sum K
- Check whether a Binary Tree is BST (Binary Search Tree) or not
- 1[0]1 Pattern Count
- Capitalize first and last letter of each word in a line
- Print vertical sum of a binary tree
- Print Boundary Sum of a Binary Tree
- Reverse a single linked list
- Greedy Strategy to solve major algorithm problems
- Job sequencing problem
- Root to leaf Path Sum
- Exit Point in a Matrix
- Find length of loop in a linked list
- Toppers of Class
- Print All Nodes that don't have Sibling
- Transform to Sum Tree
- Shortest Source to Destination Path

Comments and Discussions