## Problem Given a list of closed intervals [l, r], find all integer positions that are covered by an odd number of intervals. Return the positions as a sorted list. ```python def odd_coverage(intervals: list[tuple[int,int]]) -> list[int]: # intervals: list of [l, r] inclusive # returns: sorted list of integers covered by an odd number of intervals pass ``` **Example:** ``` odd_coverage([(1,4),(2,6),(5,8)]) # Coverage count: 1->1, 2->2, 3->2, 4->2, 5->2, 6->2, 7->1, 8->1 # Odd positions: [1, 7, 8] -> [1, 7, 8] ``` ## Follow-ups 1. What is the difference array technique and how does it solve this in O(n + max_range)? 2. How do you handle very large coordinate ranges (up to 10^9) without allocating a huge array? 3. How would you generalize this to return ranges of odd-coverage rather than individual points? 4. If intervals can overlap at non-integer boundaries (e.g., [1.5, 3.5]), how does your algorithm change?

InterviewDB Question

Odd Intervals: Find All Integers Covered by an Odd Number of Given Intervals

Onsite

Question Details

Problem Given a list of closed intervals [l, r], find all integer positions that are covered by an odd number of intervals. Return the positions as a sorted list. Example: Follow-ups What is the difference array technique and how does it solve this in O(n + max_range)? How do you handle very large coordinate ranges (up to 10^9) without allocating a huge array? How would you generalize this to return ranges of odd-coverage rather than individual points? If intervals can overlap at non-integer bou…

Full Details

🔒

Unlock all Verkada questions

Full insider details, leaked discussions, and candidate experiences.

or every company, $100/year →

About This Question

This is a reported interview question from a verkada interview during the onsite round.

It covers the following topics: Coding, Arrays, Onsite .

Topics

Coding Arrays Onsite

Odd Intervals: Find All Integers Covered by an Odd Number of Given Intervals

Question Details

Full Details

About This Question

Topics

More Verkada Interview Questions