Active Businesses - Solution & Explanation

Problem Overview: The table stores how many times each business triggered a specific event type. A business is considered active if its occurrence count is higher than the average for that event type in at least two different event categories. The result should return the IDs of such businesses.

Approach 1: Correlated Subquery Comparison (O(n^2) time, O(1) extra space)

A straightforward way compares each row's occurrences value with the average for the same event_type using a correlated subquery. For every record, compute AVG(occurrences) from rows sharing the same event type. If the row's value is greater than the computed average, count it toward that business. Finally, group by business_id and keep businesses where the count of above-average events is at least two.

This approach is easy to reason about but inefficient. The database repeatedly recomputes averages for each row, which leads to repeated scans of the same data. On large datasets the query planner may struggle to optimize it, resulting in near O(n^2) behavior.

Approach 2: Aggregation + Join (O(n) time, O(n) space)

A more efficient solution first calculates the average occurrences per event_type using a grouped subquery. This produces a small derived table mapping each event type to its average. Next, join this derived table back to the original Events table and filter rows where occurrences > avg_occurrences. Each remaining row represents an event where the business performed above the average.

Group these filtered rows by business_id and count how many qualifying event types each business has. Businesses with a count of at least two satisfy the problem requirement. This approach works efficiently because the average for each event type is computed once, then reused through a join.

This pattern—aggregate first, then filter with a join—is common in SQL and database interview problems. It separates the computation of global statistics (averages) from row-level filtering, which allows the optimizer to scan the data only once and leverage grouping efficiently.

Recommended for interviews: The aggregation + join approach is the expected solution. It demonstrates comfort with SQL aggregation, derived tables, and filtering grouped results using GROUP BY with HAVING. Mentioning the correlated subquery shows baseline understanding, but the optimized aggregation pattern reflects stronger SQL query design.