Calculate Orders Within Each Interval - Solution & Explanation

Problem Overview: You are given a table of time intervals and another table containing order timestamps. For each interval, compute how many orders occurred between its start and end time. The result should return the interval along with the total number of orders that fall inside that range.

Approach 1: Correlated Subquery Count (O(n * m) time, O(1) space)

The most direct approach runs a correlated subquery for every interval. For each row in the intervals table, execute a SELECT COUNT(*) on the orders table where the order timestamp falls between start_time and end_time. This works because each interval independently checks all orders. The downside is performance: if there are n intervals and m orders, the database may scan the orders table repeatedly. This method is easy to write but does not scale well for large datasets.

Approach 2: Range Join with Aggregation (O(n + m) to O(n log m) depending on indexing, O(1) extra space)

The efficient solution performs a LEFT JOIN between the intervals table and the orders table using a range condition such as orders.order_time BETWEEN intervals.start_time AND intervals.end_time. After joining, group the results by the interval identifier and use COUNT(order_id) to compute how many orders fall in that range. Because the database can leverage indexes on the order timestamp, it avoids repeated scans and evaluates the condition efficiently. This pattern is a classic range join problem in SQL and frequently appears in analytics-style queries.

Using a LEFT JOIN ensures intervals with zero orders still appear in the result. The GROUP BY aggregation then collapses matching rows into a single count per interval. Most relational databases optimize this pattern well when indexes exist on the timestamp column.

Recommended for interviews: The range join with aggregation is the expected approach. It demonstrates correct use of database querying patterns such as conditional joins, grouping, and counting. Mentioning the correlated subquery approach shows baseline understanding, but using a join with GROUP BY shows stronger SQL skills and familiarity with scalable JOIN operations.