I have the following Movie class -

class Movie{

    private String genre;
    private String title;
    private Date releaseDate;

    Movie(String genre, String title, Date releaseDate){
        this.genre = genre;
        this.title = title;
        this.releaseDate = releaseDate;
    }

    void setGenre(String genre){
        this.genre = genre;
    }
    void setTitle(String title){
        this.title = title;
    }
    void setReleaseDate(Date releaseDate){
        this.releaseDate = releaseDate;
    }
    String getGenre(){
        retuen genre;
    }
    String getTitle(){
        return title;
    }
    Date getReleaseDate(){
        return releaseDate;
    }
}

I have the following requirements -

1. Create a catalog to store all "Movie" objects (can be of any time complexity)
2. Create a method to return all movies of a certain genre, and time period from the catalog (This method may be called thousands of times, and should be optimized as much as possible)

Here is my implementation so far.

Method 1

void populateCatalog(List<Movie> catalog, String genre, String title, Date date){
        catalog.add(new Movie(genre, title, date));
    }

Method 2

boolean isWithinRange(Date date, Date beforeDate, Date afterDate){
        return !date.before(beforeDate) && !date.after(afterDate);
    }
    
    //timePeriod = "11/1/2020-11/2/2022"
    List<Movie> findGenreTimePeriod(List<Movie> catalog, String genre, String timePeriod){
        List<Movie> result = new ArrayList<>();

        int catalogSize = catalog.size();
        String dates[] = timePeriod.split("-");
        Date beforeDate = new Date(dates[0]);
        Date afterDate = new Date(dates[1]);

        for(int i=0; i<catalogSize; i  ){
            Movie movie = catalog.get(i);
            String movieGenre = movie.getGenre();
            Date date = movie.getDate();
            if(movieGenre.equals(genre) && isWithinRange(date, beforeDate, afterDate));
                result.add(movie);
        }
        
        return result;
    }

My implementation iterates through all items in the catalog and is O(N). Is there an approach that gives better time complexity, perhaps by modifying method 1? Additionally, is there a way to return an iterator class, that returns the information as needed?

CodePudding user response：

Sure. Maintain a Map from genre to TreeMaps from dates to lists of movies, so your query is just get(genre).subMap(fromDate, toDate).values() to get a Collection of Lists of the movies you want in O(log n).

Stop using Date, by the way. It's not the worst time API ever invented, but it's certainly not worth using anymore. So the data structure would presumably be

Map<String, NavigableMap<LocalDate, List<Movie>>>