Find Shared Motion Periods Across Camera Streams

Question

The candidate is asked to write a function that identifies shared motion periods across multiple camera streams based on their timestamps and motion events.

Codemia · Accepted Answer

To solve the problem of finding shared motion periods across camera streams, we can represent each motion period as an interval defined by a start and end time. The key is to merge overlapping intervals from different camera streams and identify the common time frames. Our approach will involve sorting the intervals and using a two-pointer technique to find overlaps.

1. **Input Representation**: Each camera stream will be represented as a list of tuples, where each tuple contains a start and end time of motion.
2. **Sorting**: First, we will sort the intervals from all camera streams based on their start times.
3. **Merging Intervals**: We will iterate through the sorted list and merge overlapping intervals into a single list of merged intervals.
4. **Finding Overlaps**: Finally, we will compare the merged intervals from each camera stream to find the common time periods.

The time complexity of this solution is O(n log n) due to the sorting step, where n is the total number of intervals across all camera streams. The space complexity is O(m), where m is the number of merged intervals, as we need to store the merged results.

```python
from typing import List, Tuple

def find_shared_motion_periods(camera_streams: List[List[Tuple[int, int]]]) -> List[Tuple[int, int]]:
    merged_intervals = []
    for stream in camera_streams:
        merged_intervals.extend(stream)
    merged_intervals.sort(key=lambda x: x[0])

# Merging intervals
    result = []
    current_start, current_end = merged_intervals[0]
    for start, end in merged_intervals[1:]:
        if start <= current_end:  # Overlapping intervals
            current_end = max(current_end, end)
        else:
            result.append((current_start, current_end))
            current_start, current_end = start, end
    result.append((current_start, current_end))  # Add the last interval

# Finding overlaps
    shared_periods = []
    for i in range(len(result) - 1):
        if result[i][1] >= result[i + 1][0]:
            shared_periods.append((max(result[i][0], result[i + 1][0]), min(result[i][1], result[i + 1][1])))
    return shared_periods
```

It's important to consider edge cases such as:
- No motion detected in any camera stream, which should return an empty list.
- All motion periods are distinct with no overlaps, which should also return an empty list.
- Single camera stream input, where the output should be the same as the input.

Find Shared Motion Periods Across Camera Streams

Serval

What the Interviewer Expects

Key Topics to Cover

How to Approach This

Possible Follow-up Questions

Sharpen Your Skills on Codemia

Sample Answer

Approach

Algorithm

Submit Your Answer

Serval 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