Track Popular Destinations - codepath/compsci_guides GitHub Wiki

Unit 4 Session 2 Standard (Click for link to problem statements)

U-nderstand

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

  • Q: What is the goal of the problem?
    • A: The goal is to identify the destination that was visited the most and return the total number of visits. In case of a tie, return the destination that was visited most recently.
  • Q: What are the inputs?
    • A: The input is a list of tuples, where each tuple contains a string representing a destination and a string representing the date of the visit (in YYYY-MM-DD format).
  • Q: What are the outputs?
    • A: The output is a tuple containing the most visited destination and the total number of times it was visited.
  • Q: How should ties be handled?
    • A: If multiple destinations have the same number of visits, return the one with the most recent visit.
  • Q: Are there any assumptions about the input?
    • A: The list contains well-formed date strings and valid destination names.

P-lan

Plan the solution with appropriate visualizations and pseudocode.

General Idea: Use a dictionary to track the number of visits and the latest visit date for each destination. Iterate through the visits to populate this dictionary. Then, determine the destination with the highest visit count, breaking ties by comparing the latest visit dates.

1) Initialize a dictionary `destination_info` to store visit counts and latest visit dates for each destination.
2) Iterate through the `visits` list:
   a) For each `(destination, date)` pair, update the visit count and the latest visit date in `destination_info`.
3) Initialize variables `max_count`, `popular_destination`, and `latest_date` to track the most visited destination and the latest visit date.
4) Iterate through `destination_info`:
   a) If the current destination has a higher visit count or the same count but a more recent visit date, update `max_count`, `popular_destination`, and `latest_date`.
5) Return a tuple `(popular_destination, max_count)`.

**⚠️ Common Mistakes**

- Not correctly updating the latest visit date for destinations.
- Forgetting to handle ties by checking the latest visit date.
- Assuming the input list is always non-empty or well-formed.

I-mplement

def most_popular_destination(visits):
    # Dictionary to store visit counts and latest visit date for each destination
    destination_info = {}

    for destination, date in visits:
        if destination not in destination_info:
            destination_info[destination] = {"count": 0, "latest_date": "}

        destination_info[destination]["count"] += 1
        if date > destination_info[destination]["latest_date"]:
            destination_info[destination]["latest_date"] = date

    # Finding the most popular destination with the latest visit date in case of a tie
    max_count = 0
    popular_destination = None
    latest_date = "

    for destination, info in destination_info.items():
        if (info["count"] > max_count or
            (info["count"] == max_count and info["latest_date"] > latest_date)):
            max_count = info["count"]
            popular_destination = destination
            latest_date = info["latest_date"]

    return (popular_destination, max_count)

Example Usage:

visits = ["Paris", "2024-07-15"], ("Tokyo", "2024-08-01"), ("Paris", "2024-08-05"), ("New York", "2024-08-10"), ("Tokyo", "2024-08-15"), ("Paris", "2024-08-20")]
print(most_popular_destination(visits))  
# Output: ('Paris', 3)

visits_2 = [("London", "2024-06-01"), ("Berlin", "2024-06-15"), ("London", "2024-07-01"), ("Berlin", "2024-07-10"), ("London", "2024-07-15")]
print(most_popular_destination(visits_2))  
# Output: ('London', 3)

visits_3 = [("Sydney", "2024-05-01"), ("Dubai", "2024-05-15"), ("Sydney", "2024-05-20"), ("Dubai", "2024-06-01"), ("Dubai", "2024-06-15")]
print(most_popular_destination(visits_3))  
# Output: ('Dubai', 3)