Netflix Movie Search Autocomplete
At Netflix, providing a seamless and intelligent search experience is crucial for user engagement. When a user starts typing in the search bar, we want to instantly suggest relevant movie titles. Beyond simple prefix matching, we aim to prioritize highly popular movies and ensure a smooth, efficient lookup process, even with a vast catalog of titles.
This problem challenges you to design and implement a MovieSearchEngine that efficiently stores movie titles along with their popularity scores and provides fast autocomplete suggestions based on a given prefix, prioritizing results by popularity.
Implement the MovieSearchEngine class with the following methods:
constructor(): Initializes the search engine.addMovie(title: string, popularity: number): Adds a movie title and its associated popularity score to the search engine. Assume movie titles are unique.search(prefix: string, k: number): Returns a list of up to k movie titles that start with the given prefix. The results should be sorted primarily by popularity in descending order. If two movies have the same popularity, they should be sorted alphabetically by title in ascending order.MovieSearchEngine()
addMovie(title: string, popularity: number)
title: A string representing the movie title (e.g., "The Crown", "Stranger Things").popularity: An integer representing the movie's popularity score (higher is more popular).void. Adds the movie to the internal data structure.search(prefix: string, k: number)
prefix: A string representing the search query prefix (e.g., "The C", "Stran").k: An integer representing the maximum number of movie titles to return.string[]. A list of up to k matching movie titles, sorted according to the rules described above.prefix is an empty string, search should return the k most popular movies from the entire catalog, sorted by popularity and then title.prefix, search should return an empty array [].k movies match the prefix, search should return all matching movies, sorted as specified.addMovie will be called with unique title values. If the same title were to be added again, it would imply an an update to its popularity, but for this problem, assume unique additions.Examples
Example 1
Input:
operations = ["MovieSearchEngine","addMovie","addMovie","addMovie","search","addMovie","search","search"], params = [[],["The Crown",100],["The Witcher",120],["The Office",90],["The ",2],["The Mandalorian",110],["The ",3],["St",2]]
Output:
[null,null,null,null,["The Witcher","The Crown"],null,["The Witcher","The Mandalorian","The Crown"],[]]
Note:
MovieSearchEngine.search("The ", 2): Matches are "The Crown" (100), "The Witcher" (120), "The Office" (90). Sorted by popularity (desc): "The Witcher", "The Crown", "The Office". Top 2 are ["The Witcher", "The Crown"].search("The ", 3): Matches are "The Crown" (100), "The Witcher" (120), "The Office" (90), "The Mandalorian" (110). Sorted by popularity (desc): "The Witcher", "The Mandalorian", "The Crown", "The Office". Top 3 are ["The Witcher", "The Mandalorian", "The Crown"].search("St", 2): No movies start with "St". Returns [].Example 2
Input:
operations = ["MovieSearchEngine","addMovie","addMovie","addMovie","search"], params = [[],["House of Cards",80],["House of the Dragon",110],["House",90],["House",3]]
Output:
[null,null,null,null,["House of the Dragon","House","House of Cards"]]
Note:
MovieSearchEngine.search("House", 3): Matches are "House of Cards" (80), "House of the Dragon" (110), "House" (90). Sorted by popularity (desc): "House of the Dragon" (110), "House" (90), "House of Cards" (80). Returns all 3.Example 3
Input:
operations = ["MovieSearchEngine","addMovie","addMovie","addMovie","search","search"], params = [[],["Ozark",95],["Ozark Season 2",95],["Ozark Season 1",98],["Ozark",2],["",1]]
Output:
[null,null,null,null,["Ozark Season 1","Ozark"],["Ozark Season 1"]]
Note:
MovieSearchEngine.search("Ozark", 2): Matches are "Ozark" (95), "Ozark Season 2" (95), "Ozark Season 1" (98). Sorted by popularity (desc) then title (asc): "Ozark Season 1" (98), "Ozark" (95), "Ozark Season 2" (95). Top 2 are ["Ozark Season 1", "Ozark"]. Note the alphabetical tie-breaking between "Ozark" and "Ozark Season 2".search("", 1): Matches all movies. Sorted: "Ozark Season 1" (98), "Ozark" (95), "Ozark Season 2" (95). Top 1 is ["Ozark Season 1"].Constraints
1 <= title.length <= 100title consists only of English letters (lowercase and uppercase), digits, and spaces.0 <= popularity <= 10^91 <= prefix.length <= 100 (or prefix can be empty)1 <= k <= 100addMovie calls will not exceed 10^4.search calls will not exceed 10^4.titles and prefixes will not exceed 5 * 10^5.addMovie or search operations.addMovie again.search method leverages the Trie for quick prefix matching and subtree traversal.k being greater than available matches.Loading editor...