Minimum Average of Smallest and Largest View Counts - 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 to the problem?
  • A: The input is an array view_counts of n integers, where n is even.
• Q: What is the output?
  • A: The output is the minimum element in the list of average view counts calculated by repeatedly removing the smallest and largest view counts and averaging them.
• Q: How are the average view counts calculated?
  • A: By removing the smallest and largest view counts from the array, calculating their average, and then repeating this process until the array is empty.

P-lan

Plan the solution with appropriate visualizations and pseudocode.

General Idea: Sort the array and use two pointers to repeatedly find the smallest and largest view counts, calculate their average, and track the minimum average.

1. Sort the `view_counts` array in ascending order.
2. Initialize an empty list `average_views` to store the calculated averages.
3. Initialize two pointers: `left` at the start of the array and `right` at the end.
4. Iterate `n/2` times:
   1. Calculate the average of the elements at `left` and `right`.
   2. Append the average to the `average_views` list.
   3. Move the `left` pointer one step to the right and the `right` pointer one step to the left.
5. Return the minimum value from the `average_views` list.

⚠️ Common Mistakes

• Not sorting the array before calculating averages, leading to incorrect results.
• Failing to correctly update the pointers after each iteration.
• Not properly handling edge cases, such as when the array has only two elements.

I-mplement

def minimum_average_view_count(view_counts):
    # Sort the view counts in ascending order
    view_counts.sort()
    
    # Initialize an empty list to store the average views
    average_views = []
    
    # Initialize two pointers: one at the start (min) and one at the end (max) of the list
    left = 0
    right = len(view_counts) - 1
    
    # Iterate n/2 times
    while left < right:
        # Calculate the average of the smallest and largest view counts
        average = (view_counts[left] + view_counts[right]) / 2
        # Append the average to the list of average views
        average_views.append(average)
        # Move the pointers inward
        left += 1
        right -= 1
    
    # Return the minimum average from the average_views list
    return min(average_views)