Index a CSV Movie Catalog for Fast Year-Range Queries

Problem Statement

You are tasked with building an in-memory, immutable movie catalog that ingests movie records from a raw CSV string. Once initialized, the catalog must support repeated, high-throughput queries that retrieve all movie titles released within an inclusive year range [start_year, end_year].

Because read queries occur frequently, scanning the entire dataset on every query is too slow. You must preprocess the data during construction to enable sub-linear search time.

Implement the MovieCatalog class:

class MovieCatalog:
    def __init__(self, csv_data: str):
        """
        Parses the raw CSV string and builds an index optimized for year-range queries.
        """
        pass

    def get_movies_in_range(self, start_year: int, end_year: int) -> list[str]:
        """
        Returns a list of movie titles released between start_year and end_year (inclusive).
        """
        pass

Requirements

1. Data Parsing & Validation:
   • Input CSV consists of a header row (title,year) followed by zero or more data rows.
   • Titles may contain commas, quotes, or whitespace; standard RFC 4180 CSV parsing rules apply.
   • Any row with a missing title or a non-integer year should be skipped.
2. Ordering:
   • Returned titles must be ordered primarily by release year in ascending order.
   • For movies released in the same year, preserve their relative order of appearance from the original CSV input (stable tie-breaking).
3. Query Semantics:
   • If start_year > end_year, return an empty list.
   • The query range is inclusive: start_year <= year <= end_year.
4. Complexity:
   • Constructor: O(N log N) time and O(N) space, where N is the number of valid movies.
   • Query: O(log N + K) time, where K is the number of movies matching the range.

Example

csv_data = """title,year
"Inception",2010
"The Matrix",1999
"Memento",2000
"Fight Club",1999
"Interstellar",2014
"Invalid Movie",unknown
""

catalog = MovieCatalog(csv_data)

# Query movies from 1999 to 2005 inclusive
print(catalog.get_movies_in_range(1999, 2005))
# Output: ["The Matrix", "Fight Club", "Memento"]
# Note: "The Matrix" appears before "Fight Club" because 1999 == 1999 and "The Matrix" was listed first in the CSV.

print(catalog.get_movies_in_range(2015, 2020))
# Output: []

Edge Cases to Consider

• Empty input or input containing only the header row.
• Malformed rows (empty strings, non-numeric years, missing fields).
• Queries where start_year > end_year.
• Queries where all movies fall inside or outside the requested range.