Unit 7 Session 1 (Click for link to problem statements)
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?
HAPPY CASE
Input: lst = [1, 2, 3, 3, 3, 4, 5], target = 3
Output: 4
Explanation: The last occurrence of the target 3 is at index 4.
EDGE CASE
Input: lst = [1, 2, 3, 4, 5], target = 6
Output: -1
Explanation: The target value 6 is not in the list.
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.
This problem is a variation of the binary search algorithm, requiring:
Plan the solution with appropriate visualizations and pseudocode.
General Idea: Adapt the binary search to locate the last occurrence of a target value within a sorted array.
1) Initialize pointers for the left and right bounds of the list.
2) Initialize a variable `last_occurrence` to store the index of the last found target.
3) While the left pointer is not greater than the right:
- Calculate the middle index.
- If the middle element is the target, update `last_occurrence` and move the left pointer to continue searching on the right for possible later occurrences.
- If the target is less than the middle element, adjust the right pointer to narrow the search to the left half.
- If the target is greater than the middle element, adjust the left pointer to narrow the search to the right half.
4) Return `last_occurrence` if found; otherwise, return -1.
⚠️ Common Mistakes
Implement the code to solve the algorithm.
def find_last(lst, target):
left, right = 0, len(lst) - 1
last_occurrence = -1
while left <= right:
mid = (left + right) // 2
if lst[mid] == target:
last_occurrence = mid
left = mid + 1 # Continue searching in the right half
elif lst[mid] < target:
left = mid + 1
else:
right = mid - 1
return last_occurrence
Review the code by running specific example(s) and recording values (watchlist) of your code's variables along the way.
Evaluate the performance of your algorithm and state any strong/weak or future potential work.
O(log n)
because the approach still fundamentally relies on binary search, halving the search space with each iteration.O(1)
because it uses a few variables for pointers and does not require additional space based on input size.