DAY 92 - Can I serve my Customers

Hey Guys! This is an interview problem I recently faced in the online assessment test of a company that visited my university.
This is not a fully optimized approach but It did pass all the test cases.
The question was as follows:

Problem: "Can I Serve My Customers?"

Imagine you're running a store, and you have a list of customers, each with their shopping list. On the other hand, you have a set of shops with items they offer. You want to figure out how many of your customers you can serve with the available items in your shops. This problem can be elegantly solved using C++.

Understanding the Problem

Let's break down the problem step by step:

• You're given a list of customers, and each customer has a shopping list represented as a vector of items.

• You also have a list of shops, and each shop provides a set of items.

• The goal is to determine how many customers you can serve with the available items in your shops.

The Approach

We'll use C++ to efficiently solve this problem. Here's the intuition behind the approach:

1. Create a Set of Items: We start by creating an unordered set called items. This set will help us keep track of all the items available in our shops.

2. Insert Available Items: We iterate through each shop's item list and insert those items into the items set. This step ensures that we have a unique set of all available items.

3. Iterate Through Customers: Now, we iterate through each customer and check if we can serve them. We initially assume that we can serve a customer, and we'll set a flag to true.

4. Check Shopping List: For each customer, we look at their shopping list. If any item in their list is not found in our items set, we set the serving flag to false.

5. Count Served Customers: If the serving flag is still true after checking all items in a customer's list, it means we can serve them. We increment our serving counter.

6. Return the Result: Finally, we return the count of served customers.

Time and Space Complexity

Let's analyze the time and space complexity of our solution:

Time Complexity

• Inserting items into the items set from all shops takes O(m * k), where m is the number of shops and k is the average number of items in a shop.

• Iterating through all customers and checking their shopping lists takes O(n * p), where n is the number of customers and p is the average number of items in a customer's list.

• Overall, the time complexity is O(m * k + n * p).

Space Complexity

• The items set stores all available items from shops, and its size is determined by the number of unique items in all shops, which is O(m * k).

• We also use a few variables, which have constant space usage.

• Overall, the space complexity is O(m * k).

The Code in Action

Here's the C++ code that implements the above approach:

#include <iostream>
#include <unordered_set>
#include <vector>
using namespace std;

int canServe(const vector<vector<int>>& customers, const vector<vector<int>>& shops) {
    unordered_set<int> items;

    // Insert all available items in shops
    for (const auto& shop : shops) {
        for (int item : shop) {
            items.insert(item);
        }
    }

    int cnt = customers.size();
    for (const auto& customer : customers) {
        bool canServeCustomer = true; // Assume initially that the customer can be served.
        for (int item : customer) {
            if (items.find(item) == items.end()) {
                canServeCustomer = false;
                break;
            }
        }
        if (!canServeCustomer) {
            cnt--;
        }
    }

    return cnt;
}

int main() {
    // n = no of customers m = no of shops
    // p = no of items per customers k = no of items available per shop
    vector<vector<int>> customers = {{1, 2}, {1, 5}};
    vector<vector<int>> shops = {{1, 2, 3, 4}, {2, 3, 4, 5}, {1, 2, 4, 5}};

    cout << "Result: " << canServe(customers, shops) << endl;

    return 0;
}