Frontend School

Netflix Movie Search Autocomplete

DSA
medium

Netflix Movie Search Autocomplete

Medium
Trie
String
Design
Sorting

Overview

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.

What you need to do / Task

Implement the MovieSearchEngine class with the following methods:

  1. constructor(): Initializes the search engine.
  2. addMovie(title: string, popularity: number): Adds a movie title and its associated popularity score to the search engine. Assume movie titles are unique.
  3. 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.

Input & output

MovieSearchEngine()

  • Input: None.
  • Output: Initializes the search engine.

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).
  • Output: 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.
  • Output: string[]. A list of up to k matching movie titles, sorted according to the rules described above.

Clarifications

  • Empty Prefix: If prefix is an empty string, search should return the k most popular movies from the entire catalog, sorted by popularity and then title.
  • No Matches: If no movies match the prefix, search should return an empty array [].
  • Fewer than k matches: If fewer than k movies match the prefix, search should return all matching movies, sorted as specified.
  • Case Sensitivity: The search should be case-sensitive. "the" is different from "The".
  • Popularity Scores: Popularity scores can be any non-negative integer. Higher values indicate higher popularity.
  • Unique Titles: You can assume that 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

1

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:

  1. Initialize MovieSearchEngine.
  2. Add "The Crown" (100), "The Witcher" (120), "The Office" (90).
  3. 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"].
  4. Add "The Mandalorian" (110).
  5. 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"].
  6. search("St", 2): No movies start with "St". Returns [].
2

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:

  1. Initialize MovieSearchEngine.
  2. Add "House of Cards" (80), "House of the Dragon" (110), "House" (90).
  3. 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.
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:

  1. Initialize MovieSearchEngine.
  2. Add "Ozark" (95), "Ozark Season 2" (95), "Ozark Season 1" (98).
  3. 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".
  4. search("", 1): Matches all movies. Sorted: "Ozark Season 1" (98), "Ozark" (95), "Ozark Season 2" (95). Top 1 is ["Ozark Season 1"].

Constraints

Constraints & assumptions

  • 1 <= title.length <= 100
  • title consists only of English letters (lowercase and uppercase), digits, and spaces.
  • 0 <= popularity <= 10^9
  • 1 <= prefix.length <= 100 (or prefix can be empty)
  • 1 <= k <= 100
  • Total number of addMovie calls will not exceed 10^4.
  • Total number of search calls will not exceed 10^4.
  • Total number of characters across all titles and prefixes will not exceed 5 * 10^5.

Out of scope

  • Handling concurrent addMovie or search operations.
  • Advanced fuzzy matching or typo correction.
  • Real-time popularity updates that don't involve explicitly calling addMovie again.

What interviewers evaluate

  • Correctness of Trie Implementation: Ability to correctly build and traverse a Trie for movie titles.
  • Efficiency of Search: How well the search method leverages the Trie for quick prefix matching and subtree traversal.
  • Handling of Popularity and Sorting: Correctly incorporating popularity scores into the search results and applying the specified sorting logic.
  • Edge Case Management: Robustness in handling cases like empty prefixes, no matches, or k being greater than available matches.
  • Code Structure and Readability: Clarity, organization, and maintainability of the code.

Loading editor...