Amazon Phone Screening SDE 2

Round 1

Questions: Given a vector of vectors in the form {{M_I, c_i, p_i}, {M_I, c_i, p_i}, {M_I, c_i, p_i}}, each tuple represents information about unrented movies, where:

• M_I is the movie ID,
• c_i is the channel ID, and
• p_i is the price of renting that movie from the given channel.

You need to implement two operations:

1. search(movie_id): Returns the 5 cheapest channel IDs for the specified unrented movie.
2. rent(movie_id, channel_id): Marks the movie as rented from the specified channel, so it will no longer appear in future search results for that movie.

Solution:

• Map of Unrented Movies: A map that keeps track of unrented movies, where the key is the movie ID and the value is a priority queue (min-heap) that stores channels and prices for that movie.
• Rented Set: A set or map to track rented movies by their (movie_id, channel_id) pair to make sure we exclude rented movies from the search results.

#include <iostream>
#include <vector>
#include <queue>
#include <unordered_map>
#include <set>

using namespace std;

struct MovieInfo {
    int movie_id;
    int channel_id;
    int price;
    
    bool operator>(const MovieInfo& other) const {
        return price > other.price; // Min-heap based on price
    }
};

class MovieRentalSystem {
public:
    unordered_map<int, priority_queue<MovieInfo, vector<MovieInfo>, greater<MovieInfo>>> unrented_movies;

    set<pair<int, int>> rented_set;
    
    MovieRentalSystem(vector<vector<int>>& movie_info) {
        for (auto& info : movie_info) {
            int movie_id = info[0];
            int channel_id = info[1];
            int price = info[2];
            
            unrented_movies[movie_id].push({movie_id, channel_id, price});
        }
    }
    
    vector<int> search(int movie_id) {
        vector<int> result;
        
        if (unrented_movies.find(movie_id) == unrented_movies.end()) {
            return result; // No such movie available
        }

        auto movie_queue = unrented_movies[movie_id];
        int count = 0;

        while (!movie_queue.empty() && count < 5) {
            MovieInfo top_movie = movie_queue.top();
            movie_queue.pop();

            if (rented_set.find({top_movie.movie_id, top_movie.channel_id}) == rented_set.end()) {
                result.push_back(top_movie.channel_id);
                count++;
            }
        }
        
        return result;
    }
    
    void rent(int movie_id, int channel_id) {
        rented_set.insert({movie_id, channel_id});
    }
};