Merging Captain Marvel's Energy Levels

Edit PagePage History

JCSU Unit 8 Problem Set 1 (Click for link to problem statements)

Problem Highlights

• 💡 Difficulty: Medium
• ⏰ Time to complete: 20-30 mins
• 🛠️ Topics: Sorting, Merging, Divide-and-Conquer

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 is the goal of the problem?
  • Merge two sorted lists into a single sorted list using the divide-and-conquer approach.
• Are there constraints on input?
  • Both input lists are already sorted.

HAPPY CASE Input: energy_readings1 = [1, 3, 5] energy_readings2 = [2, 4, 6] Output: [1, 2, 3, 4, 5, 6] Explanation: The two sorted lists are merged into one sorted list.

EDGE CASE Input: energy_readings1 = [] energy_readings2 = [] Output: [] Explanation: Both input lists are empty, so the result is an empty list.

EDGE CASE Input: energy_readings1 = [1, 2, 3] energy_readings2 = [] Output: [1, 2, 3] Explanation: One input list is empty, so the result is the non-empty list.

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 sorted list merging problems, we want to consider the following approaches:

• Divide-and-Conquer: Use two pointers to merge the two sorted lists efficiently.
• Built-in Sorting (Alternative): Concatenate the lists and use Python's sorted() function (not optimal for already sorted input).

3: P-lan

Plan the solution with appropriate visualizations and pseudocode.

General Idea:
Use two pointers to traverse both lists. Compare elements at the current pointers and append the smaller element to the merged list. If one list is exhausted, append the remaining elements from the other list.

Steps:

1. Initialize two pointers, i and j, to 0 for energy_readings1 and energy_readings2, respectively.
2. Create an empty list merged to store the merged output.
3. Use a loop to compare elements at the current pointers:
   • Append the smaller element to merged and increment the respective pointer.
4. Append any remaining elements from energy_readings1 or energy_readings2.
5. Return the merged list.

4: I-mplement

Implement the code to solve the algorithm.

def merge_energy_levels(energy_readings1, energy_readings2):
    # Initialize pointers for both lists
    i, j = 0, 0
    merged = []  # List to store the merged sorted output

    # Compare elements from both lists and append the smaller one to the merged list
    while i < len(energy_readings1) and j < len(energy_readings2):
        if energy_readings1[i] < energy_readings2[j]:
            merged.append(energy_readings1[i])
            i += 1
        else:
            merged.append(energy_readings2[j])
            j += 1

    # Add any remaining elements from energy_readings1
    while i < len(energy_readings1):
        merged.append(energy_readings1[i])
        i += 1

    # Add any remaining elements from energy_readings2
    while j < len(energy_readings2):
        merged.append(energy_readings2[j])
        j += 1

    return merged  # Return the fully merged and sorted list

5: R-eview

Review the code by running specific example(s) and recording values (watchlist) of your code's variables along the way.

Example 1:

• Input: energy_readings1 = [1, 3, 5], energy_readings2 = [2, 4, 6]
• Expected Output: [1, 2, 3, 4, 5, 6]
• Observed Output: [1, 2, 3, 4, 5, 6]

Example 2:

• Input: energy_readings1 = [], energy_readings2 = []
• Expected Output: []
• Observed Output: []

Example 3:

• Input: energy_readings1 = [10, 20], energy_readings2 = [15, 30]
• Expected Output: [10, 15, 20, 30]
• Observed Output: [10, 15, 20, 30]

6: E-valuate

Evaluate the performance of your algorithm and state any strong/weak or future potential work.

Assume n is the size of energy_readings1 and m is the size of energy_readings2.

• Time Complexity: O(n + m) because we traverse each list once.
• Space Complexity: O(n + m) because we create a new list to store the merged output.