Validate interval list symmetric

Question

Given a list of intervals, determine if the list is symmetric around a central point. An interval is defined by a pair of integers [start, end], and the list is considered symmetric if for every interval [a, b] in the list, there exists an interval [c, d] such that the midpoint of [a, b] equals the midpoint of [c, d]. Return true if the list is symmetric, and false otherwise.

Codemia · Accepted Answer

To determine if the list of intervals is symmetric around a central point, we need to recognize that the symmetry can be defined in terms of the midpoints of each interval. An interval [a, b] has a midpoint of (a + b) / 2. The key insight here is that for the list to be symmetric, each midpoint must have a corresponding midpoint that matches it. This suggests a pairing mechanism based on the calculated midpoints of the intervals. A potential pattern to apply here is sorting the intervals based on their midpoints, and then checking if the sorted midpoints are symmetric with respect to the overall midpoint of the list.

1. **Calculate Midpoints**: For each interval [start, end], compute the midpoint as (start + end) / 2. 
2. **Store Midpoints**: Create a list of these midpoints. 
3. **Determine Overall Midpoint**: Compute the overall midpoint of the list as the average of the minimum and maximum midpoints. 
4. **Sort Midpoints**: Sort the list of midpoints. 
5. **Check for Symmetry**: Iterate through the sorted midpoints and check if the ith midpoint equals the (n-i-1)th midpoint, where n is the number of midpoints. If all pairs match, the list is symmetric.

**Example**: Given intervals [[1, 3], [5, 7], [2, 4]], the midpoints will be [2, 6, 3]. The overall midpoint is (2 + 6) / 2 = 4. The sorted midpoints are [2, 3, 6]. The checks will fail since 2 != 6.

Here is the Python implementation for the approach described:

```python
def validate_intervals_symmetric(intervals):
    midpoints = [(start + end) / 2 for start, end in intervals]
    midpoints.sort()
    n = len(midpoints)
    overall_midpoint = (midpoints[0] + midpoints[-1]) / 2
    for i in range(n // 2):
        if midpoints[i] + midpoints[n - 1 - i] != overall_midpoint:
            return False
    return True
```
This function computes midpoints, sorts them, and checks for symmetry efficiently.

The time complexity of the solution is O(n log n) due to the sorting step, where n is the number of intervals. The space complexity is O(n) because we store the midpoints in a separate list. This is efficient given that we are directly processing the list and only require additional space to hold the midpoints for comparison.

1. **Empty List**: An empty list of intervals should return true, as there are no intervals to contradict symmetry. 
2. **Single Interval**: A single interval should also return true, as it trivially has symmetry on itself. 
3. **Identical Intervals**: Lists with identical intervals like [[1, 3], [1, 3], [1, 3]] should return true since all midpoints are equal. 
4. **Non-overlapping Intervals**: Lists like [[1, 2], [3, 4]] should return false as their midpoints are not symmetric. 
5. **Invalid Intervals**: Intervals that are incorrectly formatted or have start greater than end should be handled, possibly returning false or throwing an error.

Validate interval list symmetric

Cloudflare

What the Interviewer Expects

Key Topics to Cover

How to Approach This

Possible Follow-up Questions

Sharpen Your Skills on Codemia

Sample Answer

Problem Analysis

Approach

Submit Your Answer

Cloudflare Software Engineer Interview Guide

Related Questions

Binary Search on graph

Count kth largest element in array

Find connected components in string

Merge Three Sorted strings

Binary Search on string