Learn the vocabulary of efficiently finding every stored interval overlapping a query range.
0 / 5 completed
1 / 5
At standup, a dev mentions a data structure that stores a set of intervals and can efficiently find every interval overlapping a given query range, without checking every stored interval one at a time. What is this data structure called?
An interval tree is exactly this: it is a data structure that stores a set of intervals, augmenting a balanced binary search tree with each node tracking the maximum endpoint in its subtree, so it can efficiently find every stored interval overlapping a given query range without checking every stored interval one at a time. A hash collision is an unrelated hash-table concept about two keys sharing a bucket. This augmented-tree-with-max-endpoint approach is exactly why an interval tree can answer an overlap query in logarithmic time instead of scanning the entire set of intervals.
2 / 5
During a design review, the team stores a calendar's set of booked time ranges in an interval tree, specifically because finding every booking that overlaps a new requested time range needs to be fast even as the number of bookings grows large. Which capability does this provide?
An interval tree here provides efficient overlap queries that scale with the tree's depth rather than the number of intervals, since the tree's structure lets it skip entire subtrees that can't contain an overlapping interval instead of checking every booking one at a time. Scanning every stored booking one at a time grows linearly slower as the number of bookings increases, no matter how few of them actually overlap the query. This skip-non-overlapping-subtrees behavior is exactly why an interval tree keeps overlap queries fast even with a large number of stored intervals.
3 / 5
In a code review, a dev notices a calendar-booking feature checks a new requested time range against every single stored booking one at a time in a flat list, instead of storing bookings in an interval tree that can skip non-overlapping subtrees. What does this represent?
This is a missed interval-tree opportunity, since storing bookings in an interval tree would let the overlap check skip entire subtrees that can't contain a match instead of scanning every booking one at a time. A cache eviction policy is an unrelated concept about discarded cache entries. This flat-list-scan pattern is exactly the kind of scaling problem a reviewer flags once the number of stored bookings grows large.
4 / 5
An incident report shows a calendar-booking feature's overlap check grew noticeably slower as the number of stored bookings increased, because it checked a new requested time range against every single stored booking one at a time in a flat list instead of using an interval tree. What practice would prevent this?
Storing bookings in an interval tree lets an overlap check skip entire subtrees that can't contain a match instead of scanning every booking one at a time in a flat list. Continuing to check a new requested time range against every single stored booking in a flat list regardless of how many bookings accumulate over time is exactly what caused the slowdown described in this incident. This interval-tree approach is the standard fix once the flat-list scan is confirmed to slow down as bookings accumulate.
5 / 5
During a PR review, a teammate asks why the team stores bookings in an interval tree instead of simply sorting the flat list of bookings by start time and scanning from there, given that sorting also speeds up some kinds of queries. What is the reasoning?
An interval tree's augmented structure lets it skip entire subtrees that provably can't overlap the query range, giving logarithmic-time overlap queries, while a list sorted only by start time still requires scanning forward past every booking whose start time is early but whose end time might still overlap the query. This is exactly why an interval tree is preferred for frequent overlap queries against a large, changing set of intervals.