Yelp Interview Question
Software EngineersCountry: United States
Interview Type: Phone Interview
My Approach
1. Sort all the dishes in the respective cuisine
2. Use Trie and Map<String, Trie> to start storing the dishes one by one from each cuisine
3. When you reach the end, check for the group and assign to the group, if not exists create one and assign.
4. At last you would grouped the cuisines
package com.company;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.HashSet;
import java.util.List;
public class Meals {
List<String> dishes;
String cusine;
public Meals()
{
dishes = new ArrayList<>();
}
public List<String> getDishes() {
return dishes;
}
public Meals setCusine(String cusine) {
this.cusine = cusine;
return this;
}
public String getCusine() {
return cusine;
}
public Meals setDishes(List<String> dishes) {
this.dishes = dishes;
return this;
}
public static void main(String[] args){
List<Meals> mealsArrayList= new ArrayList<>();
mealsArrayList.add(new Meals().setCusine("American").setDishes(Arrays.asList("A","B","C","D")));
mealsArrayList.add(new Meals().setCusine("Korean").setDishes(Arrays.asList("E","F","C","D")));
mealsArrayList.add(new Meals().setCusine("Contine").setDishes(Arrays.asList("A","C","C","D")));
mealsArrayList.add(new Meals().setCusine("Choo").setDishes(Arrays.asList("A","B","D","D")));
mealsArrayList.stream()
.filter(meals -> (new HashSet<String>(meals.getDishes())).size() == meals.getDishes().size())
.map(meals-> meals.getCusine())
.forEach(System.out::println);
}
}
package com.company;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.HashSet;
import java.util.List;
public class Meals {
List<String> dishes;
String cusine;
public Meals()
{
dishes = new ArrayList<>();
}
public List<String> getDishes() {
return dishes;
}
public Meals setCusine(String cusine) {
this.cusine = cusine;
return this;
}
public String getCusine() {
return cusine;
}
public Meals setDishes(List<String> dishes) {
this.dishes = dishes;
return this;
}
public static void main(String[] args){
List<Meals> mealsArrayList= new ArrayList<>();
mealsArrayList.add(new Meals().setCusine("American").setDishes(Arrays.asList("A","B","C","D")));
mealsArrayList.add(new Meals().setCusine("Korean").setDishes(Arrays.asList("E","F","C","D")));
mealsArrayList.add(new Meals().setCusine("Contine").setDishes(Arrays.asList("A","C","C","D")));
mealsArrayList.add(new Meals().setCusine("Choo").setDishes(Arrays.asList("A","B","D","D")));
mealsArrayList.stream()
.filter(meals -> (new HashSet<String>(meals.getDishes())).size() == meals.getDishes().size())
.map(meals-> meals.getCusine())
.forEach(System.out::println);
}
}
package com.company;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.HashSet;
import java.util.List;
public class Meals {
List<String> dishes;
String cusine;
public Meals()
{
dishes = new ArrayList<>();
}
public List<String> getDishes() {
return dishes;
}
public Meals setCusine(String cusine) {
this.cusine = cusine;
return this;
}
public String getCusine() {
return cusine;
}
public Meals setDishes(List<String> dishes) {
this.dishes = dishes;
return this;
}
public static void main(String[] args){
List<Meals> mealsArrayList= new ArrayList<>();
mealsArrayList.add(new Meals().setCusine("American").setDishes(Arrays.asList("A","B","C","D")));
mealsArrayList.add(new Meals().setCusine("Korean").setDishes(Arrays.asList("E","F","C","D")));
mealsArrayList.add(new Meals().setCusine("Contine").setDishes(Arrays.asList("A","C","C","D")));
mealsArrayList.add(new Meals().setCusine("Choo").setDishes(Arrays.asList("A","B","D","D")));
mealsArrayList.stream()
.filter(meals -> (new HashSet<String>(meals.getDishes())).size() == meals.getDishes().size())
.map(meals-> meals.getCusine())
.forEach(System.out::println);
}
}
import java.util.ArrayList;
import java.util.HashMap;
import java.util.Scanner;
class Meals{
String dishes;
ArrayList<String> ingredient = new ArrayList<>();
Meals(String dish, ArrayList<String> ingredient){
this.dishes = dish;
this.ingredient= ingredient;
}
}
public class UniqueDishes {
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
Meals[] meals = new Meals[5];
for(int i=0;i<5;i++){
String dish = sc.next();
String ingredient = sc.next();
String [] eachIngredient= ingredient.split(",");
ArrayList<String> arrayList = new ArrayList<>();
for(String s : eachIngredient){
arrayList.add(s);
}
meals[i]=new Meals(dish, arrayList);
}
HashMap<ArrayList<String>,String> myHashMap = new HashMap<>();
for(int i=0;i<5;i++){
myHashMap.put(meals[i].ingredient, meals[i].dishes);
}
System.out.println(myHashMap.size());
}
}
This problem is very similar to the "Grouping Anagrams" problem. The idea is to use a hash table using the dishes as the key and the cuisines as values. Ex:-
However, the ingredients or dishes can be in any order, which is why you have to sort them before using them as the key.
I present a solution in Python below. I use a Python tuple to represent the key and the cuisines as values.
Time complexity would be O (n log k) where k is the max number of ingredients in the dish.
Space complexity would be O(n) since we are using a hash table to store all the meals.
Code
Test Code
- prudent_programmer September 19, 2018