Design Movie Rental System

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:

• fast calculations
  • we use a XOR operation
• minimal collisions
  • use the std::rotl function, which applies a bitwise rotation left on the hash value of p.first by 1 bit
    • spread out hash values more uniformly
    • e.g. hash<A>(p.first) and hash<B>(p.second) might have similar hash values, potentially leading to more hash collisions when both values are XOR together

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

• we need to have two priority_queue; one to track rented movies, and another to track unrented movies
  • however, we have no way of adding and removing specific movies from a priority_queue
  • a priority_queue also gives us no way of iterating through the first 5 elements
  • solution?
    • since each shop can only have one copy of a movie, we can use a sorted set to handle both priority_queue. Therefore, we have:
      • unrentedMovies (unordered_map<int, set<pair<int, int>>>) to keep track of the stores that own the cheapest unrented copies of a specific movie
      • rentedMovies (set<tuple<int, int, int>>) to keep track of cheapest rented movies
• for both the rent and drop functions, we need a way of retrieving the movie's price when given the shop and movie
  • moviePrice (unordered_map<pair<int, int>, int>) allows you to find the price, making use of the hash function defined above

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

• search
  • Time: O(1)
  • Space: O(1)
• rent
  • Time: O(log(n)) where n denotes the number of movies
  • Space: O(1)
• drop
  • Time: O(log(n))
  • Space: O(1)
• report
  • Time: O(1)
  • Space: O(1)
• overall
  • Space: O(n)

learnings

• too much... too much to learn

time taken

• too long... too long to complete