Finding Common Tourist Attractions with Least Travel Time - codepath/compsci_guides GitHub Wiki

U-nderstand

Understand what the interviewer is asking for by using test cases and questions about the problem.

• Q
  • What is the desired outcome?
    • To find the common attractions in two lists with the least total travel time.
  • What input is provided?
    • Two lists tourist_list1 and tourist_list2.

P-lan

Plan the solution with appropriate visualizations and pseudocode.

General Idea: Use a dictionary to map attractions in the first list to their indices, then find the common attractions with the minimum total travel time.

1) Create a dictionary `index_map` to store the indices of attractions in `tourist_list1`.
2) Iterate through `tourist_list2`:
   - If an attraction is in `index_map`, calculate the total travel time.
   - Track the minimum travel time and update the result list accordingly.
3) Return the result list containing common attractions with the least total travel time.

⚠️ Common Mistakes

• Not correctly handling cases with multiple common attractions having the same travel time.

I-mplement

def find_attraction(tourist_list1, tourist_list2):
    # Step 1: Populate the dictionary with the indices of attractions in tourist_list1
    index_map = {}
    for i, attraction in enumerate(tourist_list1):
        index_map[attraction] = i
    
    # Step 2: Iterate through tourist_list2 and find the common attractions with the least total travel time
    min_sum = float('inf')
    result = []
    
    for j, attraction in enumerate(tourist_list2):
        if attraction in index_map:
            i = index_map[attraction]
            total_travel_time = i + j
            if total_travel_time < min_sum:
                min_sum = total_travel_time
                result = [attraction]
            elif total_travel_time == min_sum:
                result.append(attraction)
    
    return result