algoadvance

You have two lists, list1 and list2, both of which contain strings representing restaurant names. Your task is to find the common interest with the least index sum. A common interest in these two lists means that both lists contain the same restaurant. The index sum of a common interest is the sum of the indices of the common interest in list1 and list2. If there is a tie, return all restaurants with the lowest index sum in a list. If there are no common interests, return an empty list.

Clarifying Questions

1. Input Constraints:
   • What is the length range of list1 and list2?
   • Are the restaurant names unique within each list?
   • Is the order of the output list important when there are multiple common interests with the same minimum index sum?
2. Edge Cases:
   • How should we handle lists with no common restaurants?
   • How to handle very large lists with extremely large lengths?

Assumptions

• We assume that the lists are relatively small to moderate in size.
• We assume each list contains unique strings, based on the problem description.

Strategy

1. Create Dictionaries:
   • Use a dictionary to store the index of each restaurant in list1.
   • Iterate through list2 and for each restaurant, calculate the sum of indices if it is found in list1.
2. Track Minimum Index Sum:
   • Track the minimum index sum found.
   • Use another dictionary to store all restaurants with the same minimum index sum.
3. Return Result:
   • Retrieve restaurants that have the minimum index sum and return them as a list.

Time Complexity

• Creating the index dictionary for list1: O(n)
• Iterating through list2 and checking against the dictionary: O(m)
• Overall time complexity: O(n + m)

Code

def findRestaurant(list1, list2):
    index_map_list1 = {restaurant: index for index, restaurant in enumerate(list1)}
    min_sum = float('inf')
    result = []
    
    for index2, restaurant in enumerate(list2):
        if restaurant in index_map_list1:
            index1 = index_map_list1[restaurant]
            current_sum = index1 + index2
            
            if current_sum < min_sum:
                min_sum = current_sum
                result = [restaurant]
            elif current_sum == min_sum:
                result.append(restaurant)
    
    return result

# Example Usage
list1 = ["Shogun", "Tapioca Express", "Burger King", "KFC"]
list2 = ["Piatti", "The Grill at Torrey Pines", "Hungry Hunter Steakhouse", "Shogun"]

print(findRestaurant(list1, list2))  # Output: ["Shogun"]

Explanation

1. Index Mapping: We start by creating a dictionary that maps each restaurant in list1 to its index.
2. Iteration and Comparison:
   • For each restaurant in list2, we check if it exists in list1 using the dictionary.
   • If it does, we calculate the sum of the indices.
   • We then compare this sum to our current minimum index sum and update our results accordingly.
3. Return Result: Finally, we return the list of common restaurants with the smallest index sum.

This solution efficiently finds the common interests in the two lists and solves the problem within the expected time complexity limits.

Try our interview co-pilot at AlgoAdvance.com

• Got blindsided by a question you didn’t expect?

• Spend too much time studying?

• Or simply don’t have the time to go over all 3000 questions?