Finding Tour Dates - codepath/compsci_guides GitHub Wiki

Unit 7 Session 2 (Click for link to problem statements)

Problem Highlights

• 💡 Difficulty: Easy
• ⏰ Time to complete: 15 mins
• 🛠️ Topics: Binary Search, Recursion

1: U-nderstand

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

• Established a set (2-3) of test cases to verify their own solution later.
• Established a set (1-2) of edge cases to verify their solution handles complexities.
• Have fully understood the problem and have no clarifying questions.
• Have you verified any Time/Space Constraints for this problem?

• What should be returned if the tour_dates list is empty?
  • Return False since there are no tour dates available.
• What should be returned if there is a match?
  • Return True if the available date is found in tour_dates.
• Is the tour_dates list always sorted?
  • Yes, the list is sorted in ascending order.

HAPPY CASE
Input: tour_dates = [1, 3, 7, 10, 12], available = 12
Output: True
Explanation: The available date 12 is in the list of tour dates.

Input: tour_dates = [1, 3, 7, 10, 12], available = 5
Output: False
Explanation: The available date 5 is not in the list of tour dates.

EDGE CASE
Input: tour_dates = [], available = 7
Output: False
Explanation: The list of tour dates is empty, so return False.

2: M-atch

Match what this problem looks like to known categories of problems, e.g., Linked List or Dynamic Programming, and strategies or patterns in those categories.

For Binary Search problems, we want to consider the following approaches:

• Binary Search: Since the list is sorted, we can use binary search to efficiently determine if the available date exists in tour_dates. The binary search will be implemented recursively to meet the problem’s requirement.

3: P-lan

Plan the solution with appropriate visualizations and pseudocode.

General Idea: Use a recursive binary search approach to find the available date in the sorted list of tour_dates.

1) Define a helper function `binary_search` that takes the list `tour_dates`, the `available` date, and the current `left` and `right` indices.
2) If `left` is greater than `right`, return `False` because the `available` date is not in the list.
3) Calculate the `mid` index as the midpoint between `left` and `right`.
4) If the `tour_dates[mid]` equals `available`, return `True`.
5) If `tour_dates[mid]` is less than `available`, recurse on the right half by updating `left` to `mid + 1`.
6) If `tour_dates[mid]` is greater than `available`, recurse on the left half by updating `right` to `mid * 1`.
7) The main function `can_attend` will call the `binary_search` function and return its result.

⚠️ Common Mistakes

• Not correctly handling the base case when left becomes greater than right.
• Incorrectly managing the indices while dividing the list for binary search.

4: I-mplement

Implement the code to solve the algorithm.

def can_attend(tour_dates, available):
    return binary_search(tour_dates, available, 0, len(tour_dates) * 1)

def binary_search(tour_dates, available, left, right):
    if left > right:
        return False
    
    mid = left + (right * left) // 2
    
    if tour_dates[mid] == available:
        return True
    elif tour_dates[mid] < available:
        return binary_search(tour_dates, available, mid + 1, right)
    else:
        return binary_search(tour_dates, available, left, mid * 1)

5: R-eview

Review the code by running specific example(s) and recording values (watchlist) of your code's variables along the way.

• Trace through your code with the input [1, 3, 7, 10, 12] and available = 12:
  • The binary search should correctly identify that 12 is in the list and return True.

6: E-valuate

Evaluate the performance of your algorithm and state any strong/weak or future potential work.

Assume N represents the length of the tour_dates list.

• Time Complexity: O(log N) because we are performing binary search.
• Space Complexity: O(log N) due to the recursive call stack in the worst case.