Low level design: Food delivery app like zomato, swiggy, Door Dash
See the problem statement here : https://codezym.com/question/5
In a food delivery app like zomato, swiggy, door dash etc, customers mostly do 3 things
Order food :
orderFood(String orderId, String restaurantId, String foodItemId)Rate order :
rateOrder(String orderId, int rating)rating will be 1 to 5 stars.Fetch restaurants list.
Fetch top rated restaurants :
getTopRatedRestaurants()Fetch restaurants which have the best rating for a particular food item :
getTopRestaurantsByFood(String foodItemId)
Other use-cases:
Add food item :
addFoodItem(String foodItemId, double price, String foodItemName)Add Restaurant :
addRestaurant(String restaurantId, List<String> foodItemIds, String name, String address)
Here the main problem which we are solving is correctly updating views for both fetch restaurants queries while orders are simultaneously rated in a multithreaded environment.
We can use observer design pattern here. Concepts from model view controller (MVC) design pattern can also be useful.
Separating views from data storage:
Key insight is to separate the views from data storage and update. This will simplify our solution and make it easier to add new views.
Observer pattern has two parts: Subject and Observers
Subject will keep track of all data updates and send those updates to all observers
Each observer will receive update from subject and will update their view.
Solution:
Let's have a class
OrdersManagerwhich will store orders and ratings for each order.OrdersManagerwill also be our subject in observer pattern.class OrdersManager implements RateOrderSubjectClasses which will store each view will be observers. For this problem we need two views. Both below classes will receive updates from
OrdersManagerand update their views.List of most rated restaurants :
class MostRatedRestaurants implements RateOrderObserverList of most rated restaurants for a particular food item:
class MostRatedRestaurantsByFood implements RateOrderObserver
Benefit of above design is: Let's suppose we need a new view like list of restaurants with maximum number of 5 star ratings for a particular food item. e.g. restaurants from which Biryani has been rated 5 star most number of times. We can simply create a new class with proper logic e.g. class MostFiveStarRatedRestaurantsByFood implements RateOrderObserver
And then we add
MostFiveStarRatedRestaurantsByFoodas an observer inOrdersManagerso that it receives updates when a new order is rated.MostFiveStarRatedRestaurantsByFoodwill receive all updates and will only process updates with 5-star ratings.
Fetching results from views:
Class RestaurantSearchManager will initialize and manage both above fetch restaurants.
It will receive all the getRestaurants queries and fetch results from appropriate view class.
Concept is similar to strategy design pattern.
Implementation of view classes:
Most rated restaurants: class MostRatedRestaurants
This class keeps restaurantId vs ratings map.
ConcurrentHashMap<String, Rating> ratingsMap. This map efficiently stores ratings for restaurants in a multithreaded environment.But it is not efficient for building list of top rated restaurants. Basically you have to go through all restaurants and sort them by rating.
We can keep top rated restaurants in a heap (
TreeSetin java), but managing it efficiently in a multithreaded is tricky and bug prone. Lets discuss this in comments section.What I have done in current solution is to divide restaurants by ratings and keep restaurants with same rating together.
So all restaurants with rating 5.0 will be together, followed by all restaurants with rating 4.9 then 4.8 and so on. When we need to build a list of top n restaurants, we pick all restaurants with rating 5.0 then all restaurants with rating 4.9 and so on.
Our data structure will be
ArrayList<HashSet> ratingDivisonstotal number of rating values will be 41, i.e. 1.0, 1.1, 1.2 .... 4.8, 4.9, 5.0,
ratingDivisons.get(0) will keep all restaurants with rating 1.0,
ratingDivisons.get(1) will keep all restaurants with rating 1.1 ....and so on
ratingDivisons.get(39) will keep all restaurants with rating 4.9
ratingDivisons.get(40) will keep all restaurants with rating 5.0
With above data structure, a list of top restaurants of size n can be built in O(n) time.
rating update of any restaurant is also in O(1). If an order is rated and restaurant's rating doesn't change then you don't have to do anything.
When average rating changes: Lets suppose earlier restaurant's rating was 4.1 and after receiving a rating of 5 it became 4.2 , so we simply lock ratingDivisons.get(31) using synchronized keyword, remove restaurantId from it and then add restaurantId to ratingDivisons.get(32). Both operations are O(1) i.e. fairly efficient. And we can have the maximum parallelism of 41 i.e. number of items in ratingDivisons.
Most rated restaurants by food: class MostRatedRestaurantsByFood
We can keep Map inside a map food ids vs restaurantId and rating
Map<foodId, Map<restaurantId, rating>> ratingsfor each foodId basically we are keeping list of all restaurants with their rating.
rating update to this data structure can be done in O(1) but for fetching list of most rated restaurants for a particular food item is not so efficient.
As an ending exercise Why don't you come up with a better data structure for building the list of top rated restaurants and discuss in comments.. I will wait to see the amazing solutions which people suggest for this problem.
Complete Code :
You can run and test below code on CodeZym: https://codezym.com/question/5
All important classes are already discussed above.
// ****** It's better to write code in your local code editor and paste it back here *********
// put all import statements at the top, else it will give compiler error
import java.util.*;
import java.util.concurrent.ConcurrentHashMap;
import java.util.concurrent.atomic.AtomicInteger;
interface RateOrderObserver{
void update(Order order);
}
interface RateOrderSubject{
void addObserver(RateOrderObserver observer);
void notifyAll(Order order);
}
/**
* - All the methods of this class will be tested in a MULTI-THREADED environment.
* - If you are creating new interfaces, then they have to be declared on the top, even before class Solution, else it will give class not found error for classes implementing them.
* - use helper.print("") or helper.println("") for printing logs else logs will not be visible.
*/
public class Solution implements Q05RestaurantRatingInterface {
private Helper05 helper;
private FoodManager foodManager;
private RestaurantManager restaurantManager;
private RestaurantSearchManager restaurantSearchManager;
private OrdersManager ordersManager;
// constructor must always be public, don't remove the public keyword
public Solution(){}
/**
* Use this method to initialize your instance variables
* @param helper
*/
public void init(Helper05 helper){
this.helper=helper;
foodManager = new FoodManager();
restaurantManager = new RestaurantManager();
ordersManager = new OrdersManager();
restaurantSearchManager = new RestaurantSearchManager(ordersManager);
// helper.println("restaurant rating module initialized");
}
/**
* - adds a new food item. Same food item can be sold by many restaurants.
* - for simplicity lets assume that food item's price is same in all restaurants.
* @param foodItemId it will always be a non null, non blank unique string
* @param price e.g 240
* @param foodItemName e.g. Masala Dosa, Pizza, Burger, Sandwich etc
*/
public void addFoodItem(String foodItemId, double price, String foodItemName) {
foodManager.addFoodItem(foodItemId, price, foodItemName);
}
/**
* adds a new restaurant.
* @param restaurantId it will always be a non null, non blank unique string
* @param foodItemIds it is a list of id's of food items that have already been added
* @param name name of the restaurant e.g. Burger King
* @param address e.g. connaught place, delhi
*/
public void addRestaurant(String restaurantId, List<String> foodItemIds, String name, String address) {
restaurantManager.addRestaurant(restaurantId, foodItemIds, name, address);
}
/**
* Orders food item from a restaurant.
* - for now lets assume for that only a single food item is purchased in one order.
* - orderId, restaurantId, foodItemId will all be valid and available.
* @param restaurantId restaurant from where food is being ordered.
* @param foodItemId food item which is being ordered
*/
public void orderFood(String orderId, String restaurantId, String foodItemId) {
ordersManager.orderFood(orderId,restaurantId, foodItemId);
}
/**
* Customers can rate their order.
* - when you are giving rating an order e.g giving 4 stars to an orders then it means you are assigning 4 stars to both the food item in that restaurant as well as 4 stars to the overall restaurant ranting.
* @param orderId order which will be rated by customer, orderId will always be valid i.e. order will always be created for an orderId before rateOrder() is called.
* @param rating ranges from 1 to 5 stars in increasing order, 1 being the worst and 5 being the best rating.
*/
public void rateOrder(String orderId, int rating) {
ordersManager.rateOrder(orderId, rating);
}
/**
* - Fetches a list of top 20 restaurants based on strategy
* - unrated restaurants will be at the bottom of list.
* - restaurants will be sorted on the basis of strategy
* - restaurants are sorted in descending order on average ratings of the food item and then based on restaurant id lexicographically
* - e.g. veg burger is rated 4.3 in restaurant-4 and 4.6 in restaurant-6 then we will return ['restaurant-6', 'restaurant-4']
* @param foodItemId food item for which restaurants need to be fetched.
* - lets assume that in all below examples in strategy we are talking about 'food-item-1': Veg Burger
*/
public List<String> getTopRestaurantsByFood(String foodItemId) {
List<String> list = restaurantSearchManager.getRestaurantsByFood(foodItemId, 20);
return list;//.subList(1, list.size());
}
/**
* - returns top 20 most rated restaurants ids sorted in descending order of their ratings.
* - ratings are rounded down to 1 decimal point, i.e. 4.05, 4.08, 4.11, 4.12,4.14 all become 4.1,
* 4.15, 4.19,4.22,4.24 all become 4.2
* - if two restaurants have the same rating then they will be ordered lexicographically by their restaurantId.
* - Here we are talking about restaurant's overall rating and NOT food item's rating.
* - e.g. restaurant-2 is rated 4.6 while restaurant-3 is rated 4.2 and restaurant-5 is rated 4.4 and restaurant-6 is rated 4.6, we will return ['restaurant-2','restaurant-6', 'restaurant-5', 'restaurant-3']
* - even though restaurant-2 and restaurant-6 have same rating , restaurant-6 came later because it is lexicographically greater than restaurant-2
*/
public List<String> getTopRatedRestaurants() {
List<String> list = restaurantSearchManager.getTopRatedRestaurants(20);
return list;//.subList(1, list.size());
}
}
class FoodManager{
private ConcurrentHashMap<String, FoodItem> map = new ConcurrentHashMap<>();
void addFoodItem(String foodItemId, double price, String foodItemName){
FoodItem food = new FoodItem(foodItemId, foodItemName, price);
map.put(foodItemId, food);
}
}
class RestaurantManager{
// food id vs list of restaurant ids
private ConcurrentHashMap<String, ArrayList<String>> map = new ConcurrentHashMap<>();
void addRestaurant(String restaurantId,
List<String> foodItemIds, String name, String address){
for(String foodItemId : foodItemIds)
if(foodItemId!=null && !foodItemId.isBlank()){
map.putIfAbsent(foodItemId, new ArrayList<>());
ArrayList<String> list = map.get(foodItemId);
synchronized (list){
list.add(restaurantId);
}
}
}
List<String> getAllRestaurants(String foodItemId){
if(foodItemId==null || foodItemId.isBlank()) return new ArrayList<>();
return map.getOrDefault(foodItemId, new ArrayList<>());
}
}
class OrdersManager implements RateOrderSubject{
private ConcurrentHashMap<String, Order> map = new ConcurrentHashMap<>();
private ArrayList<RateOrderObserver> observers = new ArrayList<>();
void orderFood(String orderId, String restaurantId, String foodItemId){
Order order = new Order(orderId, restaurantId, foodItemId, 0);
map.put(orderId, order);
}
void rateOrder(String orderId, int rating){
Order order = map.get(orderId);
order.setRating(rating);
notifyAll(order);
}
public void addObserver(RateOrderObserver observer) {
observers.add(observer);
}
public void notifyAll(Order order) {
for(RateOrderObserver observer : observers) observer.update(order);
}
}
class RestaurantSearchManager {
private MostRatedRestaurants mostRatedRestaurants;
private MostRatedRestaurantsByFood mostRatedRestaurantsByFood;
RestaurantSearchManager(RateOrderSubject rateOrderSubject){
mostRatedRestaurants = new MostRatedRestaurants();
mostRatedRestaurantsByFood= new MostRatedRestaurantsByFood();
rateOrderSubject.addObserver(mostRatedRestaurants);
rateOrderSubject.addObserver(mostRatedRestaurantsByFood);
}
/** n is number of restaurant ids */
public List<String> getRestaurantsByFood(String foodItemId, int n) {
List<String> list = mostRatedRestaurantsByFood.getRestaurants(foodItemId, n);
StringBuffer sb = new StringBuffer();
for(String s:list)sb.append("("+s+" : "+mostRatedRestaurantsByFood.getRating(foodItemId, s)+"), ");
return list;
}
public List<String> getTopRatedRestaurants(int n) {
List<String> list = mostRatedRestaurants.getRestaurants(n);
return list;
}
}
/**
* it keeps restaurants with same rating together,
*/
class MostRatedRestaurants implements RateOrderObserver{
// restaurantId vs rating
private ConcurrentHashMap<String, Rating> ratingsMap = new ConcurrentHashMap<>();
// to allow multiple threads to read and update simultaneously
// it doesn't keep unrated restaurants
// keeps all restaurants with same rating together e.g. all restaurants with rating 4.1 will be in the same set, all restaurants with rating 1.0 will be in same set : ratingDivisons.get(0)
private ArrayList<HashSet<String>> ratingDivisons = new ArrayList<>();
MostRatedRestaurants(){
for(int i=0;i<42;i++)ratingDivisons.add(new HashSet<>());
}
// uses synchronize to write
public void update(Order order) {
String restaurantId = order.getRestaurantId();
synchronized (restaurantId) {
ratingsMap.putIfAbsent(restaurantId, new Rating(0, 0));
Rating rating = ratingsMap.get(restaurantId);
if (rating.getAverageRating() >= 1.0) {
HashSet<String> remove = ratingDivisons.get(getDivisonKey(rating.getAverageRating()));
synchronized (remove) {
remove.remove(order.getRestaurantId());
}
}
rating.add(order.getRating());
HashSet<String> toAdd = ratingDivisons.get(getDivisonKey(rating.getAverageRating()));
synchronized (toAdd) {
toAdd.add(order.getRestaurantId());
}
ratingsMap.put(order.getRestaurantId(), rating);
}
}
/**
* basically it maps rating of a restaurant to
* index in ratingDivisons list,
* rating 1.0 -> index 0, rating 4.1 -> index 31 and so on...
*/
private int getDivisonKey(double rating){
return (int)(rating*10-10);
}
/** n is the number of top restaurants it returns, if we don't */
List<String> getRestaurants(int n){
ArrayList<String> restaurants = new ArrayList<>();
for(int i=ratingDivisons.size()-1;i>=0 && restaurants.size()<n;i--){
HashSet<String> set = ratingDivisons.get(i);
if(set.size()==0) continue;
ArrayList<String> keys = new ArrayList<>();
synchronized (set) {
keys.addAll(set);
}
Collections.sort(keys);
if(restaurants.size()+set.size()<=n){
restaurants.addAll(keys);
continue;
}
for(String restaurantId :keys){
restaurants.add(restaurantId);
if(restaurants.size()>=n) break;
}
}
return restaurants;
}
}
class MostRatedRestaurantsByFood implements RateOrderObserver{
// food ids vs restaurantId and rating
private ConcurrentHashMap<String, SortedSetWithLock> map = new ConcurrentHashMap<>();
double getRating(String foodId, String restaurantId){
return map.get(foodId).get(restaurantId).getAverageRating();
}
public void update(Order order) {
map.putIfAbsent(order.getFoodItemId(), new SortedSetWithLock());
SortedSetWithLock set = map.get(order.getFoodItemId());
synchronized (set) {
Rating newRating = set.get(order.getRestaurantId());
newRating.add(order.getRating());
set.update(order.getRestaurantId(), newRating);
}
}
List<String> getRestaurants(String foodItemId, int n){
SortedSetWithLock set = map.get(foodItemId);
if(set==null) return new ArrayList<>();
return set.getIds(n);
}
}
/**
* - it is a map of all restaurants with their ratings
* - natural order is sort by rating in descending order and then with id lexicographically
*/
class SortedSetWithLock{
private ConcurrentHashMap<String, Rating> ratings = new ConcurrentHashMap<>();
synchronized void update(String id, Rating newValue){
ratings.put(id, newValue);
}
/** returns copy of the value not the actual rating or new Rating(0,0) */
Rating get(String id){
return ratings.getOrDefault(id, new Rating(0,0)).copy();
}
synchronized List<String> getIds(int n){
ArrayList<String> ids = new ArrayList<>(ratings.keySet());
ids.sort((a,b)->{
double ratingA = ratings.get(a).getAverageRating();
double ratingB = ratings.get(b).getAverageRating();
if(ratingA!=ratingB) return ratingA>ratingB?-1:1;
return a.compareTo(b);
});
if(ids.size()>n)return ids.subList(0,n);
return ids;
}
}
class Rating{
private AtomicInteger sum=new AtomicInteger(0), count=new AtomicInteger(0);
Rating(){}
Rating(int sum, int count){
this.sum.set(sum);
this.count.set(count);
}
public String toString(){
return "sum "+sum+", count "+count+", avg "+getAverageRating();
}
// rating is rounded down to one decomal point
double getAverageRating(){
if(count.get()<=0) return 0;
double rating = sum.doubleValue()/count.doubleValue();
rating = (double)((int)((rating+0.05)*10))/10.0;
return rating;
}
void add(int num){
this.sum.addAndGet(num);
this.count.addAndGet(1);
}
Rating copy(){
return new Rating(this.sum.get(), this.count.get());
}
}
class FoodItem{
private String foodItemId, foodItemName;
private double price;
FoodItem(String foodItemId, String foodItemName, double price){
this.foodItemId=foodItemId;
this.foodItemName=foodItemName;
this.price=price;
}
public String getFoodItemId() {
return foodItemId;
}
public String getFoodItemName() {
return foodItemName;
}
public double getPrice() {
return price;
}
}
class Order{
private String orderId, restaurantId, foodItemId;
private int rating;
Order(String orderId, String restaurantId, String foodItemId, int rating){
this.orderId=orderId;
this.restaurantId=restaurantId;
this.foodItemId=foodItemId;
this.rating=rating;
}
public String toString(){
return "("+orderId+", "+foodItemId+", "+restaurantId+", "+rating+")";
}
public void setRating(int rating) {
this.rating = rating;
}
public String getOrderId() {
return orderId;
}
public String getRestaurantId() {
return restaurantId;
}
public String getFoodItemId() {
return foodItemId;
}
public int getRating() {
return rating;
}
}
// uncomment below code in case you are using your local ide like intellij, eclipse etc and
// comment it back again back when you are pasting completed solution in the online CodeZym editor.
// if you don't comment it back, you will get "java.lang.AssertionError: java.lang.LinkageError"
// This will help avoid unwanted compilation errors and get method autocomplete in your local code editor.
/**
interface Q05RestaurantRatingInterface {
void init(Helper05 helper);
void addFoodItem(String foodItemId, double price, String foodItemName);
void addRestaurant(String restaurantId, List<String> foodItemIds, String name, String address);
void orderFood(String orderId, String restaurantId, String foodItemId);
void rateOrder(String orderId, int rating);
List<String> getTopRestaurantsByFood(String foodItemId);
List<String> getTopRatedRestaurants();
}
class Helper05 {
void print(String s){System.out.print(s);}
void println(String s){System.out.println(s);}
}
*/