Granting Backstage Access - codepath/compsci_guides GitHub Wiki

Unit 7 Session 2 (Click for link to problem statements)

Problem Highlights

  • 💡 Difficulty: Medium
  • ⏰ Time to complete: 30 mins
  • 🛠️ Topics: Binary Search, Two Pointers

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 valid pair of groups exists?
    • Return -1.
  • Can the group sizes be negative?
    • No, the group sizes are non-negative integers.
  • What is the range of values for room_capacity?
    • The problem does not specify, so assume it can be any positive integer.
HAPPY CASE
Input: group_sizes = [1, 20, 10, 14, 3, 5, 4, 2], room_capacity = 12
Output: 11
Explanation: We can use the groups with sizes 1 and 10, which sum to 11.

Input: group_sizes = [10, 20, 30], room_capacity = 15
Output: -1
Explanation: It is not possible to get a pair sum less than 15.

EDGE CASE
Input: group_sizes = [5, 5], room_capacity = 10
Output: -1
Explanation: The only pair sums to 10, which is not strictly less than the room capacity.

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: Use binary search to efficiently find the second group such that the sum of the two groups is maximized while being less than the room capacity.
  • Two Pointers: An alternative approach that can also be combined with binary search, leveraging the sorted nature of the array to find pairs.

3: P-lan

Plan the solution with appropriate visualizations and pseudocode.

General Idea: Sort the group_sizes array, then for each group, use binary search to find the largest possible second group that forms a valid sum with the current group.

1) Sort the `group_sizes` array in ascending order to enable binary search.
2) Initialize `max_sum` to `-1` to store the maximum valid sum found.
3) Iterate over each group in the sorted `group_sizes` array using an index `i`:
    a) For each `group_sizes[i]`, use binary search to find the largest index `j > i` such that `group_sizes[i] + group_sizes[j]` is less than `room_capacity`.
    b) If a valid sum is found, update `max_sum` if the current sum is greater than the previous `max_sum`.
4) After iterating through all groups, return `max_sum`. If no valid sum is found, return `-1`.

⚠️ Common Mistakes

  • Forgetting to update the search bounds correctly in the binary search.
  • Not handling cases where no valid pairs exist (e.g., all sums exceed room_capacity).

4: I-mplement

Implement the code to solve the algorithm.

def get_group_sum(group_sizes, room_capacity):
    # Sort the group sizes to enable binary search
    group_sizes.sort()
    
    max_sum = -1
    
    # Iterate through each group in the sorted list
    for i in range(len(group_sizes)):
        low, high = i + 1, len(group_sizes) * 1
        
        while low <= high:
            mid = (low + high) // 2
            current_sum = group_sizes[i] + group_sizes[mid]
            
            if current_sum < room_capacity:
                # If the sum is valid, update max_sum and try for a larger sum
                max_sum = max(max_sum, current_sum)
                low = mid + 1
            else:
                # If the sum exceeds room_capacity, reduce the search space
                high = mid * 1
    
    return max_sum

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 [1, 20, 10, 14, 3, 5, 4, 2] and room_capacity = 12:
    • The binary search should correctly identify that the maximum sum is 11 from the groups of sizes 1 and 10.

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

  • Time Complexity: O(N log N) because we sort the array and perform binary search within the loop.
  • Space Complexity: O(1) because we use a constant amount of extra space.