andy.r.nathan
BAN USER- 0of 0 votes
AnswersYou are designing the client side of a Survey website. Provide the list of classes and methods you will use to break the problem down. Also, provide the API interaction with server.
- andy.r.nathan in United States| Report Duplicate | Flag | PURGE
Linkedin Senior Software Development Engineer Object Oriented Design - 0of 0 votes
AnswersGiven an array of numbers find the duplicates
- andy.r.nathan in United States for Mobile| Report Duplicate | Flag | PURGE
Linkedin Software Developer Algorithm - 1of 1 vote
AnswersSuppose you have a list of Dishes, where each dish is associated with a list of ingredients. Group together dishes with common ingredients.
- andy.r.nathan in United States for Mobile
E.g:
Input:
"Pasta" -> ["Tomato Sauce", "Onions", "Garlic"]
"Chicken Curry" --> ["Chicken", "Curry Sauce"]
"Fried Rice" --> ["Rice", "Onions", "Nuts"]
"Salad" --> ["Spinach", "Nuts"]
"Sandwich" --> ["Cheese", "Bread"]
"Quesadilla" --> ["Chicken", "Cheese"]
Output: ("Pasta", "Fried Rice") ("Fried Rice, "Salad") , ("Chicken Curry", "Quesadilla") ("Sandwich", "Quesadilla")
Follow up: What is the time and space complexity?| Report Duplicate | Flag | PURGE
Linkedin Software Developer Algorithm
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)
Looks like we can get O(N*logN) by starting from last element, finding the place of new element in a height-balanced BST.
- andy.r.nathan September 19, 2016
- andy.r.nathan September 22, 2016