Engagement Boost - codepath/compsci_guides GitHub Wiki

TIP102 Unit 3 Session 1 Standard (Click for link to problem statements)

U-nderstand

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

• Q: What is the input?
  • A: The input is a list of integers representing daily engagement rates, sorted in non-decreasing order.
• Q: What is the output?
  • A: The output is a list of the squares of each engagement rate, sorted in non-decreasing order.
• Q: What constraints should be considered?
  • A: The input list is already sorted, and the solution should efficiently sort the squares of the numbers.

P-lan

Plan the solution with appropriate visualizations and pseudocode.

General Idea: Use the two-pointer technique to efficiently compute the squares of the engagement rates and sort them in non-decreasing order.

1. Initialize two pointers, `left` at the start of the list and `right` at the end.
2. Create a result list initialized with zeros, with the same length as the input list.
3. Iterate over the list from the end towards the beginning:
   1. Compare the square of the value at `left` with the square of the value at `right`.
   2. Place the larger square at the current position in the result list.
   3. Move the corresponding pointer inward (left or right) based on which square was larger.
   4. Decrement the position in the result list.
4. Return the result list, which contains the squared engagements in sorted order.

⚠️ Common Mistakes

• Confusing the order of the squares when placing them in the result list.
• Not considering edge cases such as an empty list or a list with only one element.
• Failing to account for the fact that negative numbers, when squared, can become larger than positive numbers in the list.

I-mplement

Revised Two-Pointer Solution:

def engagement_boost(engagements):
    n = len(engagements)
    result = [0] * n
    left, right = 0, n - 1
    position = n - 1

    while left <= right:
        left_square = engagements[left] * engagements[left]
        right_square = engagements[right] * engagements[right]
        if left_square > right_square:
            result[position] = left_square
            left += 1
        else:
            result[position] = right_square
            right -= 1
        position -= 1

    return result