Filter Restaurants by Vegan-Friendly, Price and Distance

Medium

Yelp

0 views

Topics:

Arrays

Given the array restaurants where restaurants[i] = [id_i, rating_i, veganFriendly_i, price_i, distance_i]. You have to filter the restaurants using three filters.

The veganFriendly filter will be either true (meaning you should only include restaurants with veganFriendly_i set to true) or false (meaning you can include any restaurant). In addition, you have the filters maxPrice and maxDistance which are the maximum value for price and distance of restaurants you should consider respectively.

Return the array of restaurant IDs after filtering, ordered by rating from highest to lowest. For restaurants with the same rating, order them by id from highest to lowest. For simplicity veganFriendly_i and veganFriendly take value 1 when it is true, and 0 when it is false.

Example 1:

Input: restaurants = [[1,4,1,40,10],[2,8,0,50,5],[3,8,1,30,4],[4,10,0,10,3],[5,1,1,15,1]], veganFriendly = 1, maxPrice = 50, maxDistance = 10
Output: [3,1,5] 
Explanation: 
The restaurants are:
Restaurant 1 [id=1, rating=4, veganFriendly=1, price=40, distance=10]
Restaurant 2 [id=2, rating=8, veganFriendly=0, price=50, distance=5]
Restaurant 3 [id=3, rating=8, veganFriendly=1, price=30, distance=4]
Restaurant 4 [id=4, rating=10, veganFriendly=0, price=10, distance=3]
Restaurant 5 [id=5, rating=1, veganFriendly=1, price=15, distance=1] 
After filter restaurants with veganFriendly = 1, maxPrice = 50 and maxDistance = 10 we have restaurant 3, restaurant 1 and restaurant 5 (ordered by rating from highest to lowest).

Example 2:

Input: restaurants = [[1,4,1,40,10],[2,8,0,50,5],[3,8,1,30,4],[4,10,0,10,3],[5,1,1,15,1]], veganFriendly = 0, maxPrice = 50, maxDistance = 10
Output: [4,3,2,1,5]
Explanation: The restaurants are the same as in example 1, but in this case the filter veganFriendly = 0, therefore all restaurants are considered.

Example 3:

Input: restaurants = [[1,4,1,40,10],[2,8,0,50,5],[3,8,1,30,4],[4,10,0,10,3],[5,1,1,15,1]], veganFriendly = 0, maxPrice = 30, maxDistance = 3
Output: [4,5]

Constraints:

1 <= restaurants.length <= 10^4
restaurants[i].length == 5
1 <= id_i, rating_i, price_i, distance_i<= 10^5
1 <= maxPrice, maxDistance <= 10^5
veganFriendly_i and veganFriendly are 0 or 1.
All id_i are distinct.

Try coding it in LeetCode

Filter Restaurants by Vegan-Friendly, Price and Distance

Medium

Yelp

0 views

Topics:

Arrays

Given the array restaurants where restaurants[i] = [id_i, rating_i, veganFriendly_i, price_i, distance_i]. You have to filter the restaurants using three filters.

The veganFriendly filter will be either true (meaning you should only include restaurants with veganFriendly_i set to true) or false (meaning you can include any restaurant). In addition, you have the filters maxPrice and maxDistance which are the maximum value for price and distance of restaurants you should consider respectively.

Return the array of restaurant IDs after filtering, ordered by rating from highest to lowest. For restaurants with the same rating, order them by id from highest to lowest. For simplicity veganFriendly_i and veganFriendly take value 1 when it is true, and 0 when it is false.

Example 1:

Input: restaurants = [[1,4,1,40,10],[2,8,0,50,5],[3,8,1,30,4],[4,10,0,10,3],[5,1,1,15,1]], veganFriendly = 1, maxPrice = 50, maxDistance = 10
Output: [3,1,5] 
Explanation: 
The restaurants are:
Restaurant 1 [id=1, rating=4, veganFriendly=1, price=40, distance=10]
Restaurant 2 [id=2, rating=8, veganFriendly=0, price=50, distance=5]
Restaurant 3 [id=3, rating=8, veganFriendly=1, price=30, distance=4]
Restaurant 4 [id=4, rating=10, veganFriendly=0, price=10, distance=3]
Restaurant 5 [id=5, rating=1, veganFriendly=1, price=15, distance=1] 
After filter restaurants with veganFriendly = 1, maxPrice = 50 and maxDistance = 10 we have restaurant 3, restaurant 1 and restaurant 5 (ordered by rating from highest to lowest).

Example 2:

Input: restaurants = [[1,4,1,40,10],[2,8,0,50,5],[3,8,1,30,4],[4,10,0,10,3],[5,1,1,15,1]], veganFriendly = 0, maxPrice = 50, maxDistance = 10
Output: [4,3,2,1,5]
Explanation: The restaurants are the same as in example 1, but in this case the filter veganFriendly = 0, therefore all restaurants are considered.

Example 3:

Input: restaurants = [[1,4,1,40,10],[2,8,0,50,5],[3,8,1,30,4],[4,10,0,10,3],[5,1,1,15,1]], veganFriendly = 0, maxPrice = 30, maxDistance = 3
Output: [4,5]

Constraints:

1 <= restaurants.length <= 10^4
restaurants[i].length == 5
1 <= id_i, rating_i, price_i, distance_i<= 10^5
1 <= maxPrice, maxDistance <= 10^5
veganFriendly_i and veganFriendly are 0 or 1.
All id_i are distinct.

Try coding it in LeetCode

Solution

Clarifying Questions

When you get asked this question in a real-life environment, it will often be ambiguous (especially at FAANG). Make sure to ask these questions in that case:

What are the possible ranges for restaurant IDs, ratings, veganFriendly, price, and distance? Are they all non-negative integers?
What should I return if no restaurants satisfy the filter criteria? An empty list?
Can the `restaurants` list be empty or null?
If multiple restaurants have the same rating and ID, how should I handle that? Is it even possible to have the same rating and ID?
Is `veganFriendly` strictly 0 or 1, or can it be other integer values? If other values are possible, how should they be interpreted with regards to vegan-friendliness?

Brute Force Solution

Approach

We want to find restaurants that meet certain criteria. The brute force method checks every restaurant, one by one, to see if it's a match. It's like going through a list and saying 'yes' or 'no' to each item.

Here's how the algorithm would work step-by-step:

Start with an empty list of good restaurants.
Take the first restaurant from the big list of all restaurants.
Check if this restaurant is vegan-friendly based on the given requirement. If a specific preference is given, confirm that the restaurant meets that specific preference.
Check if the price of this restaurant is within the allowed price range.
Check if the distance to this restaurant is within the allowed distance.
If the restaurant meets all the criteria (vegan-friendly, price, and distance), add it to the list of good restaurants.
Repeat steps 2 through 6 for every restaurant in the big list.
Once you've checked all the restaurants, you'll have a list of all the 'good' restaurants that meet your criteria.
Return the list of good restaurants.

Code Implementation

def filter_restaurants(restaurants, vegan_friendly, max_price, max_distance):
    good_restaurants = []

    for restaurant in restaurants:
        restaurant_id, vegan_friendliness, price, distance = restaurant

        # Check vegan friendliness, handling 'any' preference
        if vegan_friendly == 1 and vegan_friendliness == 0:
            continue

        # Ensure the price is within the allowed limit
        if price > max_price:
            continue

        # Filter out restaurants exceeding the maximum distance
        if distance > max_distance:
            continue

        good_restaurants.append(restaurant_id)

    return good_restaurants

Big(O) Analysis

Time Complexity

O(n) – The provided solution iterates through each restaurant in the input list of restaurants once. Let n be the number of restaurants in the input list. For each restaurant, the algorithm performs a fixed number of checks (vegan-friendliness, price, and distance) which take constant time. Therefore, the overall time complexity is directly proportional to the number of restaurants, resulting in O(n).

Space Complexity

O(N) – The algorithm creates a new list to store the 'good' restaurants that meet the criteria. In the worst-case scenario, all N restaurants in the input list might satisfy the conditions and be added to this new list. Therefore, the auxiliary space required is proportional to the number of restaurants in the input list, which we denote as N. This results in an auxiliary space complexity of O(N).

Optimal Solution

Approach

We need to find the best restaurants based on whether they're vegan-friendly, how expensive they are, and how far away they are. We'll start by filtering out restaurants that don't meet the vegan requirement, then sort the remaining ones based on a combination of rating and distance, with closer restaurants getting a slight advantage.

Here's how the algorithm would work step-by-step:

First, check each restaurant to see if it meets the 'vegan-friendly' requirement. If a restaurant isn't vegan-friendly enough (based on the input), we simply ignore it and move on.
Now that we only have vegan-friendly restaurants, we need to sort them to find the 'best'. The problem asks us to sort by rating first, so we will start there.
If some restaurants have the same rating, we want to prefer the restaurants that are closer. So, when two restaurants have the same rating, we'll pick the one with the shorter distance.
Finally, we return the restaurant IDs in the order determined in the previous steps. This gives us the list of the 'best' vegan-friendly restaurants sorted by rating and then distance.

Code Implementation

def filter_restaurants(restaurants, vegan_friendly, max_price, max_distance):
    filtered_restaurants = []

    for restaurant_id, rating, is_vegan, price, distance in restaurants:
        is_acceptable = True

        # Filter based on vegan_friendly preference.
        if vegan_friendly == 1 and is_vegan == 0:
            is_acceptable = False

        if price > max_price:
            is_acceptable = False

        if distance > max_distance:
            is_acceptable = False

        if is_acceptable:
            filtered_restaurants.append((restaurant_id, rating, distance))

    # Sort by rating (descending) and then distance (ascending).
    filtered_restaurants.sort(key=lambda x: (x[1], -x[2]), reverse=True)

    # Extract the restaurant IDs from the sorted list.
    result = [restaurant_id for restaurant_id, _, _ in filtered_restaurants]

    return result

Big(O) Analysis

Time Complexity

O(n log n) – The initial filtering of restaurants based on vegan-friendliness iterates through the input list of n restaurants once, taking O(n) time. The dominant operation is the sorting of the filtered restaurants. Sorting algorithms like mergesort or quicksort, commonly used in standard library sort functions, have a time complexity of O(n log n), where n is the number of restaurants remaining after filtering. Therefore, the overall time complexity is dominated by the sorting step, resulting in O(n log n).

Space Complexity

O(N) – The provided solution filters the restaurants into a new list containing only vegan-friendly restaurants. In the worst-case scenario, all N restaurants could be vegan-friendly, resulting in a temporary list of size N. Additionally, the sorting algorithm, depending on the implementation, might use additional space, but a stable in-place sorting algorithm can be assumed which does not significantly impact the auxillary space. Therefore, the auxiliary space used is dominated by the size of the temporary list containing filtered restaurants, which is proportional to N.

Edge Cases

Case	How to Handle
restaurants is null or empty	Return an empty list if restaurants is null or empty, as there are no restaurants to filter.
veganFriendly is not 0 or 1	Treat veganFriendly values other than 0 or 1 as if it were 0 (any restaurant is acceptable) or reject the input.
maxPrice or maxDistance are negative	Reject the input or treat them as 0, assuming negative prices or distances are invalid.
All restaurants are filtered out (no valid restaurants)	The algorithm should correctly return an empty list when no restaurants satisfy the given criteria.
Restaurants have identical ratings	The solution correctly sorts these by their IDs in descending order.
Restaurants have identical IDs	The problem statement should clarify how to handle duplicate restaurant IDs. The last seen restaurant with an id should be used.
Integer overflow in rating or ID leading to incorrect sorting	Use appropriate data types and avoid operations that could lead to integer overflow and ensure consistent results across different compilers.
Large input size that affects time or memory complexity	Use an efficient sorting algorithm (e.g., merge sort or quick sort with O(n log n) time complexity) and avoid unnecessary memory allocation for optimal performance.