## Index a CSV Movie Catalog for Fast Year-Range Queries Design a class that loads a CSV movie catalog once and then answers frequent year-range filters quickly. Construction may do substantial preprocessing; query latency is the priority. For a concrete baseline, each CSV record contains `movie_id`, `title`, and `release_year`. Movie IDs are unique, titles may contain quoted commas, and the catalog is immutable after construction. Implement or describe: ```text MovieCatalog(csv_text) findByYearRange(start_year, end_year) -> list of movie records ``` The range is inclusive. Return matching records ordered by `release_year`, breaking ties by their original CSV order. A reversed range returns an empty list. State whether malformed rows reject the whole catalog or are reported separately, and apply that policy consistently. ### Constraints & Assumptions - Use a real CSV parser; splitting each line on commas is not sufficient for quoted titles. - Do not assume that input records are already ordered by year. - Duplicate release years are common even though movie IDs are unique. - Optimize for many reads over a static catalog; construction complexity is secondary. - Express query cost in terms of catalog size `n` and returned records `r`. ### Part 1 — Parse and Build the Catalog Define the movie record and the constructor's validation and indexing steps. Explain how original CSV order is retained for deterministic ties. #### What This Part Should Cover - Standards-compliant CSV parsing and typed year conversion. - A clear malformed-row and duplicate-ID policy. - An immutable in-memory representation after construction. - Preprocessing that supports range boundaries without scanning every movie. ```hint Preserve a stable tie key If many movies share a year, retain each row's original position before building the search index. ``` ### Part 2 — Answer and Test Range Queries Show how `findByYearRange` locates the first record at or after `start_year` and the first record after `end_year`. Cover empty catalogs, years outside the data, duplicate years, and reversed ranges. #### What This Part Should Cover - Boundary searches over an order compatible with the required output. - Inclusive handling of both endpoints. - `O(log n + r)` query time rather than an `O(n)` scan. - Tests that expose off-by-one errors and unstable ordering. ```hint Search for two boundaries The desired records form one contiguous slice once the index is ordered by year and stable tie key. ``` ### What a Strong Answer Covers - Uses construction time to create an index suited to repeated filters. - Separates CSV correctness from query logic. - Gives deterministic behavior for malformed rows, duplicate years, and empty ranges. - States construction, query, and storage complexity precisely. ### Follow-up Questions 1. What data structure would you choose if movies could be added continuously? 2. How would you support filters by both year and genre without building every possible compound index? 3. When would a database index be preferable to loading the catalog into one process? 4. How would concurrent readers safely share the catalog while a replacement snapshot is built?