lazy bartender problem solution

Daily Coding Problem: Problem #297 [Medium]

This problem was asked by Amazon.

At a popular bar, each customer has a set of favorite drinks, and will happily accept any drink among this set. For example, in the following situation, customer 0 will be satisfied with drinks 0, 1, 3, or 6.

preferences = {
    0: [0, 1, 3, 6],
    1: [1, 4, 7],
    2: [2, 4, 7, 5],
    3: [3, 2, 5],
    4: [5, 8]
}

A lazy bartender working at this bar is trying to reduce his effort by limiting the drink recipes he must memorize. Given a dictionary input such as the one above, return the fewest number of drinks he must learn in order to satisfy all customers.

For the input above, the answer would be 2, as drinks 1 and 5 will satisfy everyone.

Solution 1

Dynamic Programming using Recursion and Memoization

Solution written in c++

• First i arrange the given input into recipes and the count of customers interested in each recipe using c++ stl map – which i call cnt. Each recipe form the key of the map, while the count of customers interested in each recipe is assigned as the value for each key.
• Then i call Calc_Min_Recipe function passing two parameters: the map and the size of the given input.
• Calc_Min_Recipe is the recursive function. Here, what i want to achieve is find all possible combination of recipe set that satisfy all customers – note that each value of my map represent that set. For instance the given input gives me this map:

cnt[0] = 1 //only customer 0 interested in recipe 0
cnt[1] = 2 //only customers 0 and 1 interested in recipe 1
cnt[2] = 2 //only customers 2 and 3 interested in recipe 2
cnt[3] = 2 //only customers 0 and 3 interested in recipe 3
cnt[4] = 2 //only customers 1 and 2 interested in recipe 4
cnt[5] = 3 //only customers 2, 3 and 4 interested in recipe 5
cnt[6] = 1 //only customer 0 interested in recipe 6
cnt[7] = 2 //only customers 1 and 2 interested in recipe 7
cnt[8] = 1 //only customer 4 interested in recipe 4

All set sizes discovered must total to the no. of customers (and set elements must not repeat) – for our given input, all set sizes added together must equal 5. Possible combinations are: cnt[1], cnt[2] and cnt[8] i.e values: 2, 2, 1 totals 5 for the set elements (0, 1), (2, 3) and (4); another combination is: cnt[1] and cnt[5] i.e values: 2, 3 totals 5 for the set elements (0, 1) and (2, 3, 4).

int Calc_Min_Recipe(map<int, int> &m, int sz){
    static map<int, int> memo;//initialize memoization map

    //Our base cases//////
    if(m.empty()) return 1;//no particular reference, you can make 1 recipe for all custormers
    if(memo.count(sz)) return memo[sz];
    if(sz == 0) return 0;
    if(sz < 0) return sz;
    //base cases end here//

    int min_recipe = sz;//initialize to this incase every customers preference is unique

    for(auto x: m){
        int bal = sz - x.second;
        int result = Calc_Min_Recipe(m, bal);
        memo[bal] = result;//store result in memo map (used for memoization)
        int curr_min_recipe = result;
        if(curr_min_recipe >= 0) curr_min_recipe += 1;
        if(curr_min_recipe >= 0 && curr_min_recipe < min_recipe){
            min_recipe = curr_min_recipe;
        }
    }

    return min_recipe;
}

int Lazy_bartender(vector<vector<int>> &pref){
    map<int, int> cnt;
    int n = pref.size();

    /*This block of code arranges preferences into
    count of customers which each recipe satisfies*/
    for(int r=0;r<pref.size();r++){
        for(int c=0;c<pref[r].size();c++){
            cnt[pref[r][c]]++;
        }
    }

    int res = Calc_Min_Recipe(cnt, n);

    return res;
}
int main(){
    vector<vector<int>> preferences = {//returns 2
        {0, 1, 3, 6},
        {1, 4, 7},
        {2, 4, 7, 5},
        {3, 2, 5},
        {5, 8}
    };
    /*vector<vector<int>> preferences = {//returns 1
        {0, 1},
        {1}
    };*/
    /*vector<vector<int>> preferences = {//returns 2
        {5, 3},
        {5, 4},
        {5, 4},
        {5, 4},
        {5, 3},
        {6, 4},
        {7, 3}
    };*/
    /*vector<vector<int>> preferences = {//same preferences - returns 1
        {5, 3, 4, 6, 7},
        {5, 3, 4, 6, 7},
        {5, 3, 4, 6, 7},
        {5, 3, 4, 6, 7},
        {5, 3, 4, 6, 7},
        {5, 3, 4, 6, 7},
        {5, 3, 4, 6, 7}
    };*/
    /*vector<vector<int>> preferences = {//unique preferences - returns 5
        {5},
        {3},
        {4},
        {6},
        {7}
    };*/
    /*vector<vector<int>> preferences = {//no preferences - returns 1
        {},
        {},
        {},
        {},
        {}
    };*/
    int result = Lazy_bartender(preferences);
    cout<<"The minimum recipe required is : "<<result;
    return 0;
}

For our given input, the answer is 2 i.e cnt[1] and cnt[5]; values: 2, 3 with the set elements (0, 1) and (2, 3, 4).

Solution 2

Solution written in c++

• Start by arranging customer preferences into recipes and customers which each recipe satisfies using a map.
• Get map key/value pair with the maximum value repeatedly – this is the recipe with the maximum customers preference.
• In each pass, skip, if a customer from the previous max set belongs to new max set
• Otherwise, increment count of minimum_recipe required because you just found a recipe satisfying most customers
• Keep track of what i call final_max in each pass. Once final_max equals the input size, a set of recipe satisfying all customers has been found.

bool does_cust_belong_to_prev_recipe_set(int c, vector<int> &old_set){
    if(old_set.size() == 0) return false;//base case
    for(int x: old_set){//go through old_set and compare with c
        if(c == x){
            return true;
        }
    }
    return false;
}
int Lazy_bartender(vector<vector<int>> &pref){
    map<int, int> recipes;
    map<int, vector<int>> recipe_satisfies;
    map<int, int> cnt;
    vector<int> v;
    vector<int> cust_bal;
    int result = 0;
    priority_queue<int> q;

    /*This block of code arranges preferences into
    recipes and the customers which each recipe satisfies*/
    for(int r=0;r<pref.size();r++){
        for(int c=0;c<pref[r].size();c++){
            if(recipes.count(pref[r][c])){//if recipe exist
                v = recipe_satisfies[pref[r][c]];
                v.push_back(r);
                recipe_satisfies[pref[r][c]] = v;
                //increment cnt of customers to each recipe
                cnt[pref[r][c]]++;
            }else{//recipe does not exist
                recipes[pref[r][c]] = 1;
                v = recipe_satisfies[pref[r][c]];
                v.push_back(r);
                recipe_satisfies[pref[r][c]] = v;
                //increment cnt of customers to each recipe
                cnt[pref[r][c]]++;
            }
        }
    }

    if(cnt.empty()) return 1;//no particular reference, you can make 1 recipe for all custormers

    int max = 0;
    int recipe_max_cust;
    int recipe_max_cust_old = -1;
    bool res = false;
    vector<int> c_old;
    static int final_max;
    map<int, int> cnt_left;
    while(!cnt.empty()){//as far as map is not empty
        for(auto x: cnt){//get recipe set with max customers
            if(x.second > max){
                max = x.second;
                recipe_max_cust = x.first;
            }
        }
        //skip, if a customer from the previous max set belongs to new max set
        for(auto c: recipe_satisfies[recipe_max_cust]){
            if(recipe_satisfies.count(recipe_max_cust_old)){//if key exist
                c_old = recipe_satisfies[recipe_max_cust_old];
            }
            res = does_cust_belong_to_prev_recipe_set(c, c_old);
            if(res == true){
                cnt_left[recipe_max_cust] = cnt[recipe_max_cust];
                break;
            }
        }

        if(res == true){
            cnt.erase(recipe_max_cust);//delete key that has been considered
            max = 0;//reset max
            continue;//don't consider this set
        }
        //otherwise, recipe satisfying most customers has been found, increment count of minimum_recipe required
        if(recipe_max_cust_old == -1){
            recipe_max_cust_old = recipe_max_cust;
        }
        //increment result by 1
        result += 1;
        final_max += max;
        if(final_max == pref.size()){//A set of recipe satisfying all customers has been found
            //reset all variables
            cnt = cnt_left;//reset cnt
            //reset cnt_left (by deleting all items in the map)
            cnt_left.clear();
            final_max = 0;
            c_old = {};
            max = 0;//reset max
            recipe_max_cust_old = -1;//reset
            q.push(-result);//store result for the completed set of minimum recipe that bartender has to learn
            result = 0;
            //recipe mix is completed for 1 set - see if you can get another set
            continue;
        }
        cnt.erase(recipe_max_cust);//delete key that has been considered
        max = 0;//reset max
        //recipe_satisfies(recipe_satisfies);
    }

    result = abs(q.top());//get set count with the minimum - this is the minimum recipe mix that bartender has to learn to satisfy every customer
    return result;
}