## Linkedin Interview Question for Software Developers

Team: Mobile
Country: United States
Interview Type: Phone Interview

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

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

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

``````dishes = {"Pasta":["Tomato Sauce", "Onions", "Garlic"],
"Chicken Curry":["Chicken", "Curry Sauce"],
"Fried Rice":["Rice", "Onions", "Nuts"],

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?

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

"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.

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

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

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

``````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"],
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 sandwich =new Dish("Sandwich",new String[]{"Cheese", "Bread"});
ArrayList arr = new ArrayList();
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;
}

}``````

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

Why negative vote for answer from arkhimoff?

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

Why negative vote for answer from arkhimoff?

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

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

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

can there be more than two dishes with common ingredients ? The question sounds incomplete.

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

``````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;
}``````

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

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

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.