Groupon Interview Question
Senior Software Development EngineersCountry: United States
Interview Type: Phone Interview
You could use any algorithm like Levenshtein Distance to find the edit distance between the strings of coffee name customer is drinking and coffee flavors you have and populate top n coffee flavors order by edit distance ascending.
Sorry if this wasn't clear, but when I said 'closest flavor matches', I did not mean in terms of the edit distances of the coffee names. You have a mapping for each coffee flavor of what other flavors taste similar to it. Although the question was open ended, one way of interpreting it would be that you are perhaps given a mapping of how different each other flavor is from a particular flavor given as an integer in a range, say 1-10, 1 being closest and 10 being farthest. You just need to store this information in an appropriate data structure and answer a customer question by accessing this data that you are given.
Here is my implementation....I have made different array for each integer. (1-10, 1 being the most similar flavour, 10 being the least similar flavour). So, there shall be only 10 array lists no matter how many flavours of coffee that gets added. If there are thousand flavours, only 10 elements would be in each array at an average...So, just for implementation sake, i have created two arraylists for 1st and 2nd rank. The coffee falvours in 1st rank are those that are most similar, and similarly for subsequent flavours. When the query comes in for a coffee we shall go through 1st rank and try to find if there is coffee that is similar to it. If it is found, then the program ends or it goes onto ranks below. Here is my code...
public List<String> findSimilarCoffee(String query){
ArrayList<String> oneRanking = new ArrayList<String>();
ArrayList<String> twoRanking = new ArrayList<String>();
Map<Integer,ArrayList<String>> mapOfCoffee = new HashMap<Integer,ArrayList<String>>();
oneRanking.add("Capp");
oneRanking.add("Latte");
oneRanking.add("BlackCoffee");
mapOfCoffee.put(1,oneRanking);
twoRanking.add("Oranje Juice");
twoRanking.add("Latte");
twoRanking.add("BlackCoffee");
mapOfCoffee.put(2,twoRanking);
String coffee_query = new String("BlackCoffee"); //Assume the customer asks for black coffee
List<String> listOfSimilarCofee = new ArrayList<String>();
boolean similarCoffeeFound = false;
for(Integer i :mapOfCoffee.keySet()){
if(similarCoffeeFound==false){
if(null!=mapOfCoffee.get(i) && mapOfCoffee.get(i).contains(coffee_query)){
for(String coffee : mapOfCoffee.get(i)){
listOfSimilarCofee.add(coffee);
similarCoffeeFound = true;
return listOfSimilarCofee;
}
}
}
}
return listOfSimilarCofee;
}
public List<String> findSimilarCoffee(String query){
ArrayList<String> oneRanking = new ArrayList<String>();
ArrayList<String> twoRanking = new ArrayList<String>();
Map<Integer,ArrayList<String>> mapOfCoffee = new HashMap<Integer,ArrayList<String>>();
oneRanking.add("Capp");
oneRanking.add("Latte");
oneRanking.add("BlackCoffee");
mapOfCoffee.put(1,oneRanking);
twoRanking.add("Oranje Juice");
twoRanking.add("Latte");
twoRanking.add("BlackCoffee");
mapOfCoffee.put(2,twoRanking);
String coffee_query = new String("BlackCoffee"); //Assume the customer asks for black coffee
List<String> listOfSimilarCofee = new ArrayList<String>();
boolean similarCoffeeFound = false;
for(Integer i :mapOfCoffee.keySet()){
if(similarCoffeeFound==false){
if(null!=mapOfCoffee.get(i) && mapOfCoffee.get(i).contains(coffee_query)){
for(String coffee : mapOfCoffee.get(i)){
listOfSimilarCofee.add(coffee);
similarCoffeeFound = true;
return listOfSimilarCofee;
}
}
}
}
return listOfSimilarCofee;
Maintain a graph.
- Anonymous September 26, 2015Each node representing a Coffee flavour.
The edges to it will represent the variation in flavour.
The other end of the edge points to the resultant flavour.
You can traverse through each available flavour first to create this graph.
Then when customer asks, just tell him the adjacent nodes of his coffee.
Complexity O(V+E) for searching the node in BFS.