1912: Design-Movie-Rental-System
Hard

table of contents

I need to dissect this new template and hash functionality that I copied off of Reddit (it technically should go under the “learnings” section but this is too important to miss):

template<class A, class B>
struct hash<pair<A, B>>{
    size_t operator() (const pair<A, B>& p) const {
        return rotl(hash<A>{}(p.first),1) ^
               hash<B>{}(p.second);
    }
};

template<> is used to simplify creating functions that work with multiple data types. In our case, we use template<class A, class B> to eventually specify a hash function that can work with two independent types.

template<class A, class B>

For example, std::unordered_map and std::unordered_set uses std::hash to hash many different types of values. Unfortunately, hash<pair<A, B>> is not defined by default, so we have to define a new hash in this format:

struct hash<pair<A, B>>{
    // function call operator: allows you to call `hash<pair<A, B>>(p);`
    size_t operator() (const pair<A, B>& p) const { 
        return ... // returns the platform-independent hash value
    }
};

Note, that the second const before the function body enforces read-only behaviour, helping guarantee thread safety for example.

Finally, for the hash function itself, we have:

return rotl(hash<A>{}(p.first),1) ^ hash<B>{}(p.second);

// note: using hash<A>(p.first) as an example
//       hash<A>{} initialises the hash object for type A
//       we can then use the object as a function and pass `p.first` as a parameter
//       to get the corresponding hash value

For an ideal hash function, we want:

Similar to most design questions, we need initialise multiple data structures to make our functions as efficient as possible.

unordered_map<pair<int, int>, int> moviePrice;              // {shop, movie} -> price
unordered_map<int, set<pair<int, int>>> unrentedMovies;     // movie -> {price, shop}
set<tuple<int, int, int>> rentedMovies;                     // {price, shop, movie}

Now onto some real code!

When we initialise our MovieRentingSystem, we want to populate our moviePrice and unrentedMovies data structures:

MovieRentingSystem(int n, vector<vector<int>>& entries) {
    for(vector<int>& entry : entries) {
        moviePrice[{entry[0], entry[1]}] = entry[2];
        unrentedMovies[entry[1]].insert({entry[2], entry[0]});
    }
}

Now, for the search function, we simply iterate through the first 5 elements of the set unrentedMovies[movie], as it contains the unrented movies sorted by price in ascending order (using the smaller shop as a tiebreaker):

vector<int> search(int movie) {
    vector<int> ans;
    auto& m : unrentedMovies[movie];
    int i = 0;
    for (auto it = m.begin(); it != m.end() && i < 5; ++it, ++i) {
        ans.push_back(it->second);
    }
    return ans;
}

Both rent and drop functions are very similar; you simply just movie the movie and its corresponding values from unrentedMovies to rentedMovies or vice versa:

void rent(int shop, int movie) {
    int price = moviePrice[{shop, movie}];
    unrentedMovies[movie].erase({price, shop});
    rentedMovies.insert({price, shop, movie});
}

void drop(int shop, int movie) {
    int price = moviePrice[{shop, movie}];
    unrentedMovies[movie].insert({price, shop});
    rentedMovies.erase({price, shop, movie});
    }

Finally, for the report function, it follows a similar format to search, where you simply iterate through the first 5 elements:

vector<vector<int>> report() {
    vector<vector<int>> ans;
    int i = 0;
    for (int it = rentedMovies.begin(); it != rentedMovies.end() && i < 5; ++it, ++i) {
        auto& [price, shop, movie] = *it;
        ans.emplace_back(shop, movie);
    }
    return ans;
}

code

template<class A, class B>
struct hash<pair<A, B>>{
    size_t operator() (const pair<A, B>& p) const {
        return rotl(hash<A>{}(p.first),1) ^
               hash<B>{}(p.second);
    }
};
class MovieRentingSystem {
public:
    MovieRentingSystem(int n, vector<vector<int>>& entries) {
        for(vector<int>& entry : entries) {
            moviePrice[{entry[0], entry[1]}] = entry[2];
            unrentedMovies[entry[1]].insert({entry[2], entry[0]});
        }
    }
    
    vector<int> search(int movie) {
        vector<int> ans;
        auto& m = unrentedMovies[movie];
        int i = 0;
        for (auto it = m.begin(); it != m.end() && i < 5; ++it, ++i) {
            ans.push_back(it->second);
        }
        return ans;
    }
    
    void rent(int shop, int movie) {
        int price = moviePrice[{shop, movie}];
        unrentedMovies[movie].erase({price, shop});
        rentedMovies.insert({price, shop, movie});
    }
    
    void drop(int shop, int movie) {
        int price = moviePrice[{shop, movie}];
        unrentedMovies[movie].insert({price, shop});
        rentedMovies.erase({price, shop, movie});
    }
    
    vector<vector<int>> report() {
        vector<vector<int>> ans;
        int i = 0;
        for (auto it = rentedMovies.begin(); it != rentedMovies.end() && i < 5; ++it, ++i) {
            auto &[price, shop, movie] = *it;
            ans.emplace_back(shop, movie);
        }
        return ans;
    }
private:
    unordered_map<pair<int, int>, int> moviePrice; 
    unordered_map<int, set<pair<int, int>>> unrentedMovies;
    set<tuple<int, int, int>> rentedMovies;
};

/**
 * Your MovieRentingSystem object will be instantiated and called as such:
 * MovieRentingSystem* obj = new MovieRentingSystem(n, entries);
 * vector<int> param_1 = obj->search(movie);
 * obj->rent(shop,movie);
 * obj->drop(shop,movie);
 * vector<vector<int>> param_4 = obj->report();
 */

complexity

learnings

time taken