Merge And Sort Segments — Problem Statement & Solution Guide
Problem Description
Given an array of segments where each segment has an id and a list of scores, create a new merged array with overall scores for each segment, where the score of each segment is the sum of its individual scores, and sort them in descending order of scores. Handle edge cases such as empty input or segments with no scores.
Examples
Input
[{'id': 1, 'scores': [10, 20, 30]}, {'id': 2, 'scores': [5, 10, 15]}]Output
[{'id': 1, 'score': 60}, {'id': 2, 'score': 30}]Explanation: Step-by-step: 1. Initialize an empty list to store the merged segments. 2. Iterate over each segment in the input array. 3. For each segment, calculate the total score by summing up all the scores. 4. Append a new dictionary to the merged list with the segment's id and total score. 5. Sort the merged list in descending order of scores.
Input
[{'id': 1, 'scores': []}, {'id': 2, 'scores': [5, 10, 15]}]Output
[{'id': 2, 'score': 30}, {'id': 1, 'score': 0}]Explanation: Step-by-step: 1. Initialize an empty list to store the merged segments. 2. Iterate over each segment in the input array. 3. For each segment, calculate the total score by summing up all the scores. If the segment has no scores, set the total score to 0. 4. Append a new dictionary to the merged list with the segment's id and total score. 5. Sort the merged list in descending order of scores.
Constraints
- Each segment can have at most 3 test scores.
- The scores can be in the range of 0-100.
- All segment IDs are unique.
- Array size is ≤ 10^5.
- The scores are non-negative integers.
Optimal Approach & Strategy
The optimal approach is to first calculate the sum of scores for each segment, and then sort these segments based on their scores in descending order. This approach uses a hash map to store the sum of scores for each segment, allowing for constant-time lookups and updates. The time complexity of this approach is O(n log n) due to the sorting step.
Brute Force Approach
One possible naive approach is to iterate over each segment in the input array, calculate the sum of scores for that segment, and then compare this sum with the sums of all other segments to determine their order. This approach would result in a time complexity of O(n^2) due to the nested comparisons.
Verified Code Solutions
function mergeAndSortSegments(segments) { if (!segments.length) return []; const mergedSegments = segments.map(segment => ({ id: segment.id, score: segment.scores.reduce((a, b) => a + b, 0) || 0 })); return mergedSegments.sort((a, b) => b.score - a.score); }class Solution {
public List<Map<String, Integer>> mergeAndSortSegments(List<Map<String, List<Integer>>> segments) {
// Calculate total score for each segment
List<Map<String, Integer>> mergedSegments = new ArrayList<>();
for (Map<String, List<Integer>> segment : segments) {
Map<String, Integer> mergedSegment = new HashMap<>();
mergedSegment.put('id', segment.get('id'));
mergedSegment.put('score', segment.get('scores').stream().mapToInt(Integer::intValue).sum());
mergedSegments.add(mergedSegment);
}
// Handle empty array case
if (mergedSegments.isEmpty()) {
return new ArrayList<>();
}
// Handle segment with no scores case
for (Map<String, Integer> segment : mergedSegments) {
if (segment.get('scores').isEmpty()) {
segment.put('score', 0);
}
}
// Sort the merged list in descending order of scores
mergedSegments.sort((a, b) -> b.get('score').compareTo(a.get('score')));
return mergedSegments;
}
}def merge_and_sort_segments(segments):
# Calculate total score for each segment
merged_segments = [{'id': segment['id'], 'score': sum(segment['scores'])} for segment in segments]
# Handle empty array case
if not merged_segments:
return []
# Handle segment with no scores case
for segment in merged_segments:
if not segment['scores']:
segment['score'] = 0
# Sort the merged list in descending order of scores
merged_segments.sort(key=lambda x: x['score'], reverse=True)
return merged_segmentsfunction mergeAndSortSegments(segments) { if (!segments.length) return []; const mergedSegments = segments.map(segment => ({ id: segment.id, score: segment.scores.reduce((a, b) => a + b, 0) || 0 })); return mergedSegments.sort((a, b) => b.score - a.score); }Asked in Top Tech Interviews
Solve in Interative Editor
Ready to test your code? Open our built-in compiler, run custom test suites, and see detailed complexity analysis reports instantly.