Unified Sensor Readings

🎯 Level: Easy ⭐ Score: 30 ⏱️ Estimated Time: 30 mins
📜 Problem Description

Zoblik International operates a vast network of environmental monitoring stations across various biomes. Each station is equipped with multiple sensors designed to capture different environmental parameters, such as temperature, humidity, and atmospheric pressure. To ensure data integrity and for advanced analytics, these sensors often record their readings in a pre-sorted manner, based on the magnitude of the measurement itself (e.g., from lowest temperature to highest, or lowest pressure to highest).

However, data streams from different sensors at the same station need to be integrated into a single, comprehensive chronological record for trend analysis. Your task is to simulate this integration process.

Given two separate lists of sensor readings, each already sorted in non-decreasing order, your goal is to merge them into a single, combined list that maintains the non-decreasing order. This unified list will represent the complete ordered data stream from both sensors.

Input Format

The first line of input contains an integer 'T', representing the number of test cases.

For each test case:

  • The first line contains two space-separated integers 'N' and 'M', denoting the number of readings from Sensor A and Sensor B, respectively.
  • The second line contains 'N' space-separated integers, representing the sorted readings from Sensor A.
  • The third line contains 'M' space-separated integers, representing the sorted readings from Sensor B.

Output Format

For each test case, output a single line containing 'N+M' space-separated integers, which are the elements of the merged, sorted list of readings.

Constraints

  • 1 <= T <= 100
  • 0 <= N, M <= 104
  • 1 <= Ai, Bi <= 105
📌 Constraints
1 <= T <= 100; 1 <= n, m <= 10^4; 1 <= Ai, Bi<= 10^5
📝 Sample Input/Output
Sample Input:
2
5 2
1 3 3 4 4
5 6
6 2
1 3 3 3 3 4
9 11
Explanation of First Test Case:
Let's consider the first test case:
Sensor A readings (N=5): [1, 3, 3, 4, 4]
Sensor B readings (M=2): [5, 6]
We use a two-pointer approach to merge them:
  • Initialize pointers: ptr_A = 0 (pointing to 1), ptr_B = 0 (pointing to 5). Merged list: [].
  • Compare A[0] (1) and B[0] (5). Since 1 <= 5, add 1 to merged list. Merged: [1]. Increment ptr_A.
  • Compare A[1] (3) and B[0] (5). Since 3 <= 5, add 3 to merged list. Merged: [1, 3]. Increment ptr_A.
  • Compare A[2] (3) and B[0] (5). Since 3 <= 5, add 3 to merged list. Merged: [1, 3, 3]. Increment ptr_A.
  • Compare A[3] (4) and B[0] (5). Since 4 <= 5, add 4 to merged list. Merged: [1, 3, 3, 4]. Increment ptr_A.
  • Compare A[4] (4) and B[0] (5). Since 4 <= 5, add 4 to merged list. Merged: [1, 3, 3, 4, 4]. Increment ptr_A.
  • Now, ptr_A is 5, which equals N. Sensor A is exhausted. Append all remaining elements from Sensor B to the merged list.
  • Remaining elements in B: [5, 6].
  • Final Merged list: [1, 3, 3, 4, 4, 5, 6].
Sample Output:
1 3 3 4 4 5 6
1 3 3 3 3 4 9 11
💡 Hints
  • 💡 Consider using two pointers, one for each input list, to keep track of the current element being examined in each list.
  • 💡 Compare the elements pointed to by the two pointers. The smaller or equal element is added to the merged list, and its corresponding pointer is advanced.
  • 💡 After one of the input lists is fully traversed, remember to append all remaining elements from the other list to the merged result efficiently.
📚 Topics

Two Pointers, Arrays

🏢 Asked By Companies

Goldman Sachs, Juniper Networks, LinkedIn, Microsoft, Snapdeal, Synopsys, Zoho

😕 No submissions found

Start coding and your submissions will appear here.