CareerCup

It seems the algorithm is connected components from graph theory...

dishes = {"Pasta":["Tomato Sauce", "Onions", "Garlic"],
"Chicken Curry":["Chicken", "Curry Sauce"],
"Fried Rice":["Rice", "Onions", "Nuts"],
"Salad":["Spinach", "Nuts"],
"Sandwich":["Cheese", "Bread"],
"Quesadilla":["Chicken", "Cheese"]}

def groupByIngredients(dishes):
    by_ingredients = {}
    for dish in dishes:
        for ingredient in dishes[dish]:
            if ingredient in ingredients:
                ingredients[ingredient].append(dish) 
            else:
                ingredients[ingredient] = [dish]
                
    return by_ingredients

Space complexity is linear; time complexity is O(n*k) -- I think?

"group together dishes with common ingredients" is ambiguous and the sample doesn't really help. Following interpretations are possible:
1) For every ingredient list common dishes, e.g. two dishes that share two ingredients get listed twice
2) For every ingredient list common dished, but avoid listing a pair twice
3) For the latter one, we could as well prefer to list the dishes which share most ingredients first

1) is easy: create a hashtable with ingredient as key and dishes as list. then out put this lists if they are bigger than 1
2) I would approach as 1) but then I could keep a matrix which stores the already output pairs (for an ingredient that is used in k dishes this is (k-1)! pairs) making the whole thing exponential in time and quadratic in space (matrix), which is clearly not acceptable

I'm interested in approaches...I can't see it.

Traverse the dishes list and create a map of ingredients with ingredients as key and list of dishes as value.

import java.util.ArrayList;
import java.util.HashMap;
import java.util.HashSet;
import java.util.Iterator;
import java.util.Set;

public class DishTest {
public static void main(String ard[]){
	
	/*"Pasta":["Tomato Sauce", "Onions", "Garlic"],
	"Chicken Curry":["Chicken", "Curry Sauce"],
	"Fried Rice":["Rice", "Onions", "Nuts"],
	"Salad":["Spinach", "Nuts"],
	"Sandwich":["Cheese", "Bread"],
	"Quesadilla":["Chicken", "Cheese"]}*/
	Dish pasta =new Dish("Pasta",new String[]{"Tomato Sauce","Onions","Garlic"});
	Dish chicken =new Dish("Chicken Curry",new String[]{"Chicken", "Curry Sauce"});
	Dish friedRice =new Dish("Fried Rice",new String[]{"Rice", "Onions", "Nuts"});
	Dish salad =new Dish("Salad",new String[]{"Spinach", "Nuts"});
	Dish sandwich =new Dish("Sandwich",new String[]{"Cheese", "Bread"});
	Dish quesadilla =new Dish("Quesadilla",new String[]{"Chicken", "Cheese"});
	ArrayList arr = new ArrayList();
	arr.add(pasta);
	arr.add(chicken);
	arr.add(friedRice);
	arr.add(salad);
	arr.add(sandwich);
	arr.add(quesadilla);
	HashMap<String,HashMap<String,String>> hs = new HashMap<String,HashMap<String,String>>();
	Dish row;
	for(int i =0;i<arr.size();i++){
		row=(Dish)arr.get(i);
		setSpices(row,hs);
		row=null;
	}
	Set hSet=hs.keySet();
	Iterator it=hSet.iterator();
	while(it.hasNext()){
		String key=(String)it.next();
		HashMap hsMap=hs.get(key);
		if(isMulitpleFood(hsMap))
			System.out.println(hsMap.keySet());
	}

}



private static boolean isMulitpleFood(HashMap hsMap) {
	Set hSet=hsMap.keySet();
	if(hSet.size()>1)
		return true;

	return false;
}



private static void setSpices(Dish row, HashMap<String,HashMap<String,String>> hs) {
HashMap dish= null;

for(int i=0;i<row.getSpices().length;i++){
		if(!hs.containsKey(row.getSpices()[i].toString())){
			dish= new HashMap();
			dish.put(row.getName(), row.getName());
			hs.put(row.getSpices()[i].toString(), dish);
		}else{
			HashMap dishInc=hs.get(row.getSpices()[i].toString());
			if(!dishInc.containsKey(row.getName())){
				dishInc.put(row.getName(), row.getName());
				hs.put(row.getSpices()[i].toString(), dishInc);

			}
		}
	}
}
}

 class Dish {
	private String name;
	private String[] spices;
	
	public Dish(String dishName,String sp[]){
		this.name=dishName;
		this.spices=sp;
	}
	public String getName() {
		return name;
	}
	public void setName(String name) {
		this.name = name;
	}
	public String[] getSpices() {
		return spices;
	}
	public void setSpices(String[] spices) {
		this.spices = spices;
	}

}

Why negative vote for answer from arkhimoff?

Why negative vote for answer from arkhimoff?

pasta = ['Tomato','Onion','Garlic']
friedrice = ['White Rice','Onion','Ginger']
noodles = ['Soy sauce','Noodles','apple']

dictionary = {}

dictionary['pasta'] = pasta
dictionary['friedrice'] = friedrice
dictionary['noodles'] = noodles

dictionary2 = dictionary 

print dictionary
print dictionary2

for k,v in dictionary.iteritems():
    for k1,v1 in dictionary2.iteritems():
        if k != k1 and len(set(v) & set(v1)) > 0:
            print k,k1

can there be more than two dishes with common ingredients ? The question sounds incomplete.
Was this question asked for an internship or full-time?

struct dish
{
	string Name;
	std::vector<string> Ingredients;
};

std::vector<string> FindMatching(std::vector<dish> dishes)
{
	std::vector<std::vector<string>> matches;
	
	for (int i=0; i < dishes.Size(); i++)
	{
		std::vector<string> group;
		std::unordered_map<string, int> hash;
		
		group.push_back(dishes[i].Name);
		
		for (int m=0; m < dishes[i].Ingredients.Size(); m++)
		{
			hash[dishes[i].Ingredients[m]] = 1;
		}
		
		for (int n=0; n < dishes.Size() -1; n++)
		{
			int dish_index = (i + 1 + n) % dishes.Size();
			for (int x=0; x < dishes[dish_index].Ingredients.Size(); x++)
			{
				if (hash.find(dishes[dish_index].Ingredients[x]) != hash.end())
				{
					group.push_back(dishes[dish_index].Name);
					break;
				}
			}
		}
		
		if (group.Size() > 1)
		{
			matches.push_back(group);
		}
	}	
	
	return matches;
}

Can be solved by building an undirected graph (where vertices are dishes and edges are ingredients), and finding all maximal cliques.