## Yelp Interview Question for Software Engineers

Country: United States
Interview Type: Phone Interview

Comment hidden because of low score. Click to expand.
1
of 1 vote

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:-

"lettuce,cheese,pepper,tomato": ["Mexican", "French"]
"lettuce,cheese,olives,tomato": ["American", "Continental"]

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

class Meal:
def __init__(self, cuisine, dishes):
self.cuisine = cuisine
self.dishes = dishes

def findUniqueIngredients(meals):
# If meals is empty, return 0
if not meals:
return 0

dishesMap = collections.defaultdict(set)

for meal in meals:
# Sort it before inserting this as a key

combinedCuisines = list(dishesMap.values())
return (len(combinedCuisines), combinedCuisines)

Test Code

meals = [
Meal("American", ["lettuce", "cheese", "olives", "tomato"] ),
Meal("Mexican", ["lettuce", "cheese", "pepper", "tomato"] ),
Meal("French", ["lettuce", "cheese", "pepper", "tomato"] ),
Meal("Continental", ["lettuce", "cheese", "olives", "tomato"] )
]
uniqueDishesCount, uniqueDishesCuisines = findUniqueIngredients(meals)
print('The unique dishes cuisines are:', uniqueDishesCuisines)
print('Total unique dishes count:', uniqueDishesCount)

'''
OUTPUT:
The unique dishes cuisines are: [{'American', 'Continental'}, {'French', 'Mexican'}]
Total unique dishes count: 2
'''

Comment hidden because of low score. Click to expand.
0
of 0 vote

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

Comment hidden because of low score. Click to expand.
0
of 0 vote

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.stream()
.filter(meals -> (new HashSet<String>(meals.getDishes())).size() == meals.getDishes().size())
.map(meals-> meals.getCusine())
.forEach(System.out::println);
}
}

Comment hidden because of low score. Click to expand.
0
of 0 vote

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.stream()
.filter(meals -> (new HashSet<String>(meals.getDishes())).size() == meals.getDishes().size())
.map(meals-> meals.getCusine())
.forEach(System.out::println);
}
}

Comment hidden because of low score. Click to expand.
0
of 0 vote

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.stream()
.filter(meals -> (new HashSet<String>(meals.getDishes())).size() == meals.getDishes().size())
.map(meals-> meals.getCusine())
.forEach(System.out::println);
}
}

Comment hidden because of low score. Click to expand.
0
of 0 vote

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){
}
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());
}
}

Name:

Writing Code? Surround your code with {{{ and }}} to preserve whitespace.

### Books

is a comprehensive book on getting a job at a top tech company, while focuses on dev interviews and does this for PMs.

### Videos

CareerCup's interview videos give you a real-life look at technical interviews. In these unscripted videos, watch how other candidates handle tough questions and how the interviewer thinks about their performance.