Filter Restaurants by Vegan-Friendly, Price and Distance

Filter Restaurants by Vegan-Friendly, Price and Distance

What is this problem about?

The Filter Restaurants interview question asks you to filter a list of restaurants based on three user preferences: whether they are vegan-friendly, their maximum price, and their maximum distance. After filtering, you must return the IDs of the qualifying restaurants, sorted by their rating in descending order. If two restaurants have the same rating, the one with the higher ID comes first.

Why is this asked in interviews?

Companies like Yelp ask the Filter Restaurants coding problem to test your ability to handle multi-level sorting and filtering. It evaluates how you organize your logic to process multiple constraints and whether you can use custom comparators efficiently. It's a practical problem that mirrors real-world search and recommendation systems.

Algorithmic pattern used

This problem follows a Filter and Sort pattern.

1. Filtering: Iterate through the list of restaurants and check:
   • If veganFriendly is 1, the restaurant must also have veganFriendly as 1. If 0, any restaurant is fine.
   • price <= maxPrice.
   • distance <= maxDistance.
2. Sorting: For all qualifying restaurants, sort them using a custom comparator:
   • Primary key: rating (descending).
   • Secondary key: id (descending).
3. Extraction: Return the list of IDs from the sorted result.

Example explanation

Restaurants: [[1, 4, 1, 10, 5], [2, 8, 0, 50, 10], [3, 8, 1, 30, 4]] (ID, Rating, Vegan, Price, Distance) Preferences: veganFriendly=1, maxPrice=40, maxDistance=10.

1. Restaurant 1: Vegan=1, Price=10, Dist=5. (Fits!).
2. Restaurant 2: Vegan=0. (Filtered out because user wants vegan).
3. Restaurant 3: Vegan=1, Price=30, Dist=4. (Fits!). Sorted Qualifying:

• ID 3 (Rating 8)
• ID 1 (Rating 4) Result: [3, 1].

Common mistakes candidates make

• Logic error in Vegan filter: Assuming veganFriendly=0 means the user only wants non-vegan restaurants. Usually, 0 means the user doesn't care.
• Sorting order: Sorting by ID or rating in ascending order instead of descending.
• Efficiency: Re-sorting the entire list before filtering (it's much faster to filter first, then sort the smaller resulting set).

Interview preparation tip

Practice using custom comparators in your language of choice (e.g., lambda in Python, Comparator in Java). Multilevel sorting is a very common requirement in production code.