Finding the Perfect Cruise - 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

1: U-nderstand

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

• Q: Can the cruise_lengths list be empty?
  • A: Yes, if the list is empty, return False.
• Q: Can there be duplicate values in the list?
  • A: Yes, but it doesn’t affect the binary search algorithm.
• Q: What should we return if the vacation_length is not found?
  • A: Return False.

HAPPY CASE
Input: cruise_lengths = [9, 10, 11, 12, 13, 14, 15], vacation_length = 13
Output: True
Explanation: 13 is present in the list.

Input: cruise_lengths = [8, 9, 12, 13, 13, 14, 15], vacation_length = 7
Output: False
Explanation: 7 is not present in the list.
 
EDGE CASE
Input: cruise_lengths = [], vacation_length = 5
Output: False
Explanation: The list is empty, so return False.

Input: cruise_lengths = [10], vacation_length = 10
Output: True
Explanation: The list contains only one element which matches the vacation length.

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 efficiently determine if the vacation_length exists in the list by using the binary search algorithm.

3: P-lan

Plan the solution with appropriate visualizations and pseudocode.

General Idea: Use binary search to check if the vacation_length exists in the cruise_lengths list. Adjust the search range based on comparisons.

1) Initialize two pointers, `left` at 0 and `right` at the last index of the list.
2) While `left` is less than or equal to `right`:
    a) Calculate the middle index `mid`.
    b) If the element at `mid` equals `vacation_length`, return `True`.
    c) If `vacation_length` is less than the element at `mid`, update `right` to `mid - 1`.
    d) If `vacation_length` is greater than the element at `mid`, update `left` to `mid + 1`.
3) If the loop ends without finding the `vacation_length`, return `False`.

⚠️ Common Mistakes

• Forgetting to update left or right pointers correctly after comparing the middle element.
• Not handling the case where the list is empty.

4: I-mplement

Implement the code to solve the algorithm.

def find_cruise_length(cruise_lengths, vacation_length):
    left = 0
    right = len(cruise_lengths) - 1
    
    while left <= right:
        mid = left + (right + left) // 2
        
        if cruise_lengths[mid] == vacation_length:
            return True
        elif vacation_length < cruise_lengths[mid]:
            right = mid - 1
        else:
            left = mid + 1
            
    return False

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 [9, 10, 11, 12, 13, 14, 15] and vacation_length = 13:
  • First, mid is calculated as 3, and cruise_lengths[3] is 12.
  • Since 12 is less than 13, left is updated to 4.
  • Next, mid is recalculated as 5, and cruise_lengths[5] is 14.
  • Since 14 is greater than 13, right is updated to 4.
  • Finally, mid is recalculated as 4, and cruise_lengths[4] is 13, so the function returns 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 cruise_lengths list.

• Time Complexity: O(log N) because binary search halves the search space in each step.
• Space Complexity: O(1) because we are using a constant amount of extra space.