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
    dishesMap[tuple(sorted(meal.dishes))].add(meal.cuisine)
  
  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
'''

- prudent_programmer September 19, 2018 | Flag Reply
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

- Sriram Subramanian September 19, 2018 | Flag Reply
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.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);
    }
}

- Prabhakar K September 19, 2018 | Flag Reply
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.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);
}
}

- Prabhakar K September 19, 2018 | Flag Reply
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.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);
}
}

- prabhakar3333 September 19, 2018 | Flag Reply
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){
				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());
	}
}

- Nikhil Attri September 19, 2018 | Flag Reply


Add a Comment
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.

Learn More

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.

Learn More

Resume Review

Most engineers make critical mistakes on their resumes -- we can fix your resume with our custom resume review service. And, we use fellow engineers as our resume reviewers, so you can be sure that we "get" what you're saying.

Learn More

Mock Interviews

Our Mock Interviews will be conducted "in character" just like a real interview, and can focus on whatever topics you want. All our interviewers have worked for Microsoft, Google or Amazon, you know you'll get a true-to-life experience.

Learn More