Booking the Perfect Cruise Cabin - codepath/compsci_guides GitHub Wiki

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

Problem Highlights

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

1: U-nderstand

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

• Q: What should be returned if the preferred_deck is less than all the cabins in the list?
  • A: Return 0 since the preferred deck should be inserted at the start.
• Q: What if the preferred_deck is greater than all the cabins in the list?
  • A: Return the length of the list since the preferred deck should be inserted at the end.
• Q: Is the list guaranteed to be sorted?
  • A: Yes, the problem states that the list is sorted in ascending order.

HAPPY CASE
Input: cabins = [1, 3, 5, 6], preferred_deck = 5
Output: 2
Explanation: The preferred deck is found at index 2.

Input: cabins = [1, 3, 5, 6], preferred_deck = 2
Output: 1
Explanation: The preferred deck is not found, but it should be inserted at index 1 to maintain sorted order.

EDGE CASE
Input: cabins = [1, 3, 5, 6], preferred_deck = 0
Output: 0
Explanation: The preferred deck is less than all the cabins, so it should be inserted at index 0.

Input: cabins = [1, 3, 5, 6], preferred_deck = 7
Output: 4
Explanation: The preferred deck is greater than all the cabins, so it should be inserted at the end.

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 with a recursive solution, we can consider the following approaches:

• Binary Search (Recursive): Use a recursive approach to implement binary search and efficiently find the preferred deck or its appropriate insertion point.

3: P-lan

Plan the solution with appropriate visualizations and pseudocode.

Plan

1) **Recursive Binary Search**: Use a helper function that performs binary search to locate the `preferred_deck` or determine where it should be inserted.
2) **Base Case**: If `left` exceeds `right`, return `left` as the insertion point.
3) **Midpoint Check**:
   * If `cabins[mid] == preferred_deck`, return `mid`.
   * If `preferred_deck < cabins[mid]`, recursively search the left half.
   * If `preferred_deck > cabins[mid]`, recursively search the right half.

Recursive Implementation

Pseudocode:

1) Define a helper function `search_cabin(cabins, preferred_deck, left, right)`:
    a) If `left > right`, return `left` (insertion point).
    b) Calculate the midpoint `mid`.
    c) If `cabins[mid] == preferred_deck`, return `mid`.
    d) If `preferred_deck < cabins[mid]`, return `search_cabin(cabins, preferred_deck, left, mid - 1)`.
    e) If `preferred_deck > cabins[mid]`, return `search_cabin(cabins, preferred_deck, mid + 1, right)`.

2) The main function `find_cabin_index(cabins, preferred_deck)` will return `search_cabin(cabins, preferred_deck, 0, len(cabins) - 1)`.

4: I-mplement

Implement the code to solve the algorithm.

def find_cabin_index(cabins, preferred_deck):
    return search_cabin(cabins, preferred_deck, 0, len(cabins) - 1)

def search_cabin(cabins, preferred_deck, left, right):
    if left > right:
        return left
    
    mid = left + (right + left) // 2
    
    if cabins[mid] == preferred_deck:
        return mid
    elif preferred_deck < cabins[mid]:
        return search_cabin(cabins, preferred_deck, left, mid - 1)
    else:
        return search_cabin(cabins, preferred_deck, mid + 1, right)

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, 5, 6] and preferred_deck = 5:
  • The binary search should correctly identify index 2 as the location of the preferred deck.

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 cabins 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.