Not Boring Movies - Solution & Explanation

Problem Overview: The cinema table contains movie records with id, movie, description, and rating. Return only movies whose id is odd and whose description is not 'boring'. The result must be sorted by rating in descending order.

Approach 1: SQL Query Using Simple Filtering (O(n log n) time, O(1) extra space)

This is the direct database solution. Filter rows with two conditions: id % 2 = 1 (odd IDs) and description != 'boring'. After filtering, apply ORDER BY rating DESC to sort the result. The database scans rows and performs a sort, giving roughly O(n log n) time due to ordering. This approach relies on standard SQL filtering and works cleanly in ORMs such as SQLAlchemy.

Approach 2: Query Using SQL Conditions (Entity Framework) (O(n log n) time, O(1) extra space)

ORM frameworks like Entity Framework translate high‑level conditions into SQL. You express the same logic using conditional filters: select rows where id % 2 != 0 and description != "boring", then order by rating descending. The ORM generates the SQL query and pushes computation to the database engine. Complexity remains O(n log n) due to sorting, while the query benefits from database indexes if present.

Approach 3: Divide and Conquer (O(n log n) time, O(n) space)

If the dataset is loaded into memory (for example in a service layer), you can split the list of movies into halves, filter each half recursively for valid rows, and merge the results. During the merge step, apply a descending sort by rating similar to merge sort. The divide‑and‑conquer structure keeps filtering independent per segment, and the final merge step maintains ordering. This resembles techniques used in divide and conquer algorithms.

Approach 4: Dynamic Programming (Tabulation) (O(n log n) time, O(n) space)

A tabulation approach processes rows sequentially and stores valid results in a table or list. For each movie, check two conditions: odd ID and non‑boring description. Valid rows are appended to the DP table, which represents the accumulated filtered set. After processing all rows, sort the stored entries by rating in descending order. While DP is unnecessary for this problem, the pattern demonstrates incremental filtering and aggregation often used in dynamic programming workflows.

Recommended for interviews: The straightforward SQL filtering approach is what interviewers expect. It shows you understand conditional selection (WHERE) and result ordering (ORDER BY). Alternative approaches like divide‑and‑conquer or DP demonstrate algorithmic thinking when data is handled outside the database, but the optimal production solution keeps filtering inside the SQL query.