CareerCup

Can't we form a graph out of the information provided, like

American		Italian
Burger, 			1				0
French fries, 		1				0	
Potato Chips		1				1
Pizza			0				1				
,Bread Sticks		0				1

Now using the above adjacent matrix cant we solve the problem?

Maintain a Map, where key is categoryNames and value is list of Restaurant types.
Map<String,List<String>> mp = new HashMap<>(String,List<String>);
mp.put(Burger,American);
mp.put("French fries",American);
mp.put("Potato Chips", American->Italian );
etc.

import java.util.*;
public class Test_Me
{
  public static void main(String[] args)
  {
    HashMap<String, String> hm = new HashMap<String, String>();
      hm.put("American", "[Burger, French fries, Potato Chips]");
      hm.put("Italian", "[Pizza, Bread Sticks, Potato Chips]");

   String x = (new Scanner(System.in)).nextLine();
   Set set = hm.entrySet();
   Iterator i = set.iterator();
   int count = 0;
   while (i.hasNext())
   {
     Map.Entry me = (Map.Entry) i.next();
     String s = (String) me.getValue(); 
     if (s.toLowerCase().contains(x.toLowerCase()))
     {
      count++;
     }
    }
   System.out.println(count);
   }
}

we can use k-d Tree to make k dimension on the basis of food menu and take the restaurant when single search or multiple search is required.

restaurants = {
    "American": ["Burger", "French fries", "Potato Chips"],
    "Italian": ["Pizza", "Bread Sticks", "Potato Chips"],
}

search_term = "Pizza"

for restaurant, categories in restaurants.items():
    if search_term in categories:
        print restaurant

import java.util.HashMap;
import java.util.Iterator;
import java.util.List;
import java.util.Map;
import java.util.Scanner;
import java.util.Set;


public class SearchMap {

/**
* @param args
*/
public static void main(String[] args)
{
int count=1;
HashMap<String, String> hm = new HashMap<String, String>();
hm.put("American", "Burger,French fries, Potato Chips");
hm.put("Italian", "Pizza, Bread Sticks, Potato Chips");
String str = hm.get("American");
String str1 = hm.get("Italian");
String temp1[]=str.split(",");
String temp2[]=str1.split(",");

for (String string : temp1) {
for (String string1 : temp2) {
if(string.equals(string1))
{
count++;
System.out.print(count);
System.out.print(hm.keySet());


break;
}
}
}
}



}



import java.util.HashMap;
import java.util.Iterator;
import java.util.List;
import java.util.Map;
import java.util.Scanner;
import java.util.Set;


public class SearchMap {

/**
* @param args
*/
public static void main(String[] args)
{
int count=1;
HashMap<String, String> hm = new HashMap<String, String>();
hm.put("American", "Burger,French fries, Potato Chips");
hm.put("Italian", "Pizza, Bread Sticks, Potato Chips");
String str = hm.get("American");
String str1 = hm.get("Italian");
String temp1[]=str.split(",");
String temp2[]=str1.split(",");

for (String string : temp1) {
for (String string1 : temp2) {
if(string.equals(string1))
{
count++;
System.out.print(count);
System.out.print(hm.keySet());


break;
}
}
}
}



}

wait a second .. what all crazy answers did people give ... people think just writing a java program to solve it makes them java experts.
Also the python solution wasn't elegant .. its not the number of lines of code that matters.

if it was just to go through each and look for values its probably going to be rejected.

Dictionary<string, List<string>> collection = new Dictionary<string, List<string>>();
            List<string> items = new List<string>{"Burger", "French Fries", "Potato Chips"};
            collection.Add("American", items);
            items = new List<string>{ "Pizza", "Bread Sticks", "Potato Chips"};
            collection.Add("Italian", items);
            int count = 0;
            collection.AsParallel().ForAll(i =>
                {
                    if (i.Value.Contains("Potato Chips"))
                        count++;
                });
            Console.WriteLine("Potato Chips is found in {0} categories", count);

I would use a HashMap<String,Set<String>>.
The key would be the name of the category like Potato chips and the value which is a set will contain the restaurant types. The reason for using set here is that it will not allow duplicate values.

As already posted by many colleagues there are many answers but it depends on how often this lookup will be used and how many items it would contain. I think its better to create a map of items with the category as the key and restaurant type as the value. We will afcourse need a multi map because we can have multiple categories for a restaurant type. But this will provide a fast look up but may take more time to fill and space.

std::multimap<std::string, std::string> itemToCusine;
	itemToCusine.insert( std::make_pair<std::string, std::string>("Burger", "American") );
	itemToCusine.insert( std::make_pair<std::string, std::string>("Potato Chips", "American") );
	itemToCusine.insert( std::make_pair<std::string, std::string>("Potato Chips", "Italian") );

....
std::string itemToFind = "Potato Chips";
std::vector<std::string> result;

std::multimap<std::string, std::string> ::iterator findItr = itemToCusine.find( itemToFind );
while( findItr != itemToCusine.end() && findItr->first == itemToFind )
{
	if( std::find( result.begin() , result.end() , findItr->first ) != result.end() )
	{
		continue;
	}
	else
		result.push_back( findItr->second );

		findItr++;
}

Looks like options are:

Assuming N = number of restaurant types and V = number of "Category names" per restaurant type.

1. O(N*V) cost to create a HashTable/Dictionary with key = category name and value = list of "Restaurant types". After this we O(1) look up for GetRestaurantType(CategoryName).

2. O(1) cost to use Dictionary as-is. But O(N*V) lookup for GetRestaurantType(CategoryName).

3. O(N) cost to create Dictionary with Key = Restaurant-Type and Value = Set from list of Category names. O(N) lookup for GetRestaurantType(CategoryName).

Optimizations with 2, only the first lookup will be expensive, once you do a lookup, add the result to a hash table with key - category name and value = list of "restaurant types" with category name, so that subsequent lookups for same category name are O(1)

public static void populateResturantMenus(String findItemOnMenus)
    {
        int count =0;

        for(String itr:restMenuList.keySet()){
            if(restMenuList.get(itr).contains(findItemOnMenus)){
                count++;
            }
        }

        System.out.println(count);
        }

        
        }

    }

public static void populateResturantMenus(String findItemOnMenus)
    {
        int count =0;

        for(String itr:restMenuList.keySet()){
            if(restMenuList.get(itr).contains(findItemOnMenus)){
                count++;
            }
        }

        System.out.println(count);
        }

        
        }

    }

public static void populateResturantMenus(String findItemOnMenus)
{
int count =0;

for(String itr:restMenuList.keySet()){
if(restMenuList.get(itr).contains(findItemOnMenus)){
count++;
}
}

System.out.println(count);
}


}

}

function categoriesEncodeBin(categories) {
  categories = categories.reduce((x, y) => { x[y] = true; return x }, {});
  const binstr = ['burger', 'french fries', 'potato chips', 'pizza', 'bread sticks']
    .reduce((c, m) => { 
      c += categories[m] !== undefined ? 1 : 0;
      return c;
    }, '');
  return parseInt(binstr, 2);
}

const restaurants = {
  american: ['burger', 'french fries', 'potato chips'],
  italian: ['pizza', 'bread sticks', 'potato chips'],
  foo: ['pizza', 'bread sticks', 'potato chips']
};

const query = categoriesEncodeBin(['potato chips']);
let cnt = 0;
if (query > 0)
  for (let type in restaurants) {
    const categoriesEncoded = categoriesEncodeBin(restaurants[type]); // can pre-encode it
    if ((query & categoriesEncoded) === query) cnt++;
  }
console.log(cnt);

function categoriesEncodeBin(categories) {
  categories = categories.reduce((x, y) => { x[y] = true; return x }, {});
  const binstr = ['burger', 'french fries', 'potato chips', 'pizza', 'bread sticks']
    .reduce((c, m) => { 
      c += categories[m] !== undefined ? 1 : 0;
      return c;
    }, '');
  return parseInt(binstr, 2);
}

const restaurants = {
  american: ['burger', 'french fries', 'potato chips'],
  italian: ['pizza', 'bread sticks', 'potato chips'],
  foo: ['pizza', 'bread sticks', 'potato chips']
};

const query = categoriesEncodeBin(['potato chips']);
let cnt = 0;
if (query > 0)
  for (let type in restaurants) {
    const categoriesEncoded = categoriesEncodeBin(restaurants[type]); // can pre-encode it
    if ((query & categoriesEncoded) === query) cnt++;
  }
console.log(cnt);

function categoriesEncodeBin(categories) {
  categories = categories.reduce((x, y) => { x[y] = true; return x }, {});
  const binstr = ['burger', 'french fries', 'potato chips', 'pizza', 'bread sticks']
    .reduce((c, m) => { 
      c += categories[m] !== undefined ? 1 : 0;
      return c;
    }, '');
  return parseInt(binstr, 2);
}

const restaurants = {
  american: ['burger', 'french fries', 'potato chips'],
  italian: ['pizza', 'bread sticks', 'potato chips'],
  foo: ['pizza', 'bread sticks', 'potato chips']
};

const query = categoriesEncodeBin(['potato chips']);
let cnt = 0;
if (query > 0)
  for (let type in restaurants) {
    const categoriesEncoded = categoriesEncodeBin(restaurants[type]); // can pre-encode it
    if ((query & categoriesEncoded) === query) cnt++;
  }
console.log(cnt);

# {
# //"Restaurant Types"."[categoryNames]"
# "American" : "[Burger, French fries, Potato Chips]",
# "Italian":"[Pizza,Bread Sticks, Potato Chips]"
# }

food ={
"American" : ["Burger", "French fries", "Potato Chips"],
"Italian"  : ["Pizza","Bread Sticks", "Potato Chips"]
}

print(food)

d = {}
for key,vals in food.items():

  for val in vals:
    if val in d:
      d[val].add(key)
    else:
      d[val] = set([key])

print(len(d["Burger"]))