Unit 7 Session 2 (Click for link to problem statements)
Understand what the interviewer is asking for by using test cases and questions about the problem.
preferred_deck
is less than all the cabins in the list?
0
since the preferred deck should be inserted at the start.preferred_deck
is greater than all the cabins in the list?
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.
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:
Plan the solution with appropriate visualizations and pseudocode.
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.
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)`.
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)
Review the code by running specific example(s) and recording values (watchlist) of your code's variables along the way.
[1, 3, 5, 6]
and preferred_deck = 5
:
Evaluate the performance of your algorithm and state any strong/weak or future potential work.
Assume N
represents the length of the cabins
list.
O(log N)
because we are performing binary search.O(log N)
due to the recursive call stack in the worst case.