Description
Write a program to implement autocomplete for a given set of N strings and positive weights. That is, given a prefix and an integer k, find the top k strings in the set among those that start with the prefix.
Autocomplete is an important feature of many modern applications. As the user types, the program predicts the complete term (typically a word or phrase) that the user intends to type. Autocomplete is most effective when there are a limited number of likely terms. For example, the Internet Movie Database uses it to display the names of movies as the user types; search engines use it to display suggestions as the user enters web search queries; cell phones use it to speed up text input.
In these examples, the application predicts how likely it is that the user is typing each term and presents to the user a list of the top k matching terms, in decreasing order of weight. These weights are determined by historical data, such as box office revenue for movies, frequencies of search queries from other Google users, or the typing history of a cell phone user. For the purposes of this assignment, you will have access to a list of all possible terms and associated weights (and the terms and weights will not change).
The performance of autocomplete functionality is critical in many systems. For example, consider a search engine which runs an autocomplete application on a server farm. According to one study, the application has only about 50ms to return a list of suggestions for it to be useful to the user. Moreover, in principle, it must perform this computation for every keystroke typed into the search bar and for every user!
In this assignment, you will implement autocomplete in two different ways. The first, BruteAutocomplete.java, is a naïve, brute-force solution. The second, Autocomplete.java, will use a fancier data structure (of your own design) to improve performance substantially.
Brute force. Write an immutable data type BruteAutocomplete.java that provides autocomplete functionality for a given set of terms and weights by implementing the API below. Your brute-force implementation should maintain the terms and weights in two parallel arrays. To find the top kmatching terms, scan through all of the terms, identifying those that start with the given prefix, and return the top k such terms.
public class BruteAutocomplete
{
// Initializes an autocomplete data structure from the given parallel arrays of terms and weights.
public BruteAutocomplete(String[] terms, double[] weights)
// Returns the weight of the term, or 0.0 if no such term.
public double weightOf(String term)
// Returns a top matching term, or null if no matching term.
public String topMatch(String prefix)
// Returns the top k matching terms (in descending order of weight), as an iterable.
// If fewer than k matches, return all matching terms (in descending order of weight).
public Iterable
