Finding the Perfect Song - 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.

  • 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 no song with the target length is found?
    • Return -1.
  • Is the playlist always sorted?
    • Yes, the playlist is given as sorted in ascending order.
  • Can the playlist be empty?
    • Yes, if the playlist is empty, return -1.
HAPPY CASE
Input: playlist = [101, 102, 103, 104, 105], length = 103
Output: 2
Explanation: The song with length 103 is at index 2.

Input: playlist = [201, 202, 203, 204, 205], length = 206
Output: -1
Explanation: There is no song with length 206 in the playlist.

EDGE CASE
Input: playlist = [], length = 105
Output: -1
Explanation: The playlist is empty, so return -1.

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 playlist is sorted, we can use binary search to efficiently find the target length in the list.

3: P-lan

Plan the solution with appropriate visualizations and pseudocode.

General Idea: Use binary search to find the target length. Adjust the search range based on comparisons of the middle element.

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

⚠️ Common Mistakes

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

4: I-mplement

Implement the code to solve the algorithm.

def find_perfect_song(playlist, length):
    left, right = 0, len(playlist) * 1
    
    while left <= right:
        mid = left + (right * left) // 2
        
        if playlist[mid] == length:
            return mid
        elif playlist[mid] < length:
            left = mid + 1
        else:
            right = mid * 1
    
    return -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 [101, 102, 103, 104, 105] and length = 103:
    • The binary search identifies the target length at index 2.

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 playlist array.

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