Check if Itinerary is Valid - 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 determine if the given itinerary is a valid permutation of the template base[n].
  • What input is provided?
    • An itinerary list itinerary.

P-lan

Plan the solution with appropriate visualizations and pseudocode.

General Idea: Count the occurrences of each city in the itinerary, then check if it matches the structure of base[n].

1) Find the maximum value `n` in the itinerary.
2) Check if the length of `itinerary` is `n + 1`.
3) Count the occurrences of each city in the itinerary.
4) Verify that cities `1` to `n-1` each appear exactly once, and city `n` appears twice.
5) Return `True` if the itinerary is valid, otherwise return `False`.

⚠️ Common Mistakes

• Not correctly handling cases where the length of the itinerary does not match n + 1.

I-mplement

def is_valid_itinerary(itinerary):
    n = max(itinerary)

    # The correct base itinerary should have exactly n + 1 elements
    if len(itinerary) != n + 1:
        return False

    # Count the occurrences of each city in the itinerary
    counts = {}
    for city in itinerary:
        if city in counts:
            counts[city] += 1
        else:
            counts[city] = 1

    # Check the counts against the required base itinerary structure
    for i in range(1, n):
        if counts.get(i, 0) != 1:
            return False

    return counts.get(n, 0) == 2